2014/01/20 by Lee-Ad Gottlieb, Gottlieb, Lee-Ad, Shay Solomon +1
Computer Science · #Advanced Graph Theory Research #Computational Geometry (cs.CG) #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.1401.5014
openalex publication_date 2014/01/20 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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