Kinetic k-Semi-Yao Graph and its Applications

Original · EN

This paper introduces a new proximity graph, called the k-Semi-Yao graph (k-SYG), on a set P of points in Rᵈ, which is a supergraph of the k-nearest neighbor graph (k-NNG) of P. We provide a kinetic data structure (KDS) to maintain the k-SYG on moving points, where the trajectory of each point is a polynomial function whose degree is bounded by some constant. Our technique gives the first KDS for the theta graph (, 1-SYG) in Rᵈ. It generalizes and improves on previous work on maintaining the theta graph in R². As an application, we use the kinetic k-SYG to provide the first KDS for maintenance of all the k-nearest neighbors in Rᵈ, for any k≥ 1. Previous works considered the k=1 case only. Our KDS for all the 1-nearest neighbors is deterministic. The best previous KDS for all the 1-nearest neighbors in Rᵈ is randomized. Our structure and analysis are simpler and improve on this work for the k=1 case. We also provide a KDS for all the (1+ε)-nearest neighbors, which in fact gives better performance than previous KDS's for maintenance of all the exact 1-nearest neighbors. As another application, we present the first KDS for answering reverse k-nearest neighbor queries on moving points in Rᵈ, for any k≥ 1.