## ICS 269, Fall 2005: Theory Seminar

# Deformable Spanners

## Jonathan Sun

### November 18, 2005, in CS 259

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 R^{d}, 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.