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

Item

ITEM ACTIONSEXPORT

Released

Report

Effizient algorithms for generalized intersection searching on non-iso-oriented objects

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

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

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

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

Locator
There are no locators available
Fulltext (public)

MPI-I-93-166.pdf
(Any fulltext), 169KB

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

Gupta, P., Janardan, R., & Smid, M.(1993). Effizient algorithms for generalized intersection searching on non-iso-oriented objects (MPI-I-93-166). Saarbrücken: Max-Planck-Institut für Informatik.


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