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

Let be a set of n flat (planar) semi-algebraic regions in 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 parametrized algebraic arcs in (arcs, for short), or (ii) the input objects are arcs and the query objects are plates in . 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 present many different data structures for intersection queries, which also provide tradeoffs between their size and query time. For example, if is a set of plates and the query objects are algebraic arcs, we obtain a data structure that uses storage (where the notation hides factors of the form , for an arbitrarily small 0) ]]>) and answers an arc-intersection query in time. This result is significant since the exponents do not depend on the specific shape of the input and query objects. We generalize and slightly improve this result: for a parameter , where is the number of real parameters needed to specify a query arc, the query time can be decreased to by increasing the storage to . Our approach can be extended to many additional intersection-searching problems in three dimensions, even when the input or query objects are not flat.

Duke Scholars

Author Pankaj K. Agarwal Computer Science