Greedy spanners are optimal in doubling metrics

Glencora Borradaile, Hung Le, Christian Wulff-Nilsen

We show that the greedy spanner algorithm constructs a $(1+\epsilon )$-spanner of weight ${\epsilon }^{-O(d)}w(\mathrm{MST})$ for a point set in metrics of doubling dimension $d$, resolving an open…