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 r^d. for any given ε > 0, we construct a graph, that we call the approximate k-nng, where the edge with the ith smallest length incident to a point p in this graph is within a factor of (1 + ε) 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 r^d, where the trajectory of each point p ∈ 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+1 n) events, each in time o(log^d+1 n).