Math @ Duke

Publications [#235568] of Pankaj K. Agarwal
Papers Published
 Kreveld, MV; Overmars, M; Agarwal, PK, Intersection queries in sets of disks,
BIT Numerical Mathematics, vol. 32 no. 2
(1992),
pp. 268279, ISSN 00063835 [doi]
(last updated on 2018/03/17)
Abstract: 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 nonintersecting 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.


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

