The polynomial method in computational geometry

Seminar
Speaker
Esther Ezra (Bar-Ilan University)
Date
05/01/2020 - 15:30 - 14:00Add to Calendar 2020-01-05 14:00:00 2020-01-05 15:30:00 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. Room 201, Math and CS Building (Bldg. 216) אוניברסיטת בר-אילן - המחלקה למתמטיקה mathoffice@math.biu.ac.il Asia/Jerusalem public
Place
Room 201, Math and CS Building (Bldg. 216)
Abstract

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.

תאריך עדכון אחרון : 01/01/2020