An s-spanner graph in Euclidean space provides a sparse network of paths between pairs of points; the paths are at most s times longer than the distance between their endpoints.
This paper presents the first data structure for sparse graphs that can be efficiently maintained when points are inserted, deleted, or continuously moved (as in a kinetic structure). The resulting 1+ε-spanner, with O(n/εd) edges for points in Rd, can be additionally used for the closest pair problem, approximate nearest neighbor searches, maintaining well-separated pair decompositions, and finding approximate k-centers. The spanners assume a bounded ratio between the greatest and least distances between points in the input set. Such a restriction is natural for modeling deformable shapes (vines, ropes, cloth, or proteins), and whenever physical constraints prevent too-close interactions, or too distant a separation of particles.
Co-authored by L. Guibas, an authority in kinematic data structures, this paper sets a new direction of research, to study spanner maintenance under point motion.
