Intersection Queries for Flat Semi-Algebraic Objects in Three Dimensions and Related Problems
share
Let ๐ฏ be a set of n planar semi-algebraic regions in โ^3 of constant complexity (e.g., triangles, disks), which we call plates. We wish to preprocess ๐ฏ 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 ๐ฏ, reporting all the plates intersected by ฮณ, or counting them. We also consider two simpler cases of this general setting: (i) the input objects are plates and the query objects are constant-degree algebraic arcs in โ^3 (arcs, for short), or (ii) the input objects are arcs and the query objects are plates in โ^3. Besides being interesting in their own right, the data structures for these two special cases form the building blocks for handling 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 ๐ฏ is a set of plates and the query objects are arcs, we obtain a data structure that uses O^*(n^4/3) storage (where the O^*(ยท) notation hides subpolynomial factors) and answers an intersection query in O^*(n^2/3) time. Alternatively, by increasing the storage to O^*(n^3/2), 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.
READ FULL TEXT