Abstract
Lightness and sparsity are two natural parameters for Euclidean (1+ε)spanners. Classical results show that, when the dimension d ∈ ℕ and ε > 0 are constant, every set S of n points in dspace admits an (1+ε)spanners with O(n) edges and weight proportional to that of the Euclidean MST of S. Tight bounds on the dependence on ε > 0 for constant d ∈ ℕ have been established only recently. Le and Solomon (FOCS 2019) showed that Steiner points can substantially improve the lightness and sparsity of a (1+ε)spanner. They gave upper bounds of Õ(ε^{(d+1)/2}) for the minimum lightness in dimensions d ≥ 3, and Õ(ε^{(d1))/2}) for the minimum sparsity in dspace for all d ≥ 1. They obtained lower bounds only in the plane (d = 2). Le and Solomon (ESA 2020) also constructed Steiner (1+ε)spanners of lightness O(ε^{1}logΔ) in the plane, where Δ ∈ Ω(log n) is the spread of S, defined as the ratio between the maximum and minimum distance between a pair of points.
In this work, we improve several bounds on the lightness and sparsity of Euclidean Steiner (1+ε)spanners. Using a new geometric analysis, we establish lower bounds of Ω(ε^{d/2}) for the lightness and Ω(ε^{(d1)/2}) for the sparsity of such spanners in Euclidean dspace for all d ≥ 2. We use the geometric insight from our lower bound analysis to construct Steiner (1+ε)spanners of lightness O(ε^{1}log n) for n points in Euclidean plane.
BibTeX  Entry
@InProceedings{bhore_et_al:LIPIcs.STACS.2021.13,
author = {Bhore, Sujoy and T\'{o}th, Csaba D.},
title = {{On Euclidean Steiner (1+\epsilon)Spanners}},
booktitle = {38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021)},
pages = {13:113:16},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771801},
ISSN = {18688969},
year = {2021},
volume = {187},
editor = {Bl\"{a}ser, Markus and Monmege, Benjamin},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2021/13658},
URN = {urn:nbn:de:0030drops136586},
doi = {10.4230/LIPIcs.STACS.2021.13},
annote = {Keywords: Geometric spanner, (1+\epsilon)spanner, lightness, sparsity, minimum weight}
}
Keywords: 

Geometric spanner, (1+ε)spanner, lightness, sparsity, minimum weight 
Collection: 

38th International Symposium on Theoretical Aspects of Computer Science (STACS 2021) 
Issue Date: 

2021 
Date of publication: 

10.03.2021 