TY - GEN

T1 - An efficient algorithm for generalized polynomial partitioning and its applications

AU - Agarwal, Pankaj K.

AU - Aronov, Boris

AU - Ezra, Esther

AU - Zahl, Joshua

N1 - Funding Information:
Funding Pankaj K. Agarwal: P. Agarwal was supported by NSF under grants CCF-15-13816, CCF-15-46392, and IIS-14-08846, by an ARO grant W911NF-15-1-0408, and by BSF Grant 2012/229 from the U.S.-Israel Binational Science Foundation. Boris Aronov: B. Aronov was supported by NSF grants CCF-12-18791 and CCF-15-40656, and by grant 2014/170 from the US-Israel Binational Science Foundation. Esther Ezra: E. Ezra was supported by NSF CAREER under grant CCF:AF 1553354 and by Grant 824/17 from the Israel Science Foundation. Joshua Zahl: J. Zahl was supported by an NSERC Discovery grant.
Funding Information:
Pankaj K. Agarwal: P. Agarwal was supported by NSF under grants CCF-15-13816, CCF-15-46392, and IIS-14-08846, by an ARO grant W911NF-15-1-0408, and by BSF Grant 2012/229 from the U.S.-Israel Binational Science Foundation. Boris Aronov: B. Aronov was supported by NSF grants CCF-12-18791 and CCF-15-40656, and by grant 2014/170 from the US-Israel Binational Science Foundation. Esther Ezra: E. Ezra was supported by NSF CAREER under grant CCF:AF 1553354 and by Grant 824/17 from the Israel Science Foundation. Joshua Zahl: J. Zahl was supported by an NSERC Discovery grant.
Publisher Copyright:
© Pankaj K. Agarwal, Boris Aronov, Esther Ezra, and Joshua Zahl.

PY - 2019/6/1

Y1 - 2019/6/1

N2 - In 2015, Guth proved that if S is a collection of n g-dimensional semi-algebraic sets in ℝ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 ℝd \ 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 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 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 search queries with semi-algebraic ranges 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 semi-algebraic sets in ℝd in O(log2 n) time, with O(nd+ε) storage and expected preprocessing time. The fourth is an efficient algorithm for cutting algebraic planar curves into pseudo-segments.

AB - In 2015, Guth proved that if S is a collection of n g-dimensional semi-algebraic sets in ℝ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 ℝd \ 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 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 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 search queries with semi-algebraic ranges 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 semi-algebraic sets in ℝd in O(log2 n) time, with O(nd+ε) storage and expected preprocessing time. The fourth is an efficient algorithm for cutting algebraic planar curves into pseudo-segments.

KW - Polynomial partitioning

KW - Quantifier elimination

KW - Semi-algebraic range spaces

KW - ε-samples

UR - http://www.scopus.com/inward/record.url?scp=85066829557&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85066829557&partnerID=8YFLogxK

U2 - 10.4230/LIPIcs.SoCG.2019.5

DO - 10.4230/LIPIcs.SoCG.2019.5

M3 - Conference contribution

AN - SCOPUS:85066829557

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 35th International Symposium on Computational Geometry, SoCG 2019

A2 - Barequet, Gill

A2 - Wang, Yusu

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 35th International Symposium on Computational Geometry, SoCG 2019

Y2 - 18 June 2019 through 21 June 2019

ER -