The polynomial method in computational geometry

Since the celebrated work of Guth and Katz on the Erdos distinct distances problem, polynomial partitioning became a central tool in solving incidence problems, as well as other main problems in discrete geometry. In spite of this progress, the application of polynomial partitioning in solving computational problems received considerably less attention. In particular, except for special settings (such as points in d-space), it is currently unknown how to efficiently construct partitioning polynomials for arbitrary semi-algebraic sets. 

In this talk I will present an efficient construction of such partitioning polynomials based on quantifier elimination and epsilon-approximations.

This talk is based on joint work with Pankaj Agarwal, Boris Aronov, and Joshua Zahl.