Agarwal, Pankaj K. ;
Aronov, Boris ;
Ezra, Esther ;
Zahl, Joshua
An Efficient Algorithm for Generalized Polynomial Partitioning and Its Applications
Abstract
In 2015, Guth proved that if S is a collection of n gdimensional semialgebraic sets in R^d and if D >= 1 is an integer, then there is a dvariate polynomial P of degree at most D so that each connected component of R^d \ Z(P) intersects O(n/D^{dg}) 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 epsilonsamples.
We present four applications of our result. The first is a data structure for answering pointenclosure queries among a family of semialgebraic 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 semialgebraic 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 rayshooting queries among semialgebraic 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 pseudosegments.
BibTeX  Entry
@InProceedings{agarwal_et_al:LIPIcs:2019:10409,
author = {Pankaj K. Agarwal and Boris Aronov and Esther Ezra and Joshua Zahl},
title = {{An Efficient Algorithm for Generalized Polynomial Partitioning and Its Applications}},
booktitle = {35th International Symposium on Computational Geometry (SoCG 2019)},
pages = {5:15:14},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771047},
ISSN = {18688969},
year = {2019},
volume = {129},
editor = {Gill Barequet and Yusu Wang},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2019/10409},
URN = {urn:nbn:de:0030drops104096},
doi = {10.4230/LIPIcs.SoCG.2019.5},
annote = {Keywords: Polynomial partitioning, quantifier elimination, semialgebraic range spaces, epsilonsamples}
}
11.06.2019
Keywords: 

Polynomial partitioning, quantifier elimination, semialgebraic range spaces, epsilonsamples 
Seminar: 

35th International Symposium on Computational Geometry (SoCG 2019)

Issue date: 

2019 
Date of publication: 

11.06.2019 