A Clustering-Based Approach to Kinetic Closest Pair

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 Δ over time, our KDS uses O(nlog Δ) space and processes O(n²βlog Δlog n+ n²βlog Δlog log Δ) events, each in worst-case time O(log ²n+ log ²log Δ). Here, β is an extremely slow-growing function. The locality of the KDS is O(log n+ log log Δ). Our closest pair KDS supports insertions and deletions of points. An insertion or deletion takes worst-case time O(log Δlog ²n+ log Δlog ²log Δ). Also, we use a similar approach to provide a KDS for the all ε-nearest neighbors in R^d. The complexities of the previous KDSs, for both closest pair and all ε-nearest neighbors, have polylogarithmic factors, where the number of logs depends on dimension d. Assuming Δ 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.