×

Constructing plane spanners of bounded degree and low weight. (English) Zbl 1086.68136

Summary: 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 \approx 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.

MSC:

68U05 Computer graphics; computational geometry (digital and algorithmic aspects)
68R10 Graph theory (including graph drawing) in computer science
Full Text: DOI