Optimal Euclidean Spanners

DOI10.1145/2819008zbMATH Open1426.68271arXiv1207.1831OpenAlexW2264984242MaRDI QIDQ3177744FDOQ3177744

Michael Elkin, Shay Solomon

Publication date: 2 August 2018

Published in: Journal of the ACM (Search for Journal in Brave)

Abstract: 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(logn)$, and weight $O(lo{g}^{2}n)cdotomega(MST)$, and has running time $O(ncdotlogn)$. 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(logn)cdotomega(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.

Full work available at URL: https://arxiv.org/abs/1207.1831

zbMATH Keywords

Euclidean spacesdoubling metricsEuclidean spanners

Mathematics Subject Classification ID

Computer graphics; computational geometry (digital and algorithmic aspects) (68U05)

Cited In (13)

• Near Isometric Terminal Embeddings for Doubling Metrics
• Graph spanners: a tutorial review
• Shortest-Path Queries in Geometric Networks
• Minimum weight Euclidean \((1+\varepsilon)\)-spanners
• Title not available (Why is that?)
• Sparse Euclidean Spanners with Tiny Diameter
• The Greedy Spanner Is Existentially Optimal
• Truly Optimal Euclidean Spanners
• Minimum weight Euclidean \((1+\varepsilon)\)-spanners
• Near isometric terminal embeddings for doubling metrics
• A unified framework for light spanners
• Light Euclidean Spanners with Steiner Points
• Title not available (Why is that?)

   Recommendations

• Optimal euclidean spanners 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Sparse Euclidean Spanners with Tiny Diameter 👍 👎
• Minimum weight Euclidean \((1+\varepsilon)\)-spanners 👍 👎
• Euclidean Spanners in High Dimensions 👍 👎
• Euclidean Steiner Spanners: Light and Sparse 👍 👎
• Lower bound for sparse Euclidean spanners 👍 👎
• Euclidean distortion and the sparsest cut 👍 👎

This page was built for publication: Optimal Euclidean Spanners

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3177744)