论文标题
在Euclidean Steiner $（1+ε）$ - 跨度
On Euclidean Steiner $(1+ε)$-Spanners
论文作者
论文摘要
轻度和稀疏性是欧几里得$（1+ \ varepsilon）$ spanners的两个自然参数。经典结果表明，当尺寸$ d \ in \ mathbb {n} $和$ \ varepsilon> 0 $是常数时，每个集合$ n $ s $ s $ s $的$ n $点都在$ d $ space中承认$（1+\ varepsilon）$ - 带有$ o（n）$ edges $ edges and Iffectional of thit ocuclidean of ecuclidean mst的$（n）$ edges和权重。 \ varepsilon> 0 $的依赖性的紧密界限仅在最近才建立。 Le and Solomon（Focs 2019）表明，Steiner点可以大大改善$（1+ \ Varepsilon）$ spanner的轻度和稀疏性。他们给出了$ \ tilde {o}（\ varepsilon^{ - （d+1）/2}）$，用于尺寸的最小轻度$ d \ geq 3 $，和$ \ tilde {o} {o}（\ varepsilon^{ - （d-1））/$ d $ d $ d $ d $ d $ d $ d $ d $ d- 1 $。他们仅在飞机上获得下限（$ d = 2 $）。 Le and Solomon（ESA 2020）还构建了steiner $（1+ \ varepsilon）$ - 轻度$ o（\ varepsilon^{ - 1} \logΔ）$在ω（$Δ\ inω（\ sqrt {n}）中，$Δ\ in $Δ要点。 在这项工作中，我们提高了欧几里得史坦纳$（1+ \ varepsilon）$ - 跨度的少量和稀疏性的几个范围。使用新的几何分析，我们为轻度建立了$ω（\ varepsilon^{ - d/2}）$的$ω（\ varepsilon^{ - （d-1）/2}）$，以供euclidean $ d $ -s-space for All $ d $ d $ d \ geq Quq 2 $。我们使用从下限分析中的几何见解来构造steiner $（1+ \ varepsilon）$ - 轻度$ o（\ varepsilon^{ - 1} \ log n）$的轻度跨度。
Lightness and sparsity are two natural parameters for Euclidean $(1+\varepsilon)$-spanners. Classical results show that, when the dimension $d\in \mathbb{N}$ and $\varepsilon>0$ are constant, every set $S$ of $n$ points in $d$-space admits an $(1+\varepsilon)$-spanners with $O(n)$ edges and weight proportional to that of the Euclidean MST of $S$. Tight bounds on the dependence on $\varepsilon>0$ for constant $d\in \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+\varepsilon)$-spanner. They gave upper bounds of $\tilde{O}(\varepsilon^{-(d+1)/2})$ for the minimum lightness in dimensions $d\geq 3$, and $\tilde{O}(\varepsilon^{-(d-1))/2})$ for the minimum sparsity in $d$-space for all $d\geq 1$. They obtained lower bounds only in the plane ($d=2$). Le and Solomon (ESA 2020) also constructed Steiner $(1+\varepsilon)$-spanners of lightness $O(\varepsilon^{-1}\logΔ)$ in the plane, where $Δ\in Ω(\sqrt{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+\varepsilon)$-spanners. Using a new geometric analysis, we establish lower bounds of $Ω(\varepsilon^{-d/2})$ for the lightness and $Ω(\varepsilon^{-(d-1)/2})$ for the sparsity of such spanners in Euclidean $d$-space for all $d\geq 2$. We use the geometric insight from our lower bound analysis to construct Steiner $(1+\varepsilon)$-spanners of lightness $O(\varepsilon^{-1}\log n)$ for $n$ points in Euclidean plane.
