On Euclidean Steiner (1+ε)-Spanners
On Euclidean Steiner (1+ε)-Spanners
复制标题
论欧几里得斯坦纳 (1+ε)-扳手
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Csaba D. Tóth
中科院分区：
文献类型：
--
作者：
S. Bhore;Csaba D. Tóth
Lightness and sparsity are two natural parameters for Euclidean $(1+epsilon)$-spanners. Classical results show that, when the dimension $din mathbb{N}$ and $epsilon>0$ are constant, every set $S$ of $n$ points in $d$-space admits an $(1+epsilon)$-spanners with $O(n)$ edges and weight proportional to that of the Euclidean MST of $S$. Tight bounds on the dependence on $epsilon>0$ for constant $din mathbb{N}$ have been established only recently. Le and Solomon (FOCS 2019) showed that Steiner points can substantially improve the lightness and sparsity of a $(1+epsilon)$-spanner. They gave upper bounds of $ ilde{O}(epsilon^{-(d+1)/2})$ for the minimum lightness in dimensions $dgeq 3$, and $ ilde{O}(epsilon^{-(d-1))/2})$ for the minimum sparsity in $d$-space for all $dgeq 1$. They obtained lower bounds only in the plane ($d=2$). Le and Solomon (ESA 2020) also constructed Steiner $(1+epsilon)$-spanners of lightness $O(epsilon^{-1}logDelta)$ in the plane, where $Deltain Omega(log n)$ is the emph{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+epsilon)$-spanners. Using a new geometric analysis, we establish lower bounds of $Omega(epsilon^{-d/2})$ for the lightness and $Omega(epsilon^{-(d-1)/2})$ for the sparsity of such spanners in Euclidean $d$-space for all $dgeq 2$. We use the geometric insight from our lower bound analysis to construct Steiner $(1+epsilon)$-spanners of lightness $O(epsilon^{-1}log n)$ for $n$ points in Euclidean plane.
Lightness and sparsity are two natural parameters for Euclidean $(1+epsilon)$-spanners. Classical results show that, when the dimension $din mathbb{N}$ and $epsilon>0$ are constant, every set $S$ of $n$ points in $d$-space admits an $(1+epsilon)$-spanners with $O(n)$ edges and weight proportional to that of the Euclidean MST of $S$. Tight bounds on the dependence on $epsilon>0$ for constant $din mathbb{N}$ have been established only recently. Le and Solomon (FOCS 2019) showed that Steiner points can substantially improve the lightness and sparsity of a $(1+epsilon)$-spanner. They gave upper bounds of $ ilde{O}(epsilon^{-(d+1)/2})$ for the minimum lightness in dimensions $dgeq 3$, and $ ilde{O}(epsilon^{-(d-1))/2})$ for the minimum sparsity in $d$-space for all $dgeq 1$. They obtained lower bounds only in the plane ($d=2$). Le and Solomon (ESA 2020) also constructed Steiner $(1+epsilon)$-spanners of lightness $O(epsilon^{-1}logDelta)$ in the plane, where $Deltain Omega(log n)$ is the emph{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+epsilon)$-spanners. Using a new geometric analysis, we establish lower bounds of $Omega(epsilon^{-d/2})$ for the lightness and $Omega(epsilon^{-(d-1)/2})$ for the sparsity of such spanners in Euclidean $d$-space for all $dgeq 2$. We use the geometric insight from our lower bound analysis to construct Steiner $(1+epsilon)$-spanners of lightness $O(epsilon^{-1}log n)$ for $n$ points in Euclidean plane.