Greedy spanners are optimal in doubling metrics

12/13/2017

∙

by   Glencora Borradaile, et al.

∙

0

∙

share

We show that the greedy spanner algorithm constructs a (1+ϵ)-spanner of weight ϵ^-O(d)w(MST) 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(MST). Our proof only uses the packing property of doubling metrics and thus implies a much simpler proof for the same result in Euclidean space.