LAUSR

Given a set P of n moving points in fixed dimension d, where the trajectory of each point is a polynomial of degree bounded by some constant, we present a kinetic data structure (KDS) for maintenance of the closest pair on P. Assuming the closest pair distance is between 1 and $$\varDelta $$Δ over time, our KDS uses $$O(n \log \varDelta )$$O(nlogΔ) space and processes $$O(n^{2} \beta \log \varDelta \log n + n^{2} \beta \log \varDelta \log \log \varDelta )$$O(n2βlogΔlogn+n2βlogΔloglogΔ) events, each in worst-case time $$O(\log ^2 n + \log ^2 \log \varDelta )$$O(log2n+log2logΔ). Here, $$\beta $$β is an extremely slow-growing function. The locality of the KDS is $$O(\log n + \log \log \varDelta )$$O(logn+loglogΔ). Our closest pair KDS supports insertions and deletions of points. An insertion or deletion takes worst-case time $$O(\log \varDelta \log ^2 n + \log \varDelta \log ^2 \log \varDelta )$$O(logΔlog2n+logΔlog2logΔ). Also, we use a similar approach to provide a KDS for the all $$\varepsilon $$ε-nearest neighbors in $$\mathbb {R}^d$$Rd. The complexities of the previous KDSs, for both closest pair and all $$\varepsilon $$ε-nearest neighbors, have polylogarithmic factors, where the number of logs depends on dimension d. Assuming $$\varDelta $$Δ is polynomial in n, our KDSs obtain improvements on the previous KDSs. Our solutions are based on a kinetic clustering on P. Though we use ideas from the previous clustering KDS by Hershberger, we simplify and improve his work.