文章基本信息
- 标题：On Euclidean Steiner (1 ε)-Spanners
- 本地全文：下载
- 作者：Bhore, Sujoy ; Csaba D. Tóth
- 期刊名称：LIPIcs : Leibniz International Proceedings in Informatics
- 电子版ISSN：1868-8969
- 出版年度：2021
- 卷号：187
- 页码：13:1-13:16
- DOI：10.4230/LIPIcs.STACS.2021.13
- 出版社：Schloss Dagstuhl -- Leibniz-Zentrum fuer Informatik
- 摘要：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 d-space 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 OÌf(ε^{-(d 1)/2}) for the minimum lightness in dimensions d ⥠3, and OÌf(ε^{-(d-1))/2}) for the minimum sparsity in d-space 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 Ω(ε^{-(d-1)/2}) for the sparsity of such spanners in Euclidean d-space 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.
- 关键词：Geometric spanner; (1 ε)-spanner; lightness; sparsity; minimum weight
扫一扫关注微信
国家哲学社会科学文献中心版权所有