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

Prosenjit Gupta, Ravi Janardan, Michiel Smid

Research output: Chapter in Book/Report/Conference proceedingConference contribution

9 Scopus citations

Abstract

Generalized intersection searching problems are a class of geometric query-retrieval problems where the questions of interest concern the intersection of a query object with aggregates of geometric objects (rather than with individual objects.) This class contains, as a special case, the well-studied class of standard intersection searching problems and is 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 aggregated 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, segment intersection searching, triangle stabbing, and triangle range searching. The techniques used include: computing suitable sparse representations of the input, persistent data structures, and filtering search.

Original languageEnglish (US)
Title of host publicationProceedings of the Annual Symposium on Computational Geometry
PublisherPubl by ACM
Pages369-378
Number of pages10
ISBN (Print)0897916484, 9780897916486
DOIs
StatePublished - 1994
EventProceedings of the 10th Annual Symposium on Computational Geometry - Stony Brook, NY, USA
Duration: Jun 6 1994Jun 8 1994

Publication series

NameProceedings of the Annual Symposium on Computational Geometry

Other

OtherProceedings of the 10th Annual Symposium on Computational Geometry
CityStony Brook, NY, USA
Period6/6/946/8/94

Fingerprint Dive into the research topics of 'Efficient algorithms for generalized intersection searching on non-iso-oriented objects'. Together they form a unique fingerprint.

Cite this