2026-07-23T03:28:46Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:10409 2024-03-06T10:45:55Z ddc:004 open_access

An Efficient Algorithm for Generalized Polynomial Partitioning and Its Applications Agarwal, Pankaj K. Aronov, Boris Ezra, Esther Zahl, Joshua Polynomial partitioning quantifier elimination semi-algebraic range spaces epsilon-samples In 2015, Guth proved that if S is a collection of n g-dimensional semi-algebraic sets in R^d 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 R^d \ Z(P) intersects O(n/D^{d-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 epsilon-samples. We present four applications of our result. The first is a data structure for answering point-enclosure queries among a family of semi-algebraic sets in R^d in O(log n) time, with storage complexity and expected preprocessing time of O(n^{d+epsilon}). The second is a data structure for answering range search queries with semi-algebraic ranges in O(log n) time, with O(n^{t+epsilon}) 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 semi-algebraic sets in R^{d} in O(log^2 n) time, with O(n^{d+epsilon}) storage and expected preprocessing time. The fourth is an efficient algorithm for cutting algebraic planar curves into pseudo-segments. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Pankaj K. Agarwal and Boris Aronov and Esther Ezra and Joshua Zahl 2019 Is Part Of LIPIcs, Volume 129, 35th International Symposium on Computational Geometry (SoCG 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2019.5 urn:nbn:de:0030-drops-104096 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2019.5 eng https://creativecommons.org/licenses/by/3.0/legalcode