A Light Metric Spanner
Lee-Ad J. Gottlieb · 2015
It has long been known that d-dimensional Euclidean point sets admit (1+ε)-stretch spanners with lightness WE= ε-O(d), that is the total edge weight is at most WE times the weight of the minimum spanning tree of the set [DHN93]. Whether or not a similar result holds for metric spaces with low doubling dimension has remained an open problem. In this paper, we resolve the question in the affirmative, and show that doubling spaces admit(1 + ε)-stretch spanners with lightness WD = (ddim /ε)O(ddim).