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.
Basch, Guibas, and Zhang @cite_24 used a multidimensional range tree to maintain the closest pair. Their KDS uses @math space and processes @math events, each in worst-case time @math . Their KDS, which can be used for higher dimensions as well, is responsive, efficient, compact, and local. The same KDS with the same complexities as @cite_24 was independently presented by Agarwal, Kaplan, and Sharir @cite_11 ; the KDS by Agarwal al supports point insertions and deletions. Fu and Lee @cite_17 proposed the first kinetic algorithm for maintenance of an EMST on a set of @math moving points. Their algorithm uses @math preprocessing time and @math space, where @math is the maximum possible number of changes in the EMST from time @math to @math . At any given time, the algorithm constructs the EMST in linear time.
@cite_24 @cite_17 @cite_11
2175772512 2115704441 2069278600 1987458256
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. 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(n2βs+2(n)log n) critical events, each in O(log2n) time. Here s is the maximum number of times where the distances between any two specific pairs of points can become equal, βs(q) e λ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(log3n) time. Our kinetic data structure for all nearest neighbors uses O(n log2 n) space, and processes O(n2β2s+2(n)log3 n) critical events. The expected time to process all events is O(n2βs+22(n) log4n), though processing a single event may take Θ(n) expected time in the worst case. If m ≥ n insertions and deletions are performed, then the expected number of events is O(mnβ2s+2(n) log3n) and processing them all takes O(mnβ2s+2(n) log4n). An insertion or deletion takes O(n) expected time. We present a new efficient algorithm for the search version of the approximate Closest Vector Problem with Preprocessing (CVPP). Our algorithm achieves an approximation factor of O(n sqrt log n ), improving on the previous best of O(n^ 1.5 ) due to Lag arias, Lenstra, and Schnorr hkzbabai . We also show, somewhat surprisingly, that only O(n) vectors of preprocessing advice are sufficient to solve the problem (with the slightly worse approximation factor of O(n)). We remark that this still leaves a large gap with respect to the decisional version of CVPP, where the best known approximation factor is O(sqrt n log n ) due to Aharonov and Regev AharonovR04 . To achieve these results, we show a reduction to the same problem restricted to target points that are close to the lattice and a more efficient reduction to a harder problem, Bounded Distance Decoding with preprocessing (BDDP). Combining either reduction with the previous best-known algorithm for BDDP by Liu, Lyubashevsky, and Micciancio LiuLM06 gives our main result. In the setting of CVP without preprocessing, we also give a reduction from (1+eps)gamma approximate CVP to gamma approximate CVP where the target is at distance at most 1+1 eps times the minimum distance (the length of the shortest non-zero vector) which relies on the lattice sparsification techniques of Dadush and Kun DadushK13 . As our final and most technical contribution, we present a substantially more efficient variant of the LLM algorithm (both in terms of run-time and amount of preprocessing advice), and via an improved analysis, show that it can decode up to a distance proportional to the reciprocal of the smoothing parameter of the dual lattice MR04 . We show that this is never smaller than the LLM decoding radius, and that it can be up to an wide tilde Omega (sqrt n ) factor larger. 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.