Geometric spanners with few edges and degree five
Michiel Smid · Computing: The Australasian Theory Symposium · 2006
An O(n log n)-time algorithm is presented that, when given a set S of n points in Rd and an integer k with 0 ≤ k ≤ n, computes a graph with vertex set S, that contains at most n - 1 + k edges, has stretch factor O(n/(k+1), and whose degree is at most five. This generalizes a recent result of Aronov et al., who obtained this result for two-dimensional point sets.