TY - GEN

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

AU - Gupta, Prosenjit

AU - Janardan, Ravi

AU - Smid, Michiel

PY - 1994

Y1 - 1994

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0027929160&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0027929160&partnerID=8YFLogxK

U2 - 10.1145/177424.178096

DO - 10.1145/177424.178096

M3 - Conference contribution

AN - SCOPUS:0027929160

SN - 0897916484

SN - 9780897916486

T3 - Proceedings of the Annual Symposium on Computational Geometry

SP - 369

EP - 378

BT - Proceedings of the Annual Symposium on Computational Geometry

PB - Publ by ACM

T2 - Proceedings of the 10th Annual Symposium on Computational Geometry

Y2 - 6 June 1994 through 8 June 1994

ER -