Improved algorithms for fully dynamic geometric spanners and geometric routing

For a set S of points in ℝ ^d a t-spanner is a sparse graph on the points of S such that between any pair of points there is a path in the spanner whose total length is at most t times the Euclidean distance between the points. In this paper, we show how to construct a (1 +ε)-spanner with O(n/ε ^d) edges and maximum degree O(l/ε ^d) in time O(n log n). A spanner with similar properties was previously presented in [6, 8]. However, using our new construction (coupled with several other innovations) we obtain new results for two fundamental problems for constant doubling dimension metrics: The first result is an essentially optimal compact routing scheme. In particular, we show how to perform routing with a stretch of 1 + ε, where the label size is [log n] and the size of the table stored at each point is only O(log n/ε ^d). This routing problem was first considered by Peleg and Hassin [11], who presented a routing scheme in the plane. Later, Chan et al. [6] and Abraham et al. [1] considered this problem for doubling dimension metric spaces. Abraham et al. [1] were the first to present a (1 + ε) routing scheme where the label size depends solely on the number of points. In their scheme labels are of size of [log n], and each point stores a table of size O(log ² n/ε ^d). In our routing scheme, we achieve routing tables of size O(log n/ε ^d), which is essentially the same size as a label (up to the factor of l/ε ^d). The second and main result of this paper is the first fully dynamic geometric spanner with poly-logarithmic update time for both insertions and deletions. We present an algorithm that allows points to be inserted into and deleted from S with an amortized update time of O(log ³ n).