Abstract
The FOCS'19 paper of Le and Solomon [Hung Le and Shay Solomon, 2019], culminating a long line of research on Euclidean spanners, proves that the lightness (normalized weight) of the greedy (1+ε)spanner in ℝ^d is Õ(ε^{d}) for any d = O(1) and any ε = Ω(n^{1/(d1)}) (where Õ hides polylogarithmic factors of 1/ε), and also shows the existence of point sets in ℝ^d for which any (1+ε)spanner must have lightness Ω(ε^{d}). Given this tight bound on the lightness, a natural arising question is whether a better lightness bound can be achieved using Steiner points.
Our first result is a construction of Steiner spanners in ℝ² with lightness O(ε^{1} log Δ), where Δ is the spread of the point set. In the regime of Δ ≪ 2^(1/ε), this provides an improvement over the lightness bound of [Hung Le and Shay Solomon, 2019]; this regime of parameters is of practical interest, as point sets arising in reallife applications (e.g., for various random distributions) have polynomially bounded spread, while in spanner applications ε often controls the precision, and it sometimes needs to be much smaller than O(1/log n). Moreover, for spread polynomially bounded in 1/ε, this upper bound provides a quadratic improvement over the nonSteiner bound of [Hung Le and Shay Solomon, 2019], We then demonstrate that such a light spanner can be constructed in O_ε(n) time for polynomially bounded spread, where O_ε hides a factor of poly(1/(ε)). Finally, we extend the construction to higher dimensions, proving a lightness upper bound of Õ(ε^{(d+1)/2} + ε^{2} log Δ) for any 3 ≤ d = O(1) and any ε = Ω(n^{1/(d1)}).
BibTeX  Entry
@InProceedings{le_et_al:LIPIcs:2020:12933,
author = {Hung Le and Shay Solomon},
title = {{Light Euclidean Spanners with Steiner Points}},
booktitle = {28th Annual European Symposium on Algorithms (ESA 2020)},
pages = {67:167:22},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771627},
ISSN = {18688969},
year = {2020},
volume = {173},
editor = {Fabrizio Grandoni and Grzegorz Herman and Peter Sanders},
publisher = {Schloss DagstuhlLeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/12933},
URN = {urn:nbn:de:0030drops129331},
doi = {10.4230/LIPIcs.ESA.2020.67},
annote = {Keywords: Euclidean spanners, Steiner spanners, light spanners}
}
Keywords: 

Euclidean spanners, Steiner spanners, light spanners 
Collection: 

28th Annual European Symposium on Algorithms (ESA 2020) 
Issue Date: 

2020 
Date of publication: 

26.08.2020 