2026-07-23T22:19:41Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:13814 2024-03-06T10:52:47Z ddc:004 open_access

Light Euclidean Steiner Spanners in the Plane Bhore, Sujoy Tóth, Csaba D. Geometric spanner lightness minimum weight Lightness is a fundamental parameter for Euclidean spanners; it is the ratio of the spanner weight to the weight of the minimum spanning tree of a finite set of points in ℝ^d. In a recent breakthrough, Le and Solomon (2019) established the precise dependencies on ε > 0 and d ∈ ℕ of the minimum lightness of a (1+ε)-spanner, and observed that additional Steiner points can substantially improve the lightness. Le and Solomon (2020) constructed Steiner (1+ε)-spanners of lightness O(ε^{-1}logΔ) in the plane, where Δ ≥ Ω(√n) is the spread of the point set, defined as the ratio between the maximum and minimum distance between a pair of points. They also constructed spanners of lightness Õ(ε^{-(d+1)/2}) in dimensions d ≥ 3. Recently, Bhore and Tóth (2020) established a lower bound of Ω(ε^{-d/2}) for the lightness of Steiner (1+ε)-spanners in ℝ^d, for d ≥ 2. The central open problem in this area is to close the gap between the lower and upper bounds in all dimensions d ≥ 2. In this work, we show that for every finite set of points in the plane and every ε > 0, there exists a Euclidean Steiner (1+ε)-spanner of lightness O(ε^{-1}); this matches the lower bound for d = 2. We generalize the notion of shallow light trees, which may be of independent interest, and use directional spanners and a modified window partitioning scheme to achieve a tight weight analysis. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Sujoy Bhore and Csaba D. Tóth 2021 Is Part Of LIPIcs, Volume 189, 37th International Symposium on Computational Geometry (SoCG 2021) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SoCG.2021.15 urn:nbn:de:0030-drops-138145 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SoCG.2021.15 eng https://creativecommons.org/licenses/by/4.0/legalcode