- Series
- Combinatorics Seminar
- Time
- Tuesday, July 26, 2022 - 2:00pm for 1 hour (actually 50 minutes)
- Location
- Skiles 202
- Speaker
- Esther Ezra – Bar Ilan University – estherezra@gmail.com
- Organizer
- Xingxing Yu

Let T be a set of n triangles in 3-space, and let \Gamma be a family of

algebraic arcs of constant complexity in 3-space. We show how to preprocess T

into a data structure that supports various "intersection queries" for

query arcs \gamma \in \Gamma, such as detecting whether \gamma intersects any

triangle of T, reporting all such triangles, counting the number of

intersection points between \gamma and the triangles of T, or returning the

first triangle intersected by a directed arc \gamma, if any (i.e., answering

arc-shooting queries). Our technique is based on polynomial partitioning and

other tools from real algebraic geometry, among which is the cylindrical

algebraic decomposition.

Our approach can be extended to many other intersection-searching problems in

three and higher dimensions. We exemplify this versatility by giving an

efficient data structure for answering segment-intersection queries amid a set

of spherical caps in 3-space, and we lay a roadmap for extending our approach

to other intersection-searching problems.

Joint work with Pankaj Agarwal, Boris Aronov, Matya Katz, and Micha Sharir.