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