Given a set S of n points in the plane, we give an O(n log n)-time algorithm that constructs a plane t-spanner for S, with t ≈ 10, such that the degree of each point of S is bounded from above by 27, and the total edge length is proportional to the weight of a minimum spanning tree of S. Previously, no algorithms were known for constructing plane t-spanners of bounded degree.

, , , ,
Computational Geometry Lab

Bose, P, Gudmundsson, J. (Joachim), & Smid, M. (2005). Constructing plane spanners of bounded degree and low weight. In Algorithmica (Vol. 42, pp. 249–264). doi:10.1007/s00453-005-1168-8