MPI-I-93-166
Effizient algorithms for generalized intersection searching on non-iso-oriented objects
Gupta, Prosenjit and Janardan, Ravi and Smid, Michiel
December 1993, 32 pages.
.
Status: available - back from printing
In a generalized intersection searching problem, a set $S$ of
colored geometric objects is to be preprocessed so that, given a
query object $q$, the distinct colors of the objects of $S$ that
are intersected by $q$ can be reported or counted efficiently.
These problems generalize the well-studied standard intersection
searching problems and are rich in applications. Unfortunately,
the solutions known for the standard problems do not yield efficient
solutions to the generalized problems. Recently, efficient solutions
have been given for generalized problems where the input and query
objects are iso-oriented, i.e., axes-parallel, or where the color
classes satisfy additional properties, e.g., connectedness.
In this paper, efficient algorithms are given for several
generalized problems involving non-iso-oriented objects.
These problems include: generalized halfspace range searching in
${\cal R}^d$, for any fixed $d \geq 2$, segment intersection
searching, triangle stabbing, and triangle range searching
in ${\cal R}^2$. The techniques used include: computing suitable
sparse representations of the input, persistent data structures, and
filtering search.
-
MPI-I-93-166.pdf
- Attachement: MPI-I-93-166.dvi.gz (38 KBytes); MPI-I-93-166.pdf (168 KBytes)
URL to this document: https://domino.mpi-inf.mpg.de/internet/reports.nsf/NumberView/1993-166
BibTeX
@TECHREPORT{GuptaJanardanSmid93b,
AUTHOR = {Gupta, Prosenjit and Janardan, Ravi and Smid, Michiel},
TITLE = {Effizient algorithms for generalized intersection searching on non-iso-oriented objects},
TYPE = {Research Report},
INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
NUMBER = {MPI-I-93-166},
MONTH = {December},
YEAR = {1993},
ISSN = {0946-011X},
}