2012/07/07 by Michael Elkin, Elkin, Michael, Shay Solomon +1 · 4 citations
Computer Science · Engineering · #Advanced Numerical Analysis Techniques #Computational Geometry and Mesh Generation #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences
paper · pdf · doi:10.48550/arxiv.1207.1831
openalex publication_date 2012/07/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In a seminal STOC'95 paper, titled "Euclidean spanners: short, thin and lanky", Arya et al. devised a construction of Euclidean (1+\eps)-spanners that achieves constant degree, diameter O(log n), and weight O(log2 n) ⋅ ω(MST), and has running time O(n ⋅ log n). This construction applies to n-point constant-dimensional Euclidean spaces. Moreover, Arya et al. conjectured that the weight bound can be improved by a logarithmic factor, without increasing the degree and the diameter of the spanner, and within the same running time. This conjecture of Arya et al. became a central open problem in the area of Euclidean spanners. In this paper we resolve the long-standing conjecture of Arya et al. in the affirmative. Specifically, we present a construction of spanners with the same stretch, degree, diameter, and running time, as in Arya et al.'s result, but with optimal weight O(log n) ⋅ ω(MST). Moreover, our result is more general in three ways. First, we demonstrate that the conjecture holds true not only in constant-dimensional Euclidean spaces, but also in doubling metrics. Second, we provide a general tradeoff between the three involved parameters, which is tight in the entire range. Third, we devise a transformation that decreases the lightness of spanners in general metrics, while keeping all their other parameters in check. Our main result is obtained as a corollary of this transformation.