Get 20M+ Full-Text Papers For Less Than $1.50/day. Start a 14-Day Trial for You or Your Team.

Learn More →

Kinetic and dynamic data structures for closest pair and all nearest neighbors

Kinetic and dynamic data structures for closest pair and all nearest neighbors Kinetic and Dynamic Data Structures for Closest Pair and All Nearest Neighbors PANKAJ K. AGARWAL Duke University AND HAIM KAPLAN AND MICHA SHARIR Tel Aviv University 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(log2 n) time. Here s is the maximum number of times where the distances between any two speci c 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) log3 n) events, each in O(log3 n) time. Our kinetic data structure for all nearest neighbors http://www.deepdyve.com/assets/images/DeepDyve-Logo-lg.png ACM Transactions on Algorithms (TALG) Association for Computing Machinery

Kinetic and dynamic data structures for closest pair and all nearest neighbors

Download PDF
37 pages

Loading next page...
 
/lp/association-for-computing-machinery/kinetic-and-dynamic-data-structures-for-closest-pair-and-all-nearest-fby9yd5i7p
Publisher
Association for Computing Machinery
Copyright
Copyright © 2008 by ACM Inc.
ISSN
1549-6325
DOI
10.1145/1435375.1435379
Publisher site
See Article on Publisher Site

Abstract

Kinetic and Dynamic Data Structures for Closest Pair and All Nearest Neighbors PANKAJ K. AGARWAL Duke University AND HAIM KAPLAN AND MICHA SHARIR Tel Aviv University 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(log2 n) time. Here s is the maximum number of times where the distances between any two speci c 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) log3 n) events, each in O(log3 n) time. Our kinetic data structure for all nearest neighbors

Journal

ACM Transactions on Algorithms (TALG) – Association for Computing Machinery

Published: Nov 1, 2008

There are no references for this article.