Intersection queries for curved objects (extended abstract)
Pankaj K. Agarwal, Marc J. van Kreveld, Mark Overmars · 1991
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) 1, one can quickly (i) report all arcs intersecting /?, or (ii) count the number of arcs intersecting L We also stud y 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 0(/E+K) or 0(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.