TY - JOUR

T1 - Algorithms for generalized halfspace range searching and other intersection searching problems

AU - Gupta, Prosenjit

AU - Janardan, Ravi

AU - Smid, Michiel

N1 - Copyright:
Copyright 2017 Elsevier B.V., All rights reserved.

PY - 1996/3

Y1 - 1996/3

N2 - 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 have many 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 objects that are not necessarily iso-oriented. These problems include: generalized halfspace range searching in Rd, for any fixed d ≥ 2, and segment intersection searching, triangle stabbing, and triangle range searching in R2 for certain classes of line segments and triangles. The techniques used include: computing suitable sparse representations of the input, persistent data structures, and filtering search.

AB - 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 have many 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 objects that are not necessarily iso-oriented. These problems include: generalized halfspace range searching in Rd, for any fixed d ≥ 2, and segment intersection searching, triangle stabbing, and triangle range searching in R2 for certain classes of line segments and triangles. The techniques used include: computing suitable sparse representations of the input, persistent data structures, and filtering search.

KW - Computational geometry

KW - Data structures

KW - Filtering search

KW - Geometric duality

KW - Intersection searching

KW - Persistence

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

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

U2 - 10.1016/0925-7721(94)00019-0

DO - 10.1016/0925-7721(94)00019-0

M3 - Article

AN - SCOPUS:0041063641

VL - 5

SP - 321

EP - 340

JO - Computational Geometry: Theory and Applications

JF - Computational Geometry: Theory and Applications

SN - 0925-7721

IS - 6

ER -