hide
Free keywords:
-
Abstract:
In a generalized intersection searching problem, a
set, $S$, of colored geometric objects is to be
preprocessed so that given some query object, $q$,
the distinct colors of the objects intersected by
$q$ can be reported
efficiently or the number of such colors can be
counted efficiently. In the dynamic setting, colored objects
can be inserted into or deleted from $S$. These
problems generalize the well-studied standard
intersection searching problems and are rich in
applications. Unfortunately, the techniques known
for the standard problems do not yield efficient
solutions for the generalized problems. Moreover,
previous work on generalized
problems applies only to the static reporting
problems. In this
paper, a uniform framework is presented
to solve efficiently the counting/reporting/dynamic
versions of a variety of generalized
intersection searching problems, including: 1-, 2-,
and 3-dimensional range
searching, quadrant searching, interval intersection
searching, 1- and 2-dimensional
point enclosure searching, and orthogonal segment
intersection searching.
