For a set $S$ of points in $\reals^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. We propose a new sparse $(1+\eps)$-spanner with $O(n/\eps^d)$ edges, where $\eps$ is a specified parameter. The key property of this spanner is that it can be efficiently maintained under dynamic insertion or deletion of points, as well as under continuous motion of the points. Our deformable spanner succinctly encodes all proximity information in a deforming point cloud, giving us efficient 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.
The spanner can also be implemented in distributed fashion for maintaining proximity information among communicating mobile nodes. The communicating mobile nodes can be vehicles (cars, airplanes), people carrying cell phones, or nodes in any type of mobile ad hoc network. Our distributed data structure allows each node to quickly know which other nodes are within a given distance of itself, while requiring very modest communication with only a small number of other nodes. The structure only uses distance information between communicating nodes that can be derived using ranging or localization methods, and requires no additional shared infrastructure. Its modest requirements make it scalable to large numbers of nodes.
Copyright. All Rights Reserved.