Improved algorithms for fully dynamic geometric spanners and geometric routing

Lee-Ad Gottlieb, Liam RodittySODA 2008 · OpenReview

Abstract

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(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(log2 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 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(log3 n).
BibTeX
@inproceedings{gottlieb2008improved,
  author = {Lee-Ad Gottlieb and Liam Roditty},
  title = {{Improved algorithms for fully dynamic geometric spanners and geometric routing}},
  booktitle = {SODA},
  year = {2008},
  url = {https://openreview.net/forum?id=y9rg59GI0e3},
}

Loading related content...

Figure