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 |