Intersection queries in curved objects
A number of problems of the following type are studied: Given a set of n arcs (disks, circles, circular arcs, Jordan arcs) in the plane, preprocess it into a data structure, so that for a query line (or segment) one can quickly (i) report all arcs intersecting it, or (ii) count the number of arcs intersecting it. We also study the ray-shooting problem among disjoint Jordan arcs and circular arcs. Most of the data structures presented here use close to linear space and have query time close to O(√n + K) or O(n2/3 + K), where K is the size of the output. © 1993 Academic Press, Inc.
Agarwal, PK; Van kreveld, M; Overmars, M
Volume / Issue
Start / End Page
International Standard Serial Number (ISSN)
Digital Object Identifier (DOI)