de.mpg.escidoc.pubman.appbase.FacesBean
English
 
Help Guide Disclaimer Contact us Login
  Advanced SearchBrowse

Item

ITEM ACTIONSEXPORT

Released

Report

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

MPS-Authors
http://pubman.mpdl.mpg.de/cone/persons/resource/persons45509

Smid,  Michiel
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

http://pubman.mpdl.mpg.de/cone/persons/resource/persons44551

Gupta,  Prosenjit
Algorithms and Complexity, MPI for Informatics, Max Planck Society;

Locator
There are no locators available
Fulltext (public)

MPI-I-92-154.pdf
(Any fulltext), 28MB

Supplementary Material (public)
There is no public supplementary material available
Citation

Smid, M., & Gupta, P.(1992). Further results on generalized intersection searching problems: counting, reporting, and dynamization (MPI-I-92-154). Saarbrücken: Max-Planck-Institut für Informatik.


Cite as: http://hdl.handle.net/11858/00-001M-0000-0014-B721-F
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.