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 -