# An efficient algorithm for generalized polynomial partitioning and its applications

Conference Paper

In 2015, Guth proved that if S is a collection of n g-dimensional semi-algebraic sets in ℝ 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 ℝ \ Z(P) intersects O(n/D ) 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 R in O(log n) time, with storage complexity and expected preprocessing time of O(n ). The second is a data structure for answering range search queries with semi-algebraic ranges in O(log n) time, with O(n ) 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 ℝ in O(log n) time, with O(n ) storage and expected preprocessing time. The fourth is an efficient algorithm for cutting algebraic planar curves into pseudo-segments. d d d−g d d+ε t+ε d 2 d+ε

### Full Text

### Duke Authors

### Cited Authors

- Agarwal, PK; Aronov, B; Ezra, E; Zahl, J

### Published Date

- June 1, 2019

### Published In

### Volume / Issue

- 129 /

### International Standard Serial Number (ISSN)

- 1868-8969

### International Standard Book Number 13 (ISBN-13)

- 9783959771047

### Digital Object Identifier (DOI)

- 10.4230/LIPIcs.SoCG.2019.5

### Citation Source

- Scopus