Abstract:
This talk will be a presentation of work from papers by Jie Gao, Leonidas Guibas, and An Nguyen in SoCG 2004 and DCOSS 2005.
For a set S of points in Rd, 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. The authors propose a new sparse (1+ε)-spanner with O(n/εd) edges, where ε is a specified parameter. This spanner can be efficiently maintained under dynamic insertion or deletion of points, as well as under continuous motion of the points in both the kinetic data structures setting and in the more realistic blackbox displacement model they introduce. Deformable spanners succinctly encode 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.