Intersection queries for curved objects
© 1991 ACM. The following class of query problems is studied: Given a set of n arcs (disks, circles, circular arcs, Jordan arcs) in the plane, preprocess it into a data structure, such that for a query line (or segment) ℓ, one can quickly (i) report all arcs intersecting ℓ, or (ii) count the number of arcs intersecting ℓ. We also study the ray shooting problem for disjoint Jordan arcs and for circular arcs. Most of the data structures presented here use linear or near to linear space and have query time near to O(√n+K) or O(n2/3 + K), where K is the size of the output. The query time of some of our algorithms can be improved by allowing more space.
Agarwal, PK; Kreveld, MV; Overmars, M
Proceedings of the Annual Symposium on Computational Geometry
Start / End Page
International Standard Book Number 10 (ISBN-10)
Digital Object Identifier (DOI)