In 2015, Guth proved that for any set of k-dimensional  varieties in R^d and for any positive integer D, there exists a polynomial of degree at most D whose zero-set divides R^d into open connected "cells, " so that only a small fraction of the given varieties intersect each cell . Guth's result generalized an earlier result of Guth and Katz for points. Guth's proof relies on a variant of the Borsuk-Ulam theorem, and for k>0, it is unknown how to obtain an explicit representation of such a partitioning polynomial and how to construct it efficiently. In particular, it is unknown how to effectively construct such a polynomial for  curves (or even lines) in R^3. We present an efficient algorithmic construction for this setting. Given a set of n input  curves and a positive integer D, we efficiently construct a decomposition of space into O(D^3\log^3{D}) open cells, each of which meets O(n/D^2) curves from the input. The construction time is O(n^2). For the case of lines in 3-space we present an improved implementation, whose running time is O(n^{4/3}  n). The constant of proportionality in both time bounds depends on D and the maximum degree of the polynomials defining the input curves. As an application, we revisit the problem of eliminating depth cycles among non-vertical lines in 3-space, recently studied by Aronov and Sharir (2018), and show an algorithm that cuts n such lines into O(n^{3/2+ \varepsilon }) pieces that are depth-cycle free, for any \varepsilon > 0. The algorithm runs in O(n^{3/2+ \varepsilon }) time, which is a considerable improvement over  previously known algorithms.
In 2015, Guth proved that for any set of k-dimensional bounded complexity varieties in R^d and for any positive integer D, there exists a polynomial of degree at most D whose zero set divides R^d into open connected sets, so that only a small fraction of the given varieties intersect each of these sets . Guth's result generalized an earlier result of Guth and Katz for points. Guth's proof relies on a variant of the Borsuk-Ulam theorem, and for k>0, it is unknown how to obtain an explicit representation of such a partitioning polynomial and how to construct it efficiently. In particular, it is unknown how to effectively construct such a polynomial for bounded-degree algebraic curves (or even lines) in R^3. We present an efficient algorithmic construction for this setting. Given a set of n input algebraic curves and a positive integer D, we efficiently construct a decomposition of space into O(D^3\log^3{D}) open "cells," each of which meets O(n/D^2) curves from the input. The construction time is O(n^2). For the case of lines in 3-space we present an improved implementation, whose running time is O(n^{4/3} \log^{O(1) n). The constant of proportionality in both time bounds depends on D and the maximum degree of the polynomials defining the input curves. As an application, we revisit the problem of eliminating depth cycles among non-vertical lines in 3-space, recently studied by Aronov and Sharir (2018), and show an algorithm that cuts n such lines into O(n^{3/2+ \epsilon }) pieces that are depth-cycle free, for any \epsilon > 0. The algorithm runs in O(n^{3/2+ \epsilon }) time, which is a considerable improvement over the previously known algorithms.
A
bounded complexity
R
zero-set
zero set
R
"cells, "
sets,
R
cell
of these sets
A
bounded-degree algebraic
A
algebraic
R
cells,
"cells,"
A
\log^{O(1)
R
\varepsilon
\epsilon
R
\varepsilon
\epsilon
R
\varepsilon
\epsilon
A
the