# Constructive Polynomial Partitioning for Lines in~$\reals^3$: Revisiting Depth Cycle Elimination

### Wednesday, April 11th, 2018, 16:10

### Schreiber 309

### Constructive Polynomial Partitioning for Lines in~$\reals^3$: Revisiting Depth Cycle Elimination

### Esther Ezra, Bar-Ilan University

### Abstract:

A recent extension of Guth (2015) to the basic polynomial partitioning technique of Guth and Katz (2015) shows the existence of a partitioning polynomial, for a given set of $k$-dimensional varieties in ${\reals}^d$, which subdivides space into open cells each of which meeting only a small fraction of the total number of varieties. For most instances, it is unknown how to obtain an explicit representation of such a partitioning polynomial (and how to construct it efficiently). This, in particular, applies to the (simple) case of lines in $3$-space. In this work we present an efficient algorithmic (but somewhat suboptimal) construction for this setting, under the assumption that the lines are non-vertical and pairwise disjoint. We then revisit the problem of eliminating depth cycles among $n$ non-vertical pairwise disjoint triangles in $3$-space, recently been studied by Aronov etal. (2017) and de Berg (2017). Our main result is an algorithmic $O(n^{5/3+\eps})$ bound, for any $\eps > 0$, on the number of pieces one needs to cut the triangles such that the depth relation they induce does not contain cycles. The running time of our algorithm is comparable with this combinatorial bound.

Joint work with Boris Aronov.