Math @ Duke

Publications [#235514] of Pankaj K. Agarwal
Papers Published
 Agarwal, PK; Kaplan, H; Sharir, M, Kinetic and dynamic data structures for closest pair and all nearest neighbors,
ACM Transactions on Algorithms, vol. 5 no. 1
(2008), ISSN 15496325 [doi]
(last updated on 2018/03/19)
Abstract: We present simple, fully dynamic and kinetic data structures, which are variants of a dynamic twodimensional range tree, for maintaining the closest pair and all nearest neighbors for a set of n moving points in the plane; insertions and deletions of points are also allowed. If no insertions or deletions take place, the structure for the closest pair uses O(n log n) space, and processes O(n2Βs+2(n)log n) critical events, each in O(log2n) time. Here s is the maximum number of times where the distances between any two specific pairs of points can become equal, Βs(q) = s(q)/q, and s(q) is the maximum length of DavenportSchinzel sequences of order s on q symbols. The dynamic version of the problem incurs a slight degradation in performance: If m n insertions and deletions are performed, the structure still uses O(n log n) space, and processes O(mnΒs+2(n)log3 n) events, each in O(log3n) time. Our kinetic data structure for all nearest neighbors uses O(n log2 n) space, and processes O(n 2Β2s+2(n)log3 n) critical events. The expected time to process all events is O(n2Β s+22(n) log4n), though processing a single event may take Θ(n) expected time in the worst case. If m n insertions and deletions are performed, then the expected number of events is O(mnΒ2s+2(n) log3n) and processing them all takes O(mnΒ2s+2(n) log4n). An insertion or deletion takes O(n) expected time. © 2008 ACM.


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

