Improved algorithms for fully dynamic geometric spanners and geometric routing
Lee-Ad J. Gottlieb, Liam Roditty · 2008
For a set S of points in R 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(1/ε 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 2 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 1/ε d). The second and main result of this paper is the first fully dynamic geometric spanner with polylogarithmic 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 3 n).