Department of Mathematics
 Search | Help | Login | pdf version | printable version

Math @ Duke





.......................

.......................


Publications [#235578] of Pankaj K. Agarwal

Papers Published

  1. Agarwal, PK; Vankreveld, M; Overmars, M, Intersection Queries in Curved Objects, Journal of Algorithms, vol. 15 no. 2 (1993), pp. 229-266, ISSN 0196-6774 [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 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. All rights reserved.

 

dept@math.duke.edu
ph: 919.660.2800
fax: 919.660.2821

Mathematics Department
Duke University, Box 90320
Durham, NC 27708-0320