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.
The nearest neighbor graph is a subgraph of the Delaunay triangulation and the Euclidean minimum spanning tree. Thus by maintaining either one of these supergraphs over time, all the nearest neighbors can also be maintained. In particular, by using the kinetic Delaunay triangulation @cite_22 or the kinetic Euclidean minimum spanning tree @cite_26 , together with a basic tool in the KDS framework called the kinetic tournament tree @cite_4 , we can maintain all the nearest neighbors over time. For both these two approaches, the number of internal events is nearly cubic in @math . Since the number of external events for all the nearest neighbors is nearly quadratic, neither of these two approaches will give an efficient KDS as defined above.
@cite_26 @cite_4 @cite_22
2175772512 2086474457
This paper presents a kinetic data structure (KDS) for maintenance of the Euclidean minimum spanning tree (EMST) on a set of moving points in 2-dimensional space. For a set of n points moving in the plane we build a KDS of size O(n) in O(nlogn) preprocessing time by which the EMST is maintained efficiently during the motion. This is done by applying the required changes to the combinatorial structure of the EMST which is changed in discrete timestamps. We assume that the motion of the points, i.e. x and y coordinates of the points, are defined by algebraic functions of constant maximum degree. In terms of the KDS performance parameters, our KDS is responsive, local, and compact. The presented KDS is based on monitoring changes of the Delaunay triangulation of the points and edge-length changes of the edges of the current Delaunay triangulation. Akinetic data structure(KDS) maintains an attribute of interest in a system of geometric objects undergoing continuous motion. In this paper we develop a concentual framework for kinetic data structures, we propose a number of criteria for the quality of such structures, and we describe a number of fundamental techniques for their design. We illustrate these general concepts by presenting kinetic data structures for maintaining the convex hull and the closest pair of moving points in the plane; these structures behave well according to the proposed quality criteria for KDSs.