Efficient algorithm for generalized polynomial partitioning and its applications

In 2015, Guth proved that if S is a collection of n g-dimensional semialgebraic sets in Rd and if D ≥1 is an integer, then there is a d-variate polynomial P of degree at most D so that each connected component of Rd \ Z(P) intersects O(n/Dd-g) sets from 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 |S|. Our approach exploits the technique of quantifier elimination combined with that of ϵ-samples. We also present an extension of our construction to multilevel polynomial partitioning for semialgebraic sets in Rd. 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 Rd in O(log n) time, with storage complexity and expected preprocessing time of O(nd+ϵ). The second is a data structure for answering range-searching queries with semialgebraic ranges in Rd in O(log n) time, with O(nt+ϵ) 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 Rd in O(log2 n) time, with O(nd+ϵ) storage and expected preprocessing time. The fourth is an efficient algorithm for cutting algebraic curves in R2 into pseudosegments. The fifth application is for eliminating depth cycles among triangles in R3, where we show a nearly optimal algorithm to cut n pairwise disjoint nonvertical triangles in R3 into pieces that form a depth order.