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

Math @ Duke



Publications [#235568] of Pankaj K. Agarwal

Papers Published

  1. Kreveld, MV; Overmars, M; Agarwal, PK, Intersection queries in sets of disks, Bit, vol. 32 no. 2 (1992), pp. 268-279, ISSN 0006-3835 [doi]
    (last updated on 2018/10/21)

    In this paper we develop some new data structures for storing a set of disks that can answer different types of intersection queries efficiency. If the disks are non-intersecting we obtain a linear size data structure that can report all k disks intersecting a query line segment in time O(nβ+ε+k), where n is the number of disks, β=log2(1+√5)-1 ≈ 0.695, and ε is an arbitrarily small positive constant. If the segment is a full line, the query time becomes O(nβ+k). For intersecting disks we obtain an O(n log n) size data structure that can answer an intersection query in time O(n2/3 log2n+k). We also present a linear size data structure for ray shooting queries, whose query time is O(nβ). © 1992 BIT Foundations.
ph: 919.660.2800
fax: 919.660.2821

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