文章基本信息

标题：Light Euclidean Spanners with Steiner Points
本地全文：下载
作者：Hung Le ; Shay Solomon
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2020
卷号：173
页码：67:1-67:22
DOI：10.4230/LIPIcs.ESA.2020.67
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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 OÌf(Îµ^{-d}) for any d = O(1) and any Îµ = Î©(n^{-1/(d-1)}) (where OÌf 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 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 [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 OÌf(Îµ^{-(d+1)/2} + Îµ^{-2} log Î") for any 3 â¤ d = O(1) and any Îµ = Î©(n^{-1/(d-1)}).
关键词：Euclidean spanners; Steiner spanners; light spanners