Intersection Queries for Flat Semi-Algebraic Objects in Three Dimensions and Related Problems

Let T be a set of n planar semi-algebraic regions in R³ of constant complexity (e.g., triangles, disks), which we call plates. We wish to preprocess T into a data structure so that for a query object ?, which is also a plate, we can quickly answer various intersection queries, such as detecting whether ? intersects any plate of T, reporting all the plates intersected by ?, or counting them. We focus on two simpler cases of this general setting: (i) the input objects are plates and the query objects are constant-degree algebraic arcs in R³ (arcs, for short), or (ii) the input objects are arcs and the query objects are plates in R³. These interesting special cases form the building blocks for the general case. By combining the polynomial-partitioning technique with additional tools from real algebraic geometry, we obtain a variety of results with different storage and query-time bounds, depending on the complexity of the input and query objects. For example, if T is a set of plates and the query objects are arcs, we obtain a data structure that uses O^*(n⁴/³) storage (where the O^*(·) notation hides subpolynomial factors) and answers an intersection query in O^*(n²/³) time. Alternatively, by increasing the storage to O^*(n³/²), the query time can be decreased to O^*(n^?), where ? = (2t - 3)/3(t - 1) < 2/3 and t = 3 is the number of parameters needed to represent the query arcs.