Efficient Algorithm for Generalized Polynomial Partitioning and Its Applications
Pankaj K. Agarwal, Boris S. Aronov, Esther E. Ezra, Joshua Zahl · SIAM Journal on Computing · 2021
In 2015, Guth proved that if $\EuScript{S}$ is a collection of $n$ $g$-dimensional semialgebraic sets in ${\mathbb{R}}^d$ and if $D\geq 1$ is an integer, then there is a $d$-variate polynomial $P$ of degree at most $D$ so that each connected component of $\mathbb{R}^d\setminus Z(P)$ intersects $O(n/D^{d-g})$ sets from $\EuScript{S}$. Such a polynomial is called a generalized partitioning polynomial. We present a randomized algorithm that computes such polynomials efficiently---the expected running time of our algorithm is linear in $\lvert \EuScript{S}\rvert$. Our approach exploits the technique of quantifier elimination combined with that of $\eps$-samples. We also present an extension of our construction to multilevel polynomial partitioning for semialgebraic sets in $\mathbb{R}^d$. We present five applications of our result. The first is a data structure for answering point-enclosure queries among a family of semialgebraic sets in $\mathbb{R}^d$ in $O(\log n)$ time, with storage complexity and expected preprocessing time of $O(n^{d+\eps})$. The second is a data structure for answering range-searching queries with semialgebraic ranges in $\mathbb{R}^d$ in $O(\log n)$ time, with $O(n^{t+\eps})$ storage and expected preprocessing time, where $t > 0$ is an integer that depends on $d$ and the description complexity of the ranges. The third is a data structure for answering vertical ray-shooting queries among semialgebraic sets in $\mathbb{R}^{d}$ in $O(\log^2 n)$ time, with $O(n^{d+\eps})$ storage and expected preprocessing time. The fourth is an efficient algorithm for cutting algebraic curves in $\mathbb{R}^2$ into pseudosegments. The fifth application is for eliminating depth cycles among triangles in $\mathbb{R}^3$, where we show a nearly optimal algorithm to cut $n$ pairwise disjoint nonvertical triangles in ${\mathbb{R}}^3$ into pieces that form a depth order.