Optimal Euclidean Spanners

DOI10.1145/2819008MaRDI QIDQ3177744zbMATH OpenOpenAlexFDO

Authors Michael Elkin, Shay Solomon

Publication date 2 August 2018

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

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)

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.

Recommendations

• Optimal Euclidean spanners, really short, thin and lanky
• scientific article; zbMATH DE number 1263225
• An optimal-time construction of sparse Euclidean spanners with tiny diameter
• 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

Cited in

(20)

• scientific article; zbMATH DE number 910877 (Why is no real title available?)
• Graph spanners: a tutorial review
• Shortest-Path Queries in Geometric Networks
• An optimal-time construction of sparse Euclidean spanners with tiny diameter
• Low-light trees, and tight lower bounds for Euclidean spanners
• Euclidean Steiner spanners: light and sparse
• Minimum weight Euclidean \((1+\varepsilon)\)-spanners
• scientific article; zbMATH DE number 1263225 (Why is no real title available?)
• Sparse Euclidean Spanners with Tiny Diameter
• Truly Optimal Euclidean Spanners
• Sparse Euclidean spanners with optimal diameter: a general and robust lower bound via a concave inverse-Ackermann function
• Minimum weight Euclidean \((1+\varepsilon)\)-spanners
• Near isometric terminal embeddings for doubling metrics
• Near isometric terminal embeddings for doubling metrics
• Light spanners for snowflake metrics
• A unified framework for light spanners
• Light Euclidean Spanners with Steiner Points
• The greedy spanner is existentially optimal
• Optimal Euclidean spanners, really short, thin and lanky
• Euclidean spanners in high dimensions

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)