Max-Planck-Institut für Informatik
max planck institut
mpii logo Minerva of the Max Planck Society


Further results on generalized intersection searching problems: counting, reporting, and dynamization

Smid, Michiel and Gupta, Prosenjit and Janardan, Ravi

MPI-I-92-154. December 1992, 41 pages. | Status: available - back from printing | Next --> Entry | Previous <-- Entry

Abstract in LaTeX format:
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.
References to related material:

To download this research report, please select the type of document that fits best your needs.Attachement Size(s):
MPI-I-92-154.pdfMPI-I-92-154.pdf28224 KBytes
Please note: If you don't have a viewer for PostScript on your platform, try to install GhostScript and GhostView
URL to this document:
Hide details for BibTeXBibTeX
  AUTHOR = {Smid, Michiel and Gupta, Prosenjit and Janardan, Ravi},
  TITLE = {Further results on generalized intersection searching problems: counting, reporting, and dynamization},
  TYPE = {Research Report},
  INSTITUTION = {Max-Planck-Institut f{\"u}r Informatik},
  ADDRESS = {Im Stadtwald, D-66123 Saarbr{\"u}cken, Germany},
  NUMBER = {MPI-I-92-154},
  MONTH = {December},
  YEAR = {1992},
  ISSN = {0946-011X},