Georgia Institute of Technology College of Sciences

A recent extension by Guth (2015) of 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 R^d, such that its zero set subdivides space into open cells, each meeting only a small fraction of the given varieties. For k > 0, 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 setting of n algebraic curves, or, in fact, just lines, in 3-space. In this work we present an efficient algorithmic construction for this setting almost matching the bounds of Guth (2015); For any D > 0, we efficiently construct a decomposition of space into O(D^3\log^3{D}) open cells, each of which meets at most O(n/D^2) curves from the input. The construction time is O(n^2), where the constant of proportionality depends on the maximum degree of the polynomials defining the input curves. For the case of lines in 3-space we present an improved implementation using a range search machinery. As a main application, we revisit the problem of eliminating depth cycles among non-vertical pairwise disjoint triangles in 3-space, recently been studied by Aronov et al. Joint work with Boris Aronov and Josh Zahl.