论文标题
在飞机上轻的欧几里得施罐
Light Euclidean Steiner Spanners in the Plane
论文作者
论文摘要
轻度是欧几里得跨越的基本参数；它是扳手的重量与$ \ mathbb {r}^d $中有限点的最小跨度树的重量。在最近的突破中，Le and Solomon（2019）确立了$ \ varepsilon> 0 $和$ d \ in \ mathbb {n} $的精确依赖性，最低$（1+ \ varepsilon）$的$（1+ \ varepsilon）$ - 跨度，并观察到附加的stoiner点可以大大提高光线。 Le and Solomon (2020) constructed Steiner $(1+\varepsilon)$-spanners of lightness $O(\varepsilon^{-1}\logΔ)$ in the plane, where $Δ\geq Ω(\sqrt{n})$ is the \emph{spread} of the point set, defined as the ratio between the maximum and minimum distance between a pair of点。他们还构建了轻度$ \ tilde {o}（\ varepsilon^{ - （d+1）/2}）$ n dimensions $ d \ geq 3 $。最近，Bhore andTóth（2020）建立了$ω（\ varepsilon^{ - d/2}）$的下限，用于Steiner $（1+ \ varepsilon）$ - $ \ Mathbb {r}^d $的轻度（1+ \ varepsilon）$ - 用于$ d \ ge ge 2 $。该区域中的中心开放问题是在所有维度上缩小上下边界之间的差距$ d \ geq 2 $。 在这项工作中，我们表明，对于飞机中的每一组有限的积分，每一个$ \ varepsilon> 0 $，都存在着欧几里得施泰纳$（1+ \ varepsilon）$ - 轻度$ o（\ varepsilon^{ - 1}）$ spanner这与$ d = 2 $的下限匹配。我们概括了可能具有独立感兴趣的浅灯树的概念，并使用定向跨度和修改后的窗户划分方案来实现严格的重量分析。
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 $\mathbb{R}^d$. In a recent breakthrough, Le and Solomon (2019) established the precise dependencies on $\varepsilon>0$ and $d\in \mathbb{N}$ of the minimum lightness of $(1+\varepsilon)$-spanners, and observed that additional Steiner points can substantially improve the lightness. Le and Solomon (2020) constructed Steiner $(1+\varepsilon)$-spanners of lightness $O(\varepsilon^{-1}\logΔ)$ in the plane, where $Δ\geq Ω(\sqrt{n})$ is the \emph{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 $\tilde{O}(\varepsilon^{-(d+1)/2})$ in dimensions $d\geq 3$. Recently, Bhore and Tóth (2020) established a lower bound of $Ω(\varepsilon^{-d/2})$ for the lightness of Steiner $(1+\varepsilon)$-spanners in $\mathbb{R}^d$, for $d\ge 2$. The central open problem in this area is to close the gap between the lower and upper bounds in all dimensions $d\geq 2$. In this work, we show that for every finite set of points in the plane and every $\varepsilon>0$, there exists a Euclidean Steiner $(1+\varepsilon)$-spanner of lightness $O(\varepsilon^{-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.
