Efficient construction of a bounded degree spanner with low weight

Let S be a set of n points in ℝd and let t>1 be a real number. A t-spanner for S is a graph having the points of S as its vertices such that for any pair p, q of points there is a path between them of length at most t times the Euclidean distance between p and q. An efficient implementation of a greedy algorithm is given that constructs a t-spanner having bounded degree such that the total length of all its edges is bounded by O(log n) times the length of a minimum spanning tree for S. The algorithm has running time O(n logd n). Applying recent results of Das, Narasimhan and Salowe to this t-spanner gives an O(n logd n) time algorithm for constructing a t-spanner having bounded degree and whose total edge length is proportional to the length of a minimum spanning tree for S. Previously, no o(n 2) time algorithms were known for constructing a t-spanner of bounded degree. In the final part of the paper, an application to the problem of distance enumeration is given.Let S be a set of n points in R(d) and let t > 1 be a real number. A t-spanner for S is a graph having the points of S as its vertices such that for any pair p, q of points there is a path between them of length at most t times the Euclidean distance between p and q. An efficient implementation of a greedy algorithm is given that constructs a t-spanner having bounded degree such that the total length of all its edges is bounded by O (log n) times the length of a minimum spanning tree for S. The algorithm has running time O (n log(d) n). Applying recent results of Das, Narasimhan, and Salowe to this t-spanner gives an O(n log(d) n)-time algorithm for constructing a t-spanner having bounded degree and whose total edge length is proportional to the length of a minimum spanning tree for S. Previously, no o(n(2))-time algorithms were known for constructing a t-spanner of bounded degree. In the final part of the paper, an application to the problem of distance enumeration is given