文章基本信息
- 标题：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
