Abstract
Three classes of geometric intersection searching problems are
considered, i.e., problems in which a set $S$ of geometric
objects is to be preprocessed into a data structure so
that for any query object $q$, the objects of $S$ that are
intersected by $q$ can be counted or reported efficiently.
In the first class, $S$ is a set of linear objects, such as lines
or line segments, and $q$ is a curved object, such as a circle,
disk, or circular arc. In the second class, $S$ is a set of
curved objects, such as $d$-balls, $d$-spheres, circles,
or circular arcs, and $q$ is also a curved object.
In the third class, which is a generalization of the first two,
the objects in $S$ are curved or linear and each is assigned
a color. Given a query $q$, such as a disk or an annulus,
the goal is to count or report the distinct colors of the
objects intersected by $q$.
Efficient solutions are presented for a wide variety of
problems from these classes. The solution techniques are based
on geometric transformations, on compositions of known solutions
for simplex range searching, on the locus approach,
and on persistent data structures. Previously, efficient solutions
for such curved intersection searching problems were known only
for the case where $S$ consists of curved objects and $q$ is linear.
