Item

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 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 , for any
fixed d ≥ 2, and segment intersection searching, triangle stabbing, and
triangle range searching in 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.