An O(n log n)-time algorithm is presented that, when given a set S of n points in R{double-struck} d 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.

Additional Metadata
Keywords Computational geometry, Minimum spanning trees, Spanners
Conference Theory of Computing 2006 - 12th Computing: The Australasian Theory Symposium, CATS 2006
Citation
Smid, M. (2006). Geometric spanners with few edges and degree five. Presented at the Theory of Computing 2006 - 12th Computing: The Australasian Theory Symposium, CATS 2006.