A fast algorithm for constructing sparse Euclidean spanners

ABSTRACT

Let G=(V,E) be a n-vertex connected graph with positive edge weights. A subgraph G′ is a t-spanner if for all u,v ∈ V, the distance between u and v in the subgraph is at most t times the corresponding distance in G. We design an O(nlog2n) time algorithm which, given a set V of n points in k-dimensional space, and any constant t>1, produces a t-spanner of the complete Euclidean graph of V. This algorithm retains the spirit of a recent O(n3logn)-time greedy algorithm which produces t-spanners with a small number of edges and a small total edge weight; we use graph clustering techniques to achieve a more efficient implementation. Our spanners have similar size and weight sparseness as those constructed by the greedy algorithm.

REFERENCES

• 1: Ingo Althöfer , Gautam Das , David Dobkin , Deborah Joseph , José Soares, On sparse spanners of weighted graphs, Discrete & Computational Geometry, v.9 n.1, p.81-100, 1993 [doi>10.1007/BF02189308]
• 2: B. Awerbuch, D. Peleg: Sparse Partitions: IEEE Foundations of Computer Science, 1993.
• 3: E. Cohen: Fast Algorithms for Constructing t- Spanners and Paths with Stretch t: IEEE Foundations of Computer Science, 1993.
• 4: B. Chandra, G. Das, G. Narasimhan, J. Scares: New Sparseness Results on Graph Spanners: to appear in International Journal of Computational Geometry and Applications.
• 5: Gautam Das , Paul Heffernan , Giri Narasimhan, Optimally sparse spanners in 3-dimensional Euclidean space, Proceedings of the ninth annual symposium on Computational geometry, p.53-62, May 18-21, 1993, San Diego, California, United States [doi>10.1145/160985.160998]
• 6: Gautam Das , Paul J. Heffernan, Constructing Degree-3 Spanners with Other Sparseness Properties, Proceedings of the 4th International Symposium on Algorithms and Computation, p.11-20, December 15-17, 1993
• 7: C. Levcopoulos , A. Lingas, There are planar graphs almost as good as the complete graphs and as short as minimum spanning trees (invited), Proceedings of the international symposium on Optimal algorithms, p.9-13, November 1989, Varna, Bulgaria
• 8: Jeffrey S. Salowe, Construction of multidimensional spanner graphs, with applications to minimum spanning trees, Proceedings of the seventh annual symposium on Computational geometry, p.256-261, June 10-12, 1991, North Conway, New Hampshire, United States [doi>10.1145/109648.109677]
• 9: Jose Augusto Ramos Soares, Graph spanners, 1992
• 10: Pravin M. Vaidya, A sparse graph almost as good as the complete graph on points in K dimensions, Discrete & Computational Geometry, v.6 n.4, p.369-381, 1991 [doi>10.1007/BF02574695]

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Geometrical problems and computations

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Computations on discrete structures

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS
      G.2.2 Graph Theory
          Subjects: Graph algorithms

General Terms:
Algorithms, Theory, Verification