文章基本信息

标题：Light Euclidean Steiner Spanners in the Plane
本地全文：下载
作者：Bhore, Sujoy ; T'{o}th, Csaba D.
期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
电子版ISSN：1868-8969
出版年度：2021
卷号：189
页码：15:1-15:17
DOI：10.4230/LIPIcs.SoCG.2021.15
出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
摘要：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 Î" â¥ Î©(â^Sn) 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 OÌf(Îµ^{-(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.
关键词：Geometric spanner; lightness; minimum weight