2020/07/22 by Le, Hung, Solomon, Shay
#Computational Geometry (cs.CG) #F.2.2 #FOS: Computer and information sciences
paper · doi:10.48550/arxiv.2007.11636
The FOCS'19 paper of Le and Solomon, culminating a long line of research on Euclidean spanners, proves that the lightness (normalized weight) of the greedy (1+ε)-spanner in ℝd is O(ε-d) for any d = O(1) and any ε= Ω(n-(1)/(d-1)) (where O hides polylogarithmic factors of \frac1ε), 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 ℝ2 with lightness O(ε-1 log Δ), where Δ is the spread of the point set. In the regime of Δ≪ 21/ε, this provides an improvement over the lightness bound of Le and Solomon [FOCS 2019]; this regime of parameters is of practical interest, as point sets arising in real-life 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 non-Steiner bound of Le and Solomon [FOCS 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(\frac1ε). Finally, we extend the construction to higher dimensions, proving a lightness upper bound of O(ε-(d+1)/2 + ε-2log Δ) for any 3≤ d = O(1) and any ε= Ω(n-(1)/(d-1)).