Efficient construction of a bounded-degree spanner with low weight

LetS be a set ofn points in ℝ ^d and lett>1 be a real number. At-spanner forS is a graph having the points ofS as its vertices such that for any pairp, q of points there is a path between them of length at mostt times the Euclidean distance betweenp andq. An efficient implementation of a greedy algorithm is given that constructs at-spanner having bounded degree such that the total length of all its edges is bounded byO (logn) times the length of a minimum spanning tree forS. The algorithm has running timeO (n log ^d n). Applying recent results of Das, Narasimhan, and Salowe to thist-spanner gives anO(n log ^d n)-time algorithm for constructing at-spanner having bounded degree and whose total edge length is proportional to the length of a minimum spanning tree forS. Previously, noo(n ²)-time algorithms were known for constructing at-spanner of bounded degree. In the final part of the paper, an application to the problem of distance enumeration is given. This work was supported by the ESPRIT Basic Research Actions Program, under Contract No. 7141 (Project ALCOM II).