deformable spanners and applications
For a set S of points in &Ropf; 3 , an s -spanner is a graph on S such that any pair of points is connected via some path in the spanner whose total length is at most s times the Euclidean distance between the points. In this paper we propose a new sparse (1+?)-spanner with O ( n /? d ) edges, where ? is a specified parameter. The key property of this spanner is that it can be efficiently maintained under dynamic insertion or deletion ofpoints, as well as under continuous motion of the points in both the kinetic data structures setting and in the more realistic blackbox displacement model we introduce. Our deformable spanner succinctly encodes all proximity information in a deforming point cloud, giving us efficient kinetic algorithms for problems such as the closest pair, the near neighbors of all points, approximate nearest neighbor search (aka approximate Voronoi diagram), well-separated pair decomposition, and approximate k -centers.
kinetic data structures approximate nearest neighbor well-separated pair decomposition collision detection proximity maintenance spanner graphs geometric  k -center