Efficient algorithm for generalized polynomial partitioning and its applications

Pankaj K. Agarwaly, Boris Aronov, Esther Ezrax, Joshua Zahl

    Research output: Contribution to journalArticlepeer-review

    Abstract

    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.

    Original languageEnglish (US)
    Pages (from-to)760-787
    Number of pages28
    JournalSIAM Journal on Computing
    Volume50
    Issue number2
    DOIs
    StatePublished - 2021

    Keywords

    • Polynomial partitioning
    • Quantifier elimination
    • Semialgebraic range spaces
    • ϵ-samples

    ASJC Scopus subject areas

    • Computer Science(all)
    • Mathematics(all)

    Fingerprint Dive into the research topics of 'Efficient algorithm for generalized polynomial partitioning and its applications'. Together they form a unique fingerprint.

    Cite this