Euclidean Steiner shallow-light trees - Shay Solomon (Journal of Computational Geometry, 2015)
$\newcommand{\eps}{ε}$A spanning tree that simultaneously approximates a shortest-path tree and a minimum spanning tree is called a shallow-light tree (shortly, SLT). More specifically, an $(α,β)$-SLT of a weighted undirected graph $G = (V,E,w)$ with respect to a designated vertex $rt\in V$ is a spanning tree of $G$ with: (1) root-stretch $α$ – it preserves all distances between $rt$ and the other vertices up to a factor of $α$, and (2) lightness $β$ – it has weight at most $β$ times the weight of a minimum spanning tree $MST(G)$ of $G$. Tight tradeoffs between the parameters of SLTs were established by Awerbuch et al. in PODC'90 and by Khuller et al. in SODA'93. They showed that for any $\eps > 0$, any graph admits a $(1+\eps,O(\frac{1}{\eps}))$-SLT with respect to any root vertex, and complemented this result with a matching lower bound. Khuller et al. asked if the upper bound $β = O(\frac{1}{\eps})$ on the lightness of SLTs can be improved in Euclidean spaces. In FOCS'11 Elkin and this author gave a negative answer to this question, showing a lower bound of $β = Ω(\frac{1}{\eps})$ that applies to 2-dimensional Euclidean spaces. In this paper we show that Steiner points lead to a quadratic improvement in Euclidean SLTs, by presenting a construction of Euclidean Steiner $(1+\eps,O(\sqrt{\frac{1}{\eps})})$-SLTs in arbitrary 2-dimensional Euclidean spaces. The lightness bound $β = O(\sqrt{\frac{1}{\eps}})$ of our construction is optimal up to a constant. The runtime of our construction, and thus the number of Steiner points used, are bounded by $O(n)$.