A Framework for Computing the Greedy Spanner
Quirijn W. Bouts, Alex P. ten Brink, Kevin Buchin · 2014
The highest quality geometric spanner (e.g. in terms of edge count, both in theory and in practice) known to be computable in polynomial time is the greedy spanner. The state-of-the-art in computing this spanner are a O(n2 log n) time, O(n2) space algorithm and a O(n2 log2 n) time, O(n) space algorithm, as well as the 'improved greedy' algorithm, taking O(n3 log n) time in the worst case and O(n2) space but being faster in practice thanks to a caching strategy.