For a set of @math points in the plane, this paper presents simple kinetic data structures (KDS's) for solutions to some fundamental proximity problems, namely, the all nearest neighbors problem, the closest pair problem, and the Euclidean minimum spanning tree (EMST) problem. Also, the paper introduces KDS's for maintenance of two well-studied sparse proximity graphs, the Yao graph and the Semi-Yao graph. We use sparse graph representations, the Pie Delaunay graph and the Equilateral Delaunay graph, to provide new solutions for the proximity problems. Then we design KDS's that efficiently maintain these sparse graphs on a set of @math moving points, where the trajectory of each point is assumed to be an algebraic function of constant maximum degree @math . We use the kinetic Pie Delaunay graph and the kinetic Equilateral Delaunay graph to create KDS's for maintenance of the Yao graph, the Semi-Yao graph, all the nearest neighbors, the closest pair, and the EMST. Our KDS's use @math space and @math preprocessing time. We provide the first KDS's for maintenance of the Semi-Yao graph and the Yao graph. Our KDS processes @math (resp. @math ) events to maintain the Semi-Yao graph (resp. the Yao graph); each event can be processed in time @math in an amortized sense. Here, @math is an extremely slow-growing function. Our KDS for maintenance of all the nearest neighbors and the closest pair processes @math events. For maintenance of the EMST, our KDS processes @math events. For all three of these problems, each event can be handled in time @math in an amortized sense. We improve the previous randomized kinetic algorithm for maintenance of all the nearest neighbors by Agarwal, Kaplan, and Sharir, and the previous EMST KDS by Rahmati and Zarei.
A kinetic data structure for the maintenance of a multidimensional range search tree is introduced. This structure is used as a building block to obtain kinetic data structures for two classical geometric proximity problems in arbitrary dlmensions: the first structure maintains the closest pair of a set of continuously moving points, and is provably efficient. The second structure maintains a spanning tree of the moving points whose cost remains within some prescribed factor of the minimum spanning tree.