# Light spanners for snowflake metrics

arXiv: https://arxiv.org/abs/1401.5014 · HTML: https://mlsanity.com/paper/1401.5014/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Jan 2014.

## Built on by (most cited first, 1 of 1)

- [Fully Geometric Panoramic Localization](https://mlsanity.com/paper/2403.19904/) (2024)

## Abstract (arXiv)

A classic result in the study of spanners is the existence of light low-stretch spanners for Euclidean spaces. These spanners ahve 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 dimention). 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. In this paper, we consider snowflake metric spaces of low intrinsic dimension. The α-snowflake of a metric (X,δ) is the metric (X,δα) for 0<α<1. By utilizing an approach completely different than those used for Euclidean spaces, we demonstrate that snowflake metrics admit light spanners. Further, we show that the spanner is of diameter O(logn), a result not possible for Euclidean spaces. As an immediate corollary to our spanner, we obtain dramatic improvments in algorithms for the traveling salesman problem in this setting, achieving a polynomial-time approximation scheme with near-linear runtime. Along the way, we show that all ℓp spaces admit light spanners, a result of interest in its own right.