This paper introduces a new proximity graph, called the @math -Semi-Yao graph ( @math -SYG), on a set @math of points in @math , which is a supergraph of the @math -nearest neighbor graph ( @math -NNG) of @math . We provide a kinetic data structure (KDS) to maintain the @math -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 ( , @math -SYG) in @math . It generalizes and improves on previous work on maintaining the theta graph in @math . As an application, we use the kinetic @math -SYG to provide the first KDS for maintenance of all the @math -nearest neighbors in @math , for any @math . Previous works considered the @math case only. Our KDS for all the @math -nearest neighbors is deterministic. The best previous KDS for all the @math -nearest neighbors in @math is randomized. Our structure and analysis are simpler and improve on this work for the @math case. We also provide a KDS for all the @math -nearest neighbors, which in fact gives better performance than previous KDS's for maintenance of all the exact @math -nearest neighbors. As another application, we present the first KDS for answering reverse @math -nearest neighbor queries on moving points in @math , for any @math .
Using multidimensional range trees, Agarwal, Kaplan, and Sharir (TALG'08) @cite_13 gave KDS's both for maintenance of the closest pair and for all the @math -nearest neighbors in @math . The closest pair KDS by Agarwal al uses @math space and processes @math events, each in amortized time @math ; this KDS is efficient, amortized responsive, local, and compact. Agarwal al gave the first efficient KDS to maintain all the @math -nearest neighbors in @math . For the efficiency of their KDS, they implemented range trees by using randomized search trees (treaps). Their kinetic approach uses @math space and processes @math events; the expected time to process all events is @math . Their all @math -nearest neighbors KDS is efficient, amortized responsive, compact, but in general is not local.
@cite_13
2115704441
We present simple, fully dynamic and kinetic data structures, which are variants of a dynamic two-dimensional range tree, for maintaining the closest pair and all nearest neighbors for a set of n moving points in the plane; insertions and deletions of points are also allowed. If no insertions or deletions take place, the structure for the closest pair uses O(n log n) space, and processes O(n2βs+2(n)log n) critical events, each in O(log2n) time. Here s is the maximum number of times where the distances between any two specific pairs of points can become equal, βs(q) e λs(q) q, and λs(q) is the maximum length of Davenport-Schinzel sequences of order s on q symbols. The dynamic version of the problem incurs a slight degradation in performance: If m ≥ n insertions and deletions are performed, the structure still uses O(n log n) space, and processes O(mnβs+2(n)log3 n) events, each in O(log3n) time. Our kinetic data structure for all nearest neighbors uses O(n log2 n) space, and processes O(n2β2s+2(n)log3 n) critical events. The expected time to process all events is O(n2βs+22(n) log4n), though processing a single event may take Θ(n) expected time in the worst case. If m ≥ n insertions and deletions are performed, then the expected number of events is O(mnβ2s+2(n) log3n) and processing them all takes O(mnβ2s+2(n) log4n). An insertion or deletion takes O(n) expected time.