Personal tools
You are here: Home CG seminar 2019 An Efficient Algorithm for Generalized Polynomial Partitioning and Its Applications
« October 2019 »
October
SuMoTuWeThFrSa
12345
6789101112
13141516171819
20212223242526
2728293031
Log in


Forgot your password?
 

An Efficient Algorithm for Generalized Polynomial Partitioning and Its Applications

Wednesday, April 3rd, 2019, 16:10

Schreiber 309

underline

An Efficient Algorithm for Generalized Polynomial Partitioning and Its Applications

Esther Ezra, BIU

Abstract:

n 2015, Guth proved that if S is a collection of n g-dimensional semi-algebraic sets in R^d and if D\geq 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 \setminus Z(P) intersects O(n/D^{d-g}) sets from S (where Z(p) is the zero set of P). 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 several applications of our result including data structures that support point-enclosure queries, range search queries, and vertical ray-shooting queries among semi-algebraic sets in R^d.

 

Joint work with Pankaj Agarwal, Boris Aronov, and Josh Zahl

Document Actions