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
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.)