Approximate k-Nearest Neighbor Graph on Moving Points

In this paper, we introduce an approximation for the k-nearest neighbor graph (k-NNG) on a point set P in \mathbb{R}^d. For any given \varepsilon>۰, we construct a graph, that we call the \emph{approximate k-NNG}, where the edge with the ith smallest length incident to a point p in this graph is within a factor of (۱+\varepsilon) of the length of the edge with the ith smallest length incident to p in the k-NNG. For a set P of n moving points in \mathbb{R}^d, where the trajectory of each point p\in P is given by d polynomial functions of constant bounded degree, where each function gives one of the d coordinates of p, we compute the number of combinatorial changes to the approximate k-NNG, and provide a kinetic data structure (KDS) for maintenance of the edges of the approximate k-NNG over time. Our KDS processes O(kn^۲\log^{d+۱} n) events, each in time O(\log^{d+۱}n).

کلیدواژه ها:

approximation ، k-Nearest Neighbor Graph ، Moving Points