# Constructive Polynomial Partitioning for Lines in **R**^{3}:

Revisiting Depth Cycle Elimination

## Esther Ezra, Bar-Ilan University and Georgia Tech

## February 13, 2018

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 $\mathbb{R}^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+\varepsilon})$ bound, for any $\varepsilon >
0$, on the number of pieces one needs to cut the triangles such that
the depth relation they induce does not contain cycles.

Joint work with Boris Aronov.