Kinetic and dynamic data structures for closest pair and all nearest neighbors
Abstract
We present simple, fully dynamic and kinetic data structures, which are variants of a dynamic two-dimensional 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 ( n 2 β s +2 ( n )log n ) critical events, each in O (log 2 n ) 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 Davenport-Schinzel 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 )log 3 n ) events, each in O (log 3 n ) time.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Nov 01, 2008
- Source ID
- 10.1145/1435375.1435379
Entities
People
- Haim Kaplan
- Micha Sharir
- Pankaj Agarwal
Organizations
- Army Research Office
- Division of Computing and Communication Foundations
- Division of Environmental Biology
- Duke University
- Israel Science Foundation
- National Science Foundation
- Tel Aviv University