EFFICIENT CONSTRUCTION OF A BOUNDED-DEGREE SPANNER WITH LOW-WEIGHT

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 lengt h at most t times the Euclidean distance between p and q. An efficient implementation of a greedy algorithm is given that constructs a t-spa nner 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 f or S. The algorithm has running time O (n log(d) n). Applying recent r esults of Das, Narasimhan, and Salowe to this t-spanner gives an O(n l og(d) n)-time algorithm for constructing a t-spanner having bounded de gree and whose total edge length is proportional to the length of a mi nimum spanning tree for S. Previously, no o(n(2))-time algorithms were known for constructing a t-spanner of bounded degree. In the final pa rt of the paper, an application to the problem of distance enumeration is given.