Seminar Details

Let T be a set of n triangles in 3-space, and let G 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 gϵG, such as detecting whether g intersects any triangle of T, reporting all such triangles, counting the number of intersection points between g and the triangles of T, or returning the first triangle intersected by a directed arc g, 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.