##### Personal tools
You are here: Home 2022 Arc-Intersection Queries Amid Triangles in Three Dimensions and Related Problems
« August 2022 »
August
SuMoTuWeThFrSa
123456
78910111213
14151617181920
21222324252627
28293031

# Arc-Intersection Queries Amid Triangles in Three Dimensions and Related Problems

### Abstract:

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 \emph{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 first result is an O^*(n^{4/3})-size data structure that answers a query in
O^*(n^{2/3}) time. Next, we devise an O^*(n)-size data structure that answers a
query in O^*(n^{4/5}) time. Incorporating this structure at the leaf nodes of
the main structure reduces its overall size to O^*(n^{11/9}), without affecting
its query time which remains O^*(n^{2/3}). We also present a data structure
that provides a trade-off between the query time and the size of the data
structure. For example, if \Gamma is a family of algebraic arcs defined by t > 1
real parameters, increasing the storage to O^*(n^{3/2}) decreases the query
time to O^*(n^{\rho}), where \rho=\max {1/2, (2t-3)/3(t-1)} < 2/3. We also show
that this query time can be further improved for circular query arcs.

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.
##### Document Actions 