CS 269S, Winter 2012: Theory Seminar
Bren Hall, Room 1423, 1pm
March 8, 2013:

Kinetic Data Structures for All Nearest Neighbors and Closest Pair in the Plane

Joe Simons

This paper presents a kinetic data structure (KDS) for solutions to the all nearest neighbors problem and the closest pair problem in the plane. For a set P of n moving points where the trajectory of each point is an algebraic function of constant maximum degree s, our kinetic algorithm uses O(n) space and O(n log n) preprocessing time and processes O(n2 β2s + 2(n)2 log n) events in amortized O(log n) time per event, where βs(n) is an extremely slow growing function. In terms of the KDS performance criteria, our KDS is efficient, responsive (in an amortized sense), compact, and local (on average).

Our deterministic kinetic algorithm improves by an O(log2 n) factor the previous randomized kinetic algorithm by Agarwal, Kaplan, and Sharir. The improvement is obtained by using a new sparse graph representation, the Pie Delaunay graph, to reduce the problem to one-dimensional range searching, as opposed to the two-dimensional range searching in the previous work. Their KDS is efficient, responsive (in an amortized sense), and compact, but it is not local.

(Based on a paper by Z. Rahmati, V. King, and S. Whitesides, to appear at the 29th ACM Symposium on Computational Geometry, SoCG 2013.)