BIU theory seminar- May 24 : Esther Ezra (BIU) - Recent Developments on Intersection Searching

[Arnold Filtser]

Hello all,

Next week (Wed May 24, at 12) we will meet for our theory seminar.

Location: Building 605 room 14.

See you there,

Arnold

https://theory.cs.biu.ac.il/

Speaker: Esther Ezra (BIU)

Title:  Recent Developments on Intersection Searching.
Abstract: Algebraic techniques have been extensively used in discrete and computational geometry since the early 1980's, beginning with the seminal work of Schwartz and Sharir on the piano movers problem, where they introduced techniques from real algebraic geometry. More recently, Guth and Katz introduced the polynomial partitioning technique and almost settled the classical distinct-distance conjecture. Polynomial partitioning became a central tool in solving incidence problems, as well as other main problems in discrete geometry. Very recently, efficient constructions of partitioning polynomials have led to the solution of fundamental algorithmic problems in computational geometry, including eliminating depth cycles, point location, and semi-algebraic range searching.

In this talk I will present several recent developments in the study of intersection searching - a family of range searching problems. I will first describe a solution to the ray-shooting problem amid triangles in 3-space, where polynomial partitioning serves as a main tool in order to obtain an efficient data structure supporting ray-shooting queries. Then, I will show an extension of this approach, which exploits additional tools in algebraic geometry, resulting in efficient data structures for detecting intersections amid flat objects in 3-space and semi-algebraic arcs.

This talk is based on several joint projects with Pankaj Agarwal, Boris Aronov, Matthew Katz, Micha Sharir, and Joshua Zahl.

[Arnold Filtser]

The seminar will take place tmw as planned (regardless of the strike).

See you there!