Math @ Duke

Publications [#235578] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Vankreveld, M; Overmars, M, Intersection Queries in Curved Objects,
Journal of Algorithms, vol. 15 no. 2
(1993),
pp. 229266, ISSN 01966774 [doi]
(last updated on 2017/12/13)
Abstract: 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 rayshooting 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. All rights reserved.


dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821
 
Mathematics Department
Duke University, Box 90320
Durham, NC 277080320

