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 .
Akinetic data structure(KDS) maintains an attribute of interest in a system of geometric objects undergoing continuous motion. In this paper we develop a concentual framework for kinetic data structures, we propose a number of criteria for the quality of such structures, and we describe a number of fundamental techniques for their design. We illustrate these general concepts by presenting kinetic data structures for maintaining the convex hull and the closest pair of moving points in the plane; these structures behave well according to the proposed quality criteria for KDSs.