Greedy spanners are optimal in doubling metrics

We show that the greedy spanner algorithm constructs a $(1+ϵ)$-spanner of weight ${ϵ}^{-O(d)}w(\mathrm{M}\mathrm{S}\mathrm{T})$ for a point set in metrics of doubling dimension $d$, resolving an open problem posed by Gottlieb. Our result generalizes the result by Narasimhan and Smid who showed that a point set in $d$-dimension Euclidean space has a $(1+ϵ)$-spanner of weight at most ${ϵ}^{-O(d)}w(\mathrm{M}\mathrm{S}\mathrm{T})$. Our proof only uses the packing property of doubling metrics and thus implies a much simpler proof for the same result in Euclidean space.