Light spanners for Snowflake Metrics
Lee-Ad J. Gottlieb, Shay Solomon · 2014
A classic result in the study of spanners is the existence of light low-stretch spanners for Euclidean spaces. These spanners have arbitrary low stretch, and weight only a constant factor greater than that of the minimum spanning tree of the points (with dependence on the stretch and Euclidean dimension). A central open problem in this field asks whether other spaces admit low weight spanners as well -- for example metric space with low intrinsic dimension -- yet only a handful of results of this type are known.