Approximating Euclidean Shallow-Light Trees

Le, Hung; Solomon, Shay; Than, Cuong; Tóth, Csaba D.; Zhang, Tianyi

doi:10.4230/LIPIcs.SoCG.2026.71

Approximating Euclidean Shallow-Light Trees

Hung Le

University of Massachusetts Amherst, MA, USA Shay Solomon

Tel Aviv University, Israel Cuong Than

University of Massachusetts Amherst, MA, USA Csaba D. Tóth

California State University Northridge, Los Angeles, CA, USA
Tufts University, Medford, MA, USA Tianyi Zhang

State Key Laboratory for Novel Software Technology, Nanjing University, China

Abstract

For a weighted graph $G=(V,E,w)$ and a designated source vertex $s\in V$ , a spanning tree that simultaneously approximates a shortest-path tree w.r.t. source $s$ and a minimum spanning tree is called a shallow-light tree (SLT). Specifically, an $(\alpha,\beta)$ -SLT of $G$ w.r.t. $s\in V$ is a spanning tree of $G$ with root-stretch $\alpha$ (preserving all distances between $s$ and all other vertices up to a factor of $\alpha$ ) and lightness $\beta$ (its weight is at most $\beta$ times the weight of a minimum spanning tree of $G$ ).

It was shown in the early 1990s that (1) for any graph, any source, and any $\epsilon>0$ , there is a $(1+\epsilon,O(1/\epsilon))$ -SLT, and (2) there exist graphs for which $\beta=\Omega(1/\epsilon)$ for any $(1+\epsilon,\beta)$ -SLT.

The focus of this work is on SLTs in low-dimensional Euclidean spaces, which are of special interest for some applications of SLTs, in geometric network optimization problems. The aforementioned existential lower bound applies to Euclidean plane, as well. It was shown more than a decade ago that (1) by using Steiner points, one can reduce the lightness bound from $O(1/\epsilon)$ to $O(\sqrt{1/\epsilon})$ , and (2) there exist point sets in the plane for which $\beta=\Omega(\sqrt{1/\epsilon})$ for any Steiner $(1+\epsilon,\beta)$ -SLT.

These tight existential bounds for the Euclidean case yield approximation factors of $O(1/\epsilon)$ and $O(\sqrt{1/\epsilon})$ on the minimum weight of any non-Steiner and Steiner tree with root-stretch $1+\epsilon$ , respectively. Despite the large body of work on SLTs, the basic question of whether a better approximation algorithm exists was left untouched to date, and this holds in any graph family. This paper makes a first nontrivial step towards resolving this question by presenting two bicriteria approximation algorithms. For any $\epsilon>0$ , a set $P$ of $n$ points in constant-dimensional Euclidean space and a source $s\in P$ , our first (respectively, second) algorithm returns, in $O(n\log n\cdot{\rm polylog}(\epsilon^{-1}))$ time, a non-Steiner (resp., Steiner) tree with root-stretch $1+O(\epsilon\log\epsilon^{-1})$ and weight at most $O(\mathsf{opt}_{\epsilon}\cdot\log^{2}\epsilon^{-1})$ (resp., $O(\mathsf{opt}_{\epsilon}\cdot\log\epsilon^{-1})$ ), where $\mathsf{opt}_{\epsilon}$ denotes the minimum weight of a non-Steiner (resp., Steiner) tree with root-stretch $1+\epsilon$ .

Keywords and phrases:

geometric network design, optimization, shallow-light tree, Steiner point

Funding:

Hung Le: Supported by the NSF CAREER award CCF-2237288, the NSF grants CCF-2517033 and CCF-2121952, a Google Research Scholar Award.

Shay Solomon: Supported by the European Union (ERC, DynOpt, 101043159). Views and opinions expressed are however those of the author(s) only and do not necessarily reflect those of the European Union or the European Research Council. Neither the European Union nor the granting authority can be held responsible for them. Shay Solomon is also funded by a grant from the United States-Israel Binational Science Foundation (BSF), Jerusalem, Israel, and the United States National Science Foundation (NSF).

Cuong Than: Supported by the NSF CAREER award CCF-2237288, the NSF grants CCF-2517033 and CCF-2121952, a Google Research Scholar Award, and a Google Ph.D. Fellowship.

Csaba D. Tóth: Supported by the NSF award DMS-2154347.

Tianyi Zhang: Supported by Fundamental and Interdisciplinary Disciplines Breakthrough Plan of the Ministry of Education of China (No. JYB2025XDXM118) and the “111 Center” (No. B26023).

Copyright and License:

2012 ACM Subject Classification:

Theory of computation

\rightarrow

Sparsification and spanners ; Theory of computation

\rightarrow

Routing and network design problems ; Mathematics of computing

\rightarrow

Graph algorithms

Editors:

Hee-Kap Ahn, Michael Hoffmann, and Amir Nayyeri

Series and Publisher:

Leibniz International Proceedings in Informatics, Schloss Dagstuhl – Leibniz-Zentrum für Informatik

1 Introduction

A shortest-path tree (SPT) of an undirected edge-weighted $n$ -vertex graph $G=(V,E,\mathbf{w})$ with respect to a designated source or root vertex $s\in V$ , denoted by $\mathsf{SPT}(G,s)$ is a spanning tree $T$ rooted at $s$ that preserves all distances from $s$ , i.e., for every vertex $v\in V$ , the distance $d_{T}(s,v)$ between $s$ and $v$ in $T$ equals their distance $d_{G}(s,v)$ in $G$ . For a parameter $\alpha\geq 1$ , an $\alpha$ -shallow tree ( $\alpha$ -ST) is a spanning tree $T$ of $G$ of root-stretch at most $\alpha$ , i.e., for every $v\in V$ , $d_{T}(s,v)\leq\alpha\cdot d_{G}(s,v)$ . A minimum spanning tree (MST) of $G$ , denoted by $\mathsf{MST}(G)$ , is a spanning tree $T$ of $G$ of minimum weight. For a parameter $\beta\geq 1$ , a $\beta$ -light tree ( $\beta$ -LT) is a spanning tree $T$ of $G$ of lightness $\beta$ , i.e., $\mathbf{w}(T)\leq\beta\cdot\mathbf{w}(\mathsf{MST}(G))$ . The SPT and the MST, including their approximate versions, are among the most fundamental graph constructs and have been extensively studied over decades.

A single tree that simultaneously approximates the SPT and the MST is called a shallow-light tree (SLT). For a pair of parameters $\alpha,\beta\geq 1$ , a $(\alpha,\beta)$ -SLT of graph $G$ w.r.t. a designated source $s\in V$ is a spanning tree of $G$ that is both a $\alpha$ -ST and a $\beta$ -LT. The notion of SLTs was introduced in the pioneering works of Awerbuch et al. [2, 3] and Khuller et al. [18] (see also [8]). They showed that for every $\epsilon>0$ , a $(1+\epsilon,O(\frac{1}{\epsilon}))$ -SLT can be constructed in linear time for every graph $G$ if an SPT and an MST are given. Khuller et al. [18] also showed that this tradeoff is tight, by presenting a planar graph for which $\beta=\Omega(\frac{1}{\epsilon})$ for any $(1+\epsilon,\beta)$ -SLT.

The balance between the useful properties of an MST, which provides a light-weight network, and of an SPT, which provides short paths from a designated source to all other vertices, has led to a wide variety of applications across diverse domains. This includes applications in routing [1, 5, 16, 19, 21, 27, 32] and in network and VLSI-circuit design [7, 8, 14, 26], for data gathering and dissemination tasks in overlay networks [17, 20, 30], in the message-passing model of distributed computing [2, 3], and in wireless and sensor networks [31, 4, 9, 23, 22, 28]. Additionally, SLTs are used as building blocks in other related graph structures, such as light approximate routing trees [32], shallow-low-light trees [11, 12], light spanners [3, 25], and others [26, 23, 22]. In particular, in real-world applications, such as VLSI-design and wireless communication networks, the vertices are embedded in Euclidean space, and the edge weights correspond to the metric distances between the nodes.

Low-dimensional Euclidean spaces.

Khuller et al. [18] asked whether a better construction of SLTs can be achieved in Euclidean plane, which is the focus of this work. Euclidean space $\mathbb{R}^{d}$ , $d\geq 1$ , can be modeled as a complete edge-weighted graph $G=(V,E,\mathbf{w})$ induced by a finite set $P$ of points in $\mathbb{R}^{d}$ with $V=P$ , $E=\binom{P}{2}$ , and $\mathbf{w}=\|\cdot\|_{2}$ . Elkin and Solomon [13] showed that the upper bound of $(1+\epsilon,O(\frac{1}{\epsilon}))$ -SLTs in general graphs [2, 3, 18] is asymptotically tight even in Euclidean plane: For a set $C$ of $\lceil 1/\epsilon\rceil$ evenly spaced points on a circle, any $(1+\epsilon,\beta)$ -SLT for $C$ for any source $s\in C$ must have $\beta=\Omega(\frac{1}{\epsilon})$ . Solomon [29] showed that allowing Steiner points lead to substantial improvement in Euclidean plane: For every set $P\subset\mathbb{R}^{2}$ and source $s\in P$ , one can construct a Steiner $(1+\epsilon,O(\sqrt{1/\epsilon}))$ -SLT in linear time. Moreover, this bound is asymptotically tight: For the same set $C$ of $\lceil 1/\epsilon\rceil$ evenly spaced points on a circle (in fact, here $\lceil\sqrt{1/\epsilon}\rceil$ evenly spaced points suffice), any Steiner $(1+\epsilon,\beta)$ -SLT for $C$ for any source $s\in C$ must have $\beta=\Omega(\sqrt{1/\epsilon})$ [13, 29].

Approximation algorithms and hardness.

The aforementioned results provide tight existential bounds on the tradeoff between root-stretch and lightness of SLTs in general graphs as well as in planar graphs and in Euclidean plane; moreover, as mentioned above, tight bounds were established also for Steiner SLTs in Euclidean plane. However, these algorithms do not necessarily provide instance-optimal SLTs: We present point sets $P\subset\mathbb{R}^{2}$ for which any previous SLT algorithm in [2, 3, 18] returns a $(1+\epsilon)$ -ST of weight $O(\frac{1}{\epsilon})\cdot\mathbf{w}(\mathsf{MST}(P))$ , Solomon [29] constructs a Steiner $(1+\epsilon)$ -ST of weight $O(\sqrt{1/\epsilon})\cdot\mathbf{w}(\mathsf{MST}(P))$ , but the minimum weight of a $(1+\epsilon)$ -ST is only $O(1)\cdot\mathbf{w}(\mathsf{MST}(P))$ . Despite the large body of work on SLTs, very little is known about SLTs from the perspective of optimization and approximation algorithms.

In the $(1+\epsilon)$ -SLT problem, we are given a parameter $\epsilon\geq 0$ and an edge-weighted graph $G$ , and the goal is to find a $(1+\epsilon)$ -ST for $G$ of minimum weight. Khuller et al. [18] showed that for any $\epsilon>0$ , the $(1+\epsilon)$ -SLT problem is NP-hard (via a reduction from 3SAT), while the case $\epsilon=0$ can be solved in near-linear time. Cheong and Lee [6] showed that it is NP-hard in Euclidean plane, as well (via a reduction from Knapsack). A $\kappa$ -approximation algorithm for the problem should return a $(1+\epsilon)$ -ST for $G$ whose weight is at most $\kappa$ times that of a minimum weight $(1+\epsilon)$ -ST. One can also consider a bicriteria approximation: a $(\kappa_{1},\kappa_{2})$ -approximation for the problem should return a $(1+\kappa_{1}\cdot\epsilon)$ -ST for $G$ whose weight is at most $\kappa_{2}$ times that of a minimum-weight $(1+\epsilon)$ -ST.

The tight existential bounds, mentioned above, yield approximation factors of $O(1/\epsilon)$ and $O(\sqrt{1/\epsilon})$ , respectively, for the $(1+\epsilon)$ -SLT problem on general edge-weighted graphs and in Euclidean plane, respectively. To the best of our knowledge, no other approximation algorithm or hardness result is known for this problem, even for basic graph families such as the complete graph with Euclidean edge weights. (In our full version, we discuss a related problem, for which both approximation algorithms and hardness results are known.)

In Euclidean spaces, one can define the Steiner $(1+\epsilon)$ -SLT problem: For a parameter $\epsilon\geq 0$ and an input point set $P\subset\mathbb{R}^{d}$ , $d\in\mathbb{N}$ , the goal is to find a Steiner $(1+\epsilon)$ -ST for $P$ of minimum weight. We note that a minimum weight Steiner $(1+\epsilon)$ -ST may be significantly lighter than a minimum weight non-Steiner $(1+\epsilon)$ -ST. For example, for a set $C$ of $\lceil 1/\epsilon\rceil$ evenly spaced points on a circle, the ratio between the weights of minimum weight non-Steiner and Steiner $(1+\epsilon)$ -STs is $\Theta(\sqrt{1/\epsilon})$ .

1.1 Our Contribution

We provide a bicriteria approximation for the $(1+\epsilon)$ -SLT problem, where $0<\epsilon\ll 1$ is an arbitrary parameter, in any constant-dimensional Euclidean space. (We shall assume throughout that $\epsilon$ is a sub-constant parameter. If $\epsilon>0$ is a constant, the algorithm in [18] already provides a constant approximation in linear time.)

Theorem 1.

There is an $O(n\log n\cdot\mathrm{polylog}(\epsilon^{-1}))$ -time algorithm that, given $\epsilon>0$ , a finite set $P$ of $n$ points in Euclidean plane, including a source $s\in P$ , returns a Steiner $(1+O(\epsilon\log\epsilon^{-1}))$ -ST of weight at most $O(\mathsf{opt}_{\epsilon}\cdot\log\epsilon^{-1})$ , where $\mathsf{opt}_{\epsilon}$ denotes the minimum weight of a Steiner $(1+\epsilon)$ -ST. The result extends without any loss in parameters to Euclidean space $\mathbb{R}^{d}$ , for any constant $d\geq 3$ .

Interestingly, our bicriteria approximation algorithm of Theorem 1 incurs the same $O(\log\epsilon^{-1})$ ratio for both the stretch approximation (to the additive $\epsilon$ term) and the weight approximation. With some additional effort and another $\log\epsilon^{-1}$ factor in the weight approximation ratio, our result generalizes to the setting without Steiner points in the plane.

Theorem 2.

There is an $O(n\log n\cdot{\rm polylog}(\epsilon^{-1}))$ -time algorithm that, given $\epsilon>0$ , a finite set $P$ of $n$ points in Euclidean plane, including a source $s\in P$ , returns a $(1+O(\epsilon\log\epsilon^{-1}))$ -ST of weight at most $O(\mathsf{opt}_{\epsilon}\cdot\log^{2}\epsilon^{-1})$ , where $\mathsf{opt}_{\epsilon}$ denotes the minimum weight of a $(1+\epsilon)$ -ST. The result extends to Euclidean space $\mathbb{R}^{d}$ , for any constant $d\geq 3$ , with approximation ratio increasing by a factor of $O(\log\epsilon^{-1})$ and the running time increasing by a factor of $\mathsf{poly}(\epsilon^{-1})$ .

To complement our results, we show that the approximation ratio of our algorithms (with or without using Steiner points) is significantly better than the state-of-the-art algorithms at the instance level. Specifically, we design point sets in Euclidean plane for which any previous algorithm returns a $(1+\epsilon)$ -ST of approximation ratio at least $\Omega(\sqrt{1/\epsilon})$ with Steiner points and $\Omega\left(\frac{1}{\epsilon}\right)$ without Steiner points.

Theorem 3.

For every $\epsilon>0$ , there exists a set $P\subseteq\mathbb{R}^{2}$ and a source $s\in P$ such that the minimum weight of a $(1+\epsilon)$ -ST (resp., Steiner $(1+\epsilon$ )-ST) is $O(1)\cdot\mathbf{w}(\mathsf{MST}(P)),$ but any previous algorithm in [2, 3, 18] returns a $(1+\epsilon)$ -ST of weight $\Omega(\frac{1}{\epsilon})\cdot\mathbf{w}(\mathsf{MST}(P))$ , and the algorithm in [29] returns a Steiner $(1+\epsilon)$ -ST of weight $\Omega(\sqrt{1/\epsilon})\cdot\mathbf{w}(\mathsf{MST}(P))$ .

To prove Theorem 1 and Theorem 2, we reduced the problem to a set of points, called centered $\epsilon$ -net, in a region in a cone with aperture $\sqrt{\epsilon}$ , within $\Theta(1)$ distance from the root. The classical lower-bound construction for this problem consists of a set $P$ of uniformly distributed points along a circle of unit radius centered at the root $s$ . However, if $P$ is the subset of points in a cone of angle $\sqrt{\epsilon}$ , then there exists a Steiner $(1+\epsilon)$ -ST of weight $O(1)\cdot\mathbf{w}(\mathsf{MST}(P))$ [29]. This raises the question: What is the maximum lightness of a Steiner $(1+\epsilon)$ -ST for points in a cone of aperture $\sqrt{\epsilon}$ ? We give a lower bound on the maximum lightness of a minimum-weight Steiner $(1+\epsilon)$ -ST for points in a cone of aperture $\sqrt{\epsilon}$ .

1.2 Technical Overview

Given a set $P$ of $n$ points in the plane, including a source $s\in P$ , and a parameter $\epsilon>0$ , we describe $O(n\log n\cdot\mathrm{polylog}(\epsilon^{-1}))$ -time algorithms to construct a (Steiner) $(1+\epsilon\cdot\log\epsilon^{-1})$ -ST rooted at $s$ , and then analyze its weight compared to the minimum weight $(1+\epsilon)$ -ST rooted at $s$ . We note that, since $(1+\epsilon)$ -STs do not have a recursive substructure, the stretch between two arbitrary points in $P$ may be unbounded. Yet, we can apply a divide-and-conquer strategy by clustering nearby points together, based on their position w.r.t. the source $s$ .

In Section 3, we partition the plane into trapezoid tiles, and show that the union of bicriteria approximate SLTs for the point sets in the tiles is a bicriteria approximation for the entire point set for both the Steiner and non-Steiner settings (Theorem 6). We construct a tiling based on geometric considerations. The diameter of each tile $\tau$ is proportional to the distance ${\rm dist}(s,\tau)$ , and the shape of $\tau$ is roughly $A\times(A\cdot\sqrt{\epsilon})$ for $A={\rm dist}(s,\tau)$ ; see Figure 1. That is, we choose the aspect ratio of every tile to be roughly $\sqrt{\epsilon}$ for the following reason: The triangle inequality implies that every $p s$ -path of weight at most $(1+\epsilon)\cdot d(p,s)$ lies in an ellipse $\mathcal{E}_{ps}$ with foci $p$ and $s$ , and aspect ratio roughly $\sqrt{\epsilon}$ ; see Section 2. Therefore, the union of all ellipses $\mathcal{E}_{ps}$ , for all points $p\in P\cap\tau$ , will be similar to the tile $\tau$ in the sense that the aspect ratio of its bounding box is roughly $\sqrt{\epsilon}$ . The shape of the tiles is crucial for the proof of the reduction (Theorem 6).

For all points in a tile $P\cap\tau$ , the distance $d(p,s)$ to $s$ is the same up to constant factors. We can further partition the set of points in each tile into cluster by approximating $d(p,s)$ up to a $(1+\epsilon)$ -factor. Recall that a classical $\epsilon$ -net in a metric space $(X,d)$ is a set $N\subset X$ such that the points in $N$ are at least $\epsilon$ distance apart, and the $\epsilon$ -neighborhood of every point $x\in X$ contains a net point in $N$ . In Section 3, we define a centered $\epsilon$ -net $N$ , where points $a,b\in N$ are at least $\epsilon\cdot\max\{d(a,s),d(b,s)\}$ apart, and the $(\epsilon\cdot d(p,s))$ -neighborhood of every point $p\in P$ contains a net point in $N$ . We show that a bicriteria approximate STs for a centered $\epsilon$ -net can be extended to bicriteria ST for the entire point set, using $O(1)$ -spanners in the neighborhoods of the net points (Lemma 7). Interestingly, we reduce the $(1+\epsilon)$ -SLT problem for $P$ to a variant of the Steiner $(1+\epsilon)$ -SLT problem for the net $N\subset P$ , where all Steiner points must be in the original set $P$ . We note that although the reduction steps in Section 3 are new and essential to our approach, they are based mainly on standard techniques.

Figure 1: Points in a trapezoid tile

\tau

, and Steiner points

s_{1},\ldots,s_{4}\in\mathcal{E}_{ps}

on parallel lines.

The core technical contributions of our work appear in Sections 4 and 5, where we construct a Steiner ST for a centered $\epsilon$ -net in Section 4 and then extend the construction to the non-Steiner setting in Section 5. The Steiner setting is easier to work with because we can control the location of Steiner points. We begin with a brief overview of the Steiner construction; refer to Figure 1. From the perspective of a single point $p\in P\cap\tau$ , the construction is similar to the Steiner SLT construction by [29], which gave an existentially tight bound: We choose Steiner points $s_{1},s_{2},\ldots,s_{k-1}$ in the ellipse $\mathcal{E}_{ps}$ on parallel lines $L_{1},\ldots,L_{k-1}$ at distance $4^{i}\epsilon\cdot d(p,s)$ from $p$ , where $k=O(\log\epsilon^{-1})$ . Solomon [29] shows that one can carefully choose Steiner points so that the stretch of the path $\pi_{ps}=(p,s_{1},\ldots,s_{k-1},s)$ is at most $1+\epsilon$ . However, geometric calculations show that even if we choose arbitrary points $s_{i}\in L_{i}\cap\mathcal{E}_{ps}$ for $i=1,\ldots,k-1$ , then each edge $s_{i-1}s_{i}$ still contributes only $O(\epsilon)$ to the stretch (more precisely, $\mathbf{w}(s_{i-1}s_{i})$ exceeds the length of its orthogonal projection to the line $p s$ by $O(\epsilon)\cdot d(p,s)$ ). In other words, arbitrary Steiner points $s_{i}\in L_{i}\cap\mathcal{E}_{ps}$ , for $i=1,\ldots,k-1$ , guarantee a root-stretch $1+O(\epsilon\cdot\log\epsilon^{-1})$ .

For a point set $P_{\tau}=P\cap\tau$ in a tile $\tau$ , we follow the above strategy, but we synchronize the lines $L_{1},\ldots,L_{k}$ chosen for different points in $P_{\tau}$ . Then each line $L_{i}$ corresponds to many points $p\in P_{\tau}$ , and intersects their ellipses $\mathcal{E}_{ps}$ . We use a minimum hitting set for the intervals $L_{i}\cap\mathcal{E}_{ps}$ , to choose the minimum number of Steiner points that serve all associated ellipses. The weight analysis uses the fact that each ellipse $\mathcal{E}_{ps}$ contains a $p s$ -path that crosses all lines $L_{1},\ldots,L_{k}$ .

In Section 5, we adapt the Steiner ST algorithm to the non-Steiner setting. However, both the algorithm design and its analysis are more challenging. Instead of creating Steiner points $s_{i}$ in a line $L_{i}$ of our choice, now all points $s_{i}$ must be in $P$ . We use the lines $L_{1},\ldots,L_{k}$ to cover the ellipse $\mathcal{E}_{ps}$ with axis-aligned rectangles whose corners are on two consecutive lines $L_{i}$ and $L_{i+1}$ ; and then choose minimum hitting sets from $P$ for the nonempty rectangles. Some of the rectangles $R_{i}$ might be empty (i.e., $R_{i}\cap P=\emptyset$ ). This means that we cannot choose a point $s_{i}\in P$ in $R_{i}$ for some $p s$ -path (our algorithm simply skips $R_{i}$ ), but it also means that an optimal ST $\mathsf{OPT}$ does not have any vertices in $R_{i}$ , to the $p s$ -path in $\mathsf{OPT}$ contains an edge that traverses $R_{i}$ whose weight is proportional to the width of $R_{i}$ . This is a crucial observation for the weight analysis. The root-stretch analysis also requires more work in the non-Steiner setting: In the Steiner case, the Steiner points $s_{i-1}$ and $s_{i}$ are on the lines $L_{i-1}$ and $L_{i}$ , so we can control the distance between $s_{i-1}$ and $s_{i}$ . However, when are limited to points $s_{i-1},s_{i}\in P$ in rectangles $R_{i-1}$ and $R_{i}$ , it is possible that $s_{i-1}$ and $s_{i}$ are too close to each other, and their contribution to the root-stretch is too large. In such cases, we modify the $p s$ -paths by skipping $s_{i-1}$ or $s_{i}$ . This ensures that the distances between consecutive points of the $p s$ -paths are sufficiently large, and we prove that the weight increases by at most a constant factor. We show that our algorithms (for both the Steiner and non-Steiner settings) extend naturally to higher dimensions using cone partitioning and approximate high-dimensional hitting sets. For the Steiner version, the approximation guarantee remains unchanged. However, the non-Steiner algorithm incurs an additional $\log(\varepsilon^{-1})$ factor in its approximation ratio. Its running time also increases by an additional $\mathsf{poly}(\varepsilon^{-1})$ factor.

2 Preliminaries

Let $p,s\in\mathbb{R}^{2}$ , and $\epsilon>0$ . If $\pi_{ps}$ is a $p s$ -path of weight at most $(1+\epsilon)\cdot d(p,s)$ , then every point $q\in\pi_{ps}$ , we have $d(p,q)+d(q,s)\leq\mathbf{w}(\pi_{ps})\leq(1+\epsilon)\cdot d(p,s)$ . This implies that $\pi_{ps}$ is contained in the ellipse $\mathcal{E}_{ps}$ with foci $p$ and $s$ , and major axis $(1+\epsilon)d(p,s)$ ; see Figure 2. The ellipse $\mathcal{E}_{ps}$ is contained in a rectangle spanned by its major and minor axes. The length of its minor axis is $\sqrt{(1+\epsilon)^{2}-1}\cdot d(p,s)=\sqrt{2\epsilon+\epsilon^{2}}\cdot d(p,s% )<2\sqrt{\epsilon}\cdot d(p,s)$ if $\epsilon<2$ .

Figure 2: The ellipse

\mathcal{E}_{ps}

with foci

p

and

s

and major axis of length

(1+\epsilon)\cdot d(p,s)

.

For analyzing the weight of an ST, we consider a $p s$ -path $\pi_{ps}$ as a polyline (i.e., a subset of the plane). In particular, for any region $R\subset\mathbb{R}^{2}$ , the intersection $\pi\cap R$ is the part of the polyline contained in $R$ .

Slopes, slack, and stretch.

The slope of a line segment $a b$ is $\mathrm{slope}(ab)=\frac{y(b)-y(a)}{x(b)-x(a)}$ if $x(a)\neq x(b)$ , and $\mathrm{slope}(ab)=\infty$ if $x(a)=x(b)$ . For a line segment $a b$ in the plane, we denote by $\mathrm{proj}(ab)$ the orthogonal projection of $a b$ to the $x$ -axis. Note that $|\mathrm{proj}(ab)|=|x(b)-x(a)|$ . We define the slack of $a b$ as $\mathrm{slack}(ab)=d(a,b)-|\mathrm{proj}(ab)|$ . In our paper, all proofs of theorems, lemmas, corollaries, and observations marked with a $\star$ are in our full version.

Lemma 4 ( $\star$ ).

For any line segment $a b$ with $\mathrm{slope}(ab)\neq\infty$ , we have

	$\displaystyle\|\mathrm{proj}(ab)\|\cdot\left(1+\frac{1}{3}\cdot\|\mathrm{slope}(% ab)\|^{2}\right)\nobreak\ \leq\nobreak\$	$\displaystyle d(a,b)\nobreak\ \leq\nobreak\ \|\mathrm{proj}(ab)\|\cdot\left(1+% \frac{1}{2}\cdot\|\mathrm{slope}(ab)\|^{2}\right)$		(1)
	$\displaystyle\frac{1}{3}\cdot\|\mathrm{slope}(ab)\|^{2}\nobreak\ \leq\nobreak\$	$\displaystyle\frac{\mathrm{slack}(ab)}{\|\mathrm{proj}(ab)\|}\nobreak\ \leq% \nobreak\ \frac{1}{2}\cdot\|\mathrm{slope}(ab)\|^{2}.$		(2)

It is known that a $x$ -monotone path (i.e., a path in which the $x$ -coordinates of the points along the path are monotone increasing) with edges of bounded slopes have small stretch.

Lemma 5.

Let $\pi=(v_{0},v_{1},\ldots,v_{k})$ be a $x$ -monotone polygonal path in $\mathbb{R}^{2}$ such that $|\mathrm{slope}(v_{i-1}v_{i})|\leq\varrho$ for all $i\in[1,k]$ . Then $|\mathrm{slope}(v_{0}v_{k})|\leq\varrho$ ; and $\frac{\mathbf{w}(\pi)}{d(v_{0},v_{k})}\leq\sqrt{1+\varrho^{2}}<1+\frac{\varrho% ^{2}}{2}$ .

For two points $a,b\in\mathbb{R}^{2}$ and a parameter $\epsilon>0$ , let $\mathcal{E}_{ab,\epsilon}$ denote the ellipse with foci $a$ and $b$ and major axis $(1+\epsilon)\cdot d(a,b)$ , that is, $\mathcal{E}_{ab,\epsilon}=\{p\in\mathbb{R}^{2}:d(a,p)+d(p,b)\leq(1+\epsilon)% \cdot d(a,b)\}$ .

3 Reduction to Net Points in a Trapezoid

In this section, we reduce the problem of constructing a bicriteria approximation for the minimum weight (Steiner) $(1+\epsilon)$ -ST to the special case where all points, except the source $s$ , lie in a trapezoid, and the point set is sparse (i.e., form a centered $\epsilon$ -net, defined below).

Given a source $s\in\mathbb{R}^{2}$ and $\epsilon>0$ , define a tiling of the plane into a set $\mathcal{T}$ of trapezoids as follows; refer to Figure 3. Let $C$ be a circle of unit radius centered at $s$ . Let $O_{1}$ be a regular $k$ -polygon with inscribed circle $C$ , where $k$ is the minimum integer such that the side length of $O_{1}$ is less than $\sqrt{\epsilon}$ . For all integers $i\in\mathbb{Z}$ , let $O_{i}=2^{i}\cdot O_{1}$ , that is, a scaled copy of $O_{1}$ , centered at $s$ . Finally, add $k$ rays emanating from $s$ that pass through the vertices of the polygons $O_{i}$ , $i\in\mathbb{Z}$ . Polygons $O_{i}$ , $i\in\mathbb{Z}$ , and the $k$ rays subdivide the plane into a set $\mathcal{T}$ of trapezoids: Each trapezoid $\tau\in\mathcal{T}$ lies between two consecutive polygons $O_{i}$ and $O_{i+1}$ , and two consecutive rays.

Figure 3: A section of the trapezoid tiling of the plane.

Let $P$ be a set of $n$ points in the plane, and let $\tau_{1},\ldots,\tau_{m}\in\mathcal{T}$ be a finite set of tiles that cover $P$ , and let $P_{i}:=P\cap\tau_{i}$ . For a tile $\tau_{i}\in\mathcal{T}$ , we define a tile-restricted $(1+\epsilon)$ -ST (for short, $(1+\epsilon)$ -tST) as a tree $T=(V,E)$ such that $P_{i}\cup\{s\}\subseteq V(T)\subseteq P$ , and $T$ contains a $p s$ -path of weight at most $(1+\epsilon)\cdot d(p,s)$ for every $p\in P_{i}$ . In other words, a tile-restricted $(1+\epsilon)$ -ST is a Steiner $(1+\epsilon)$ -ST for $P_{i}\cup\{s\}$ rooted at $s$ , where all Steiner points are in $P$ .

Theorem 6 ( $\star$ ).

Given a set $P\subset\mathbb{R}^{2}$ of $n$ points, a source $s\in\mathbb{R}^{2}$ , a parameter $\epsilon>0$ , and two real functions $f(.)$ and $g(.)$ . Let $\tau_{1},\ldots,\tau_{m}$ be the set of tiles in $\mathcal{T}$ , where $P_{i}:=P\cap\tau_{i}\neq\emptyset$ . Let $G_{i}$ be a tile-restricted $(1+f(\epsilon)\cdot\epsilon)$ -ST (resp., Steiner $(1+f(\epsilon)\cdot\epsilon)$ -ST) for $P_{i}\cup\{s\}$ of weight $\mathbf{w}(G_{i})\leq O(g(\epsilon)\cdot\mathsf{opt}_{\epsilon,i})$ , where $\mathsf{opt}_{\epsilon,i}$ is the minimum weight of a $(1+\epsilon)$ -ST for $P_{i}\cup\{s\}$ , for all $i=1,\ldots,m$ . Then, a shortest-path tree of the graph $G:=\bigcup_{i=1}^{m}G_{i}$ , rooted at $s$ , is a $(1+f(\epsilon)\cdot\epsilon)$ -ST (resp., Steiner $(1+f(\epsilon)\cdot\epsilon)$ -ST) for $P\cup\{s\}$ and $\mathbf{w}(G)\leq O(g(\epsilon)\cdot\mathsf{opt}_{\epsilon})$ , where $\mathsf{opt}_{\epsilon}$ is the minimum weight of a $(1+\epsilon)$ -ST for $P\cup\{s\}$ .

For the purpose of a $(1+\epsilon)$ -ST, with a source (or center) $s\in P$ , we define a variation of $\epsilon$ -nets where the density of the net depends on the distance from $s$ : A centered $\epsilon$ -net (for short, $\epsilon$ -cnet) with center $s$ is a subset $N\subset P$ such that

$\blacksquare$

for all $a,b\in N$ , $a\neq b$ , we have $d(a,b)>\epsilon\cdot\min\{d(a,s),d(b,s)\}$ and
$\blacksquare$

for every $p\in P$ , there exists a point $a\in N$ such that $d(p,a)\leq\epsilon\cdot d(p,s)$ .

Given a point set $P\subset\mathbb{R}^{2}$ , including $s\in P$ , a parameter $\epsilon>0$ and a subset $P$ , we also define a net-restricted $(1+\epsilon)$ -ST for $N\subset P$ as a tree $T=(V,E)$ such that $N\cup\{s\}\subseteq V(T)\subseteq P$ , and $T$ contains a $p s$ -path of weight at most $(1+\epsilon)\cdot d(p,s)$ for every $p\in N$ . This means that $T$ is a Steiner $(1+\epsilon)$ -ST rooted at $s$ for the $\epsilon$ -cnet $N$ , where all Steiner points are in $P$ . We claim that it suffices to find a net-restricted (resp., Steiner) $(1+\epsilon)$ -ST for a $\epsilon$ -cnet with center $s$ .

Lemma 7 ( $\star$ ).

Let $P$ be a set of $n$ points in the plane, $s\in P$ , $\epsilon\in(0,\frac{1}{9})$ , and $N\subset P$ a $\epsilon$ -cnet for $P$ . Let $f(.)$ and $g(.)$ be real functions such that $f(x)\geq x$ and $g(x)\geq x$ for all $x\geq 0$ . Assume that in $O(|N|\log|N|)$ time, we can compute a net-restricted (resp., Steiner) $(1+f(\epsilon)\cdot\epsilon)$ -ST $T_{N}$ for $N$ of weight $O(g(\epsilon))\cdot\mathsf{opt}_{\epsilon}(N)$ , where $\mathsf{opt}_{\epsilon}(N)$ is the minimum weight of a net-restricted (resp., Steiner) $(1+\epsilon)$ -ST for $N$ . Then, in $O(n\log n)$ time, we can compute a (Steiner) $(1+O(f(\epsilon)\cdot\epsilon))$ -ST $T_{P}$ for $P$ of weight $O(g(\epsilon))\cdot\mathsf{opt}_{\epsilon}(P)$ , where $\mathsf{opt}_{\epsilon}(P)$ is the minimum weight of a (Steiner) $(1+\epsilon)$ -ST for $P$ .

4 Steiner Shallow Trees for Points in a Tile

In this section, we prove Theorem 1. By Theorem 6 and Lemma 7, we may assume that $P$ is a set of points in a trapezoid $\tau\in\mathcal{T}$ (defined in Section 3), and $P$ is a centered $\epsilon$ -net w.r.t. center $s\in P$ . We may further assume w.l.o.g. that $\tau\subset[0,1]\times[-\sqrt{\epsilon},\sqrt{\epsilon}]$ and $s=(2,0)$ ; see Figure 4. We first present an algorithm that constructs a Steiner tree $T$ for $P\cup\{s\}$ , rooted at $s$ . Then we show that $T$ is a $(1+O(\epsilon\log\epsilon^{-1}))$ -ST and its weight is $O(\mathsf{opt}_{\epsilon}\cdot\log\epsilon^{-1})$ , where $\mathsf{opt}_{\epsilon}$ denotes the minimum weight of a Steiner $(1+\epsilon)$ -ST for $P$ rooted at $s$ ; and let $\mathsf{OPT}_{\epsilon}$ be one such Steiner $(1+\epsilon)$ -ST.

Figure 4: A point set

P

in a trapezoid

\tau

and a source

s=(2,0)

.

Steiner shallow tree construction: Overview.

We start with a brief overview of the ST construction and then present the algorithm in detail. We construct a Steiner graph $G$ on $P\cup\{s\}$ (which is not necessarily a tree), and then let $T$ be the shortest path tree of $G$ rooted at $s$ (that is, the single-source shortest path tree of $G$ with $s$ as the source). We can analyze the root-stretch in the graph $G$ , and the weight of $T$ is upper-bounded by the weight of $G$ .

For each point $p\in P$ , we know that $\mathsf{OPT}_{\epsilon}$ contains a $p s$ -path of length at most $(1+\epsilon)\cdot d(p,s)$ in the ellipse $\mathcal{E}_{ps}$ with major axis $(1+\epsilon)\cdot d(p,s)$ . We associate each point $p\in P$ with vertical lines $L_{0}(p),\ldots,L_{k-1}(p)$ , where $k=O(\log\epsilon^{-1})$ . For $i=0,1,\ldots,k-1$ , we choose a Steiner point $s_{i}$ in the line segments $\mathcal{E}_{ps}\cap L_{i}(p)$ , and add the path $\pi_{ps}=(p,s_{0},\ldots,s_{k-1},s)$ to the graph $G$ . We show (Lemma 12) that if the distances between the vertical lines $L_{1},\ldots,L_{k}$ increase exponentially, then $\mathbf{w}(\pi_{ps})=(1+O(\epsilon\log\epsilon^{-1}))\cdot d(p,s)$ .

Importantly, each line $L_{i}$ is associated with multiple points in $P$ , and each Steiner point $s_{i}\in L_{i}$ also serves multiple points in $P$ . For each line $L_{i}$ , we choose the Steiner points in $L_{i}$ as a minimum hitting set for the line segments $\mathcal{E}_{ps}\cap L_{i}$ over all points $p\in P$ associated with line $L_{i}$ . Since the intersection $\mathsf{OPT}_{\epsilon}\cap L_{i}$ is a hitting set for these intervals, we can charge the weight of $G$ to the weight of $\mathsf{OPT}_{\epsilon}$ . The approximation factor $O(\log\epsilon^{-1})$ , in the stretch and the weight, is the result of using $O(\log\epsilon^{-1})$ Steiner points, one in each line $L_{i}$ , for $i=1,\ldots,k$ .

Steiner shallow tree construction: Details.

Assume w.l.o.g. that $\epsilon=4^{-(k+1)}$ for some $k\in\mathbb{N}$ . Each ellipse $\mathcal{E}_{ps}$ is contained in an ellipse $\mathcal{E}_{pb(p),2\epsilon}$ ( $\star$ ), where the segment $pb(p)$ is horizontal and $d(p,b(p))\leq 2\cdot d(p,s)$ . As a shorthand notation, we use $\mathcal{E}_{p}:=\mathcal{E}_{pb(p),2\epsilon}$ .

We define families of vertical lines. For every integer $i\geq 0$ , let

\mathcal{L}_{i}=\{x=j4^{i}\cdot\epsilon:j\in\mathbb{Z}\},

(3)

that is, the distance between two consecutive vertical lines in $\mathcal{L}_{i}$ is $4^{i}\cdot\epsilon$ . For every point $p\in P$ , we recursively choose $L_{i}(p)\in\mathcal{L}_{i}$ for $i=0,1,\ldots,k-1$ , as follows. Let $L_{0}(p)$ be the second line in $\mathcal{L}_{0}$ to the right of $p$ . For $i=1,\ldots,k-1$ , if $L_{i-1}(p)$ has already been chosen, let $L_{i}(p)$ be the second line in $\mathcal{L}_{i}$ to the right of $L_{i-1}(p)$ . (We choose the second line in $\mathcal{L}_{i}$ , rather than the first one, to ensure that the gaps between $L_{i-1}(p)$ and $L_{i}(p)$ grow exponentially in $i$ ; cf. Observation 8.)

Now consider a line $L\in\mathcal{L}_{i}$ , and let $P(L)$ be the set of all points in $P$ associated with $L$ . Formally, we put $P(L)=\{p\in P:L_{i}(p)=L\}$ . Consider the set of intervals $I(L)=\{L\cap\mathcal{E}_{p}:p\in P(L)\}$ . Let $H(L)$ be a minimum hitting set (a.k.a., piercing set, stabbing set, or transversal) for $I(L)$ : It is a minimum subset of $L$ that contains at least one point in each interval in $I(L)$ ; it can be computed in $O(|I(L)|\log|H(L)|)$ time [10, 15, 24].

Finally, we construct the Steiner graph $G$ as follows. The vertex set of $G$ comprises $P$ , $s$ , and the points $H(L)$ for all $L\in\mathcal{L}_{i}$ , $i=0,\ldots,k-1$ . The edges are defined as follows. For each point $p\in P$ , consider the lines $L_{0}(p),\ldots,L_{k-1}(p)$ associated with $p$ . For $i=0,1,\ldots,k-1$ let $s_{i}(p)$ be an arbitrary point in $H(L_{i}(p))\cap\mathcal{E}_{p}$ . Add the edges of the path $\pi_{ps}=(p,s_{0}(p),\ldots,s_{k-1}(p),s)$ to $G$ . We output the shortest path tree $T$ of $G$ rooted at $s$ .

Observation 8.

For $i\in[1,k-1]$ , $\mathsf{dist}(L_{i-1}(p),L_{i}(p))$ is within $[4^{i}\,\epsilon,2\cdot 4^{i}\,\epsilon]$ .

From Observation 8, using a geometric series, we obtain the following corollary:

Corollary 9 ( $\star$ ).

For $i\in[1,k-1]$ , $\mathsf{dist}(p,L_{i}(p))$ is within $[4^{i}\,\epsilon,\frac{32}{3}\cdot 4^{i}\,\epsilon]$ .

Root stretch analysis.

It is enough to analyze the root stretch in the graph $G$ . Recall that in the construction of $G$ , we have already built a path $\pi_{ps}=(p,s_{0}(p),\ldots,s_{k-1}(p),s)$ . We show that $\mathbf{w}(\pi_{ps})\leq(1+O(\epsilon\log\epsilon^{-1}))\cdot d(p,s)$ (Lemma 12). We first need to estimate the slopes of the edges of $\pi_{ps}$ . We start with the following lemma.

Lemma 10.

For every point $p\in P$ if a vertical line $L$ is to the right of $p$ at distance $x\in[0,\frac{2}{3}]$ from $p$ , then $\mathbf{w}(L\cap\mathcal{E}_{p})=\Theta(\sqrt{\epsilon\,x})$ . In particular, for every $i=0,\ldots,k-1$ , we have $\mathbf{w}(L_{i}(p)\cap\mathcal{E}_{p})=\Theta(2^{i}\cdot\epsilon)$ .

Proof.

Consider the unit disk $D=\{(x,y)\in\mathbb{R}^{2}:x^{2}+y^{2}=1\}$ and the line $L:x=-1+\varrho$ for $0\leq\varrho\leq 1$ ; see Figure 5. Then for $\varrho\in[0,1]$ , we obtain

\mathbf{w}(D\cap L)=2\cdot\sqrt{1^{2}-(1-\varrho)^{2}}=2\cdot\sqrt{2\varrho-% \varrho^{2}}=2^{3/2}\cdot\sqrt{\varrho-\frac{\varrho^{2}}{2}}=\Theta(\sqrt{% \varrho}).

The ellipse $\mathcal{E}_{p}=\mathcal{E}_{pb,2\epsilon}$ is an affine image of the unit disk $D$ : The affine transformation $f(x,y)=(\frac{M}{2}x,\frac{m}{2}y)$ takes $D$ to $\mathcal{E}_{p}$ , where $M$ and $m$ are the major and minor axes of $\mathcal{E}_{p}$ . We estimate $M$ and $m$ up to constant factors. Since $P\subset[0,1]\times[-\sqrt{\epsilon},\sqrt{\epsilon}]$ and $s=(2,0)$ , then we have $1\leq|x(p)-x(s)|\leq 2$ . We have $1\leq d(p,b(p))\leq 4$ ( $\star$ ). The major axis of $\mathcal{E}_{p}$ is $M=(1+2\epsilon)\cdot d(p,b(p))$ so $1<M\leq 4+8\epsilon$ ; and its minor axis is $m=2\cdot\sqrt{(1+2\epsilon)^{2}-1}\cdot d(p,b(p))=4\cdot\sqrt{\epsilon+% \epsilon^{2}}\cdot d(p,b(p))$ , and so $4\cdot\sqrt{\epsilon}\leq m\leq 16\cdot\sqrt{\epsilon+\epsilon^{2}}\leq 16% \sqrt{2}\cdot\sqrt{\epsilon}$ .

Figure 5: A unit disk

D

, a cross section

L\cap D

, and an affine transformation to the ellipse

\mathcal{E}_{p}

.

The focus $p$ is at distance $\epsilon\cdot d(p,b(p))$ from the leftmost point of $\mathcal{E}_{p}$ , where $\epsilon\leq\epsilon\cdot d(p,b(p))\leq 4\epsilon$ . By Corollary 9, the distance between $L_{i}(p)$ and the leftmost point of $\mathcal{E}_{p}$ is at least $\epsilon+4^{i}\epsilon=\Omega(4^{i}\epsilon\cdot M)$ and at most $4\epsilon+\frac{32}{3}\cdot 4^{i}\epsilon=O(4^{i}\epsilon\cdot M)$ . Overall, this distance is $\Theta(4^{i}\epsilon\cdot M)$ .

The inverse transformation $f^{-1}$ takes $\mathcal{E}_{p}$ to the unit disk $D$ , and the line $L_{i}(p)$ to a vertical line $L:x=-1+\varrho$ , where $\varrho=\Theta(4^{i}\epsilon)$ . As noted above, we have $\mathbf{w}(L\cap D)=\Theta(\sqrt{\varrho})=\Theta(2^{i}\cdot\sqrt{\epsilon})$ , consequently $\mathbf{w}(L_{i}(p)\cap\mathcal{E}_{p})=\Theta(m\cdot\sqrt{\varrho})=\Theta(% \sqrt{\epsilon}\cdot 2^{i}\cdot\sqrt{\epsilon})=\Theta(2^{i}\cdot\epsilon)$ . $\hfill\blacktriangleleft$

Combining Observation 8 and Lemma 10, we have the following corollary:

Corollary 11 ( $\star$ ).

For every $p\in P$ , consider the path $\pi_{ps}=(p,s_{0},\ldots,s_{k-1},s)$ . For all $i=1,\ldots,k-1$ , we have $|\mathrm{slope}(s_{i-1}s_{i})|\leq O(2^{-i})$ .

Lemma 12.

For every $p\in P$ , we have $\mathbf{w}(\pi_{ps})\leq(1+O(\epsilon\log\epsilon^{-1}))\cdot d(p,s)$ .

Proof.

By construction, we have $\pi_{ps}=(p,s_{0},s_{1},\ldots s_{k-1},s)$ . We partition $\pi_{ps}$ into three parts: $ps_{0}$ , $(s_{0},s_{1},\ldots s_{k-1})$ and $s_{k-1}s$ , and bound the weight of each part separately.

First we estimate the weight of the first edge $ps_{0}$ . Recall that $p\in[0,1]\times[-\sqrt{\epsilon},\sqrt{\epsilon}]$ and $s=(2,0)$ . By construction, we have $|x(p)-x(s_{0})|\leq\epsilon$ , and Lemma 10 gives $|y(p)-y(s_{0})|\leq O(\epsilon)$ . Therefore, we have $\mathbf{w}(ps_{0})=O(\epsilon)\leq O(\epsilon)\cdot d(p,s)$ . We can now bound the weight of the subpath $(s_{0},s_{1},\ldots,s_{k-1})$ of $\pi_{ps}$ . By Lemma 4, Observation 8, and Corollary 11,
$\displaystyle\mathbf{w}((s_{0},s_{1},\ldots,s_{k-1}))$ $\displaystyle=\sum_{j=1}^{k}\mathbf{w}(s_{j-1}s_{j})\leq\sum_{j=1}^{k-1}\left(% 1+\frac{(\mathrm{slope}(s_{j-1}s_{j}))^{2}}{2}\right)\cdot|\mathrm{proj}(s_{j-% 1}s_{j})|$ $\displaystyle=\sum_{j=1}^{k-1}|\mathrm{proj}(s_{j-1}s_{j})|+\sum_{j=1}^{k-1}O(% 4^{-j})\cdot|\mathrm{proj}(s_{j-1}s_{j})|$ $\displaystyle\leq|\mathrm{proj}(s_{0}s_{k-1})|+\sum_{j=1}^{k-1}O(4^{-j})\cdot 2% \cdot 4^{j}\cdot\epsilon=|\mathrm{proj}(s_{0}s_{k-1})|+O(k\epsilon)$ $\displaystyle=|\mathrm{proj}(s_{0}s_{k-1})|+O\left(\epsilon\log\epsilon^{-1}% \right)=|\mathrm{proj}(s_{0}s_{k-1})|\left(1+O\left(\epsilon\log\epsilon^{-1}% \right)\right).$

Finally, we estimate the weight of the last edge, $s_{k-1}s$ , of $\pi_{ps}$ . We have

{\rm dist}(p,L_{k-1}(p))<\frac{32}{3}\cdot 4^{k-1}\cdot\epsilon=\frac{2}{3% \epsilon}\cdot\epsilon=\frac{2}{3}.\qquad\text{(by \lx@cref{creftypecap~refnum% }{cor:spacing} and $\epsilon=4^{-(k+1)}$)}

(4)

Since $x(p)\in[0,1]$ and $s=(2,0)$ , then $|x(s_{k-1})-x(s)|\geq\frac{1}{3}$ . Lemma 10 gives $|y(s_{k-1})-y(s)|=|y(s_{k-1})|\leq O(2^{k-1}\cdot\epsilon)=O\left(\frac{1}{% \sqrt{\epsilon}}\cdot\epsilon\right)=O(\sqrt{\epsilon})$ . Consequently, $\mathrm{slope}(s_{k-1}s)=O(\sqrt{\epsilon})$ , and Lemma 4 yields $\mathbf{w}(s_{k-1}s)\leq(1+O(\epsilon))\cdot|\mathrm{proj}(s_{k-1}s)|$ .

The sum of the weights of the three parts is

	$\displaystyle\mathbf{w}(\pi_{ps})$	$\displaystyle=\mathbf{w}(ps)+\mathbf{w}((s_{0},s_{1},\ldots,s_{k-1}))+\mathbf{% w}(s_{k-1}s)$
		$\displaystyle\leq O(\epsilon)\cdot d(p,s)+\left(1+O\left(\epsilon\log\epsilon^% {-1}\right)\right)\|\mathrm{proj}(s_{0}s_{k-1})\|+(1+O(\epsilon))\cdot\|\mathrm{% proj}(s_{k-1}s)\|$
		$\displaystyle\leq O(\epsilon)\cdot d(p,s)+\left(1+O\left(\epsilon\log\epsilon^% {-1}\right)\right)\|\mathrm{proj}(s_{0}s)\|\leq\left(1+O\left(\epsilon\log% \epsilon^{-1}\right)\right)d(p,s).\$

$\hfill\blacktriangleleft$

Weight analysis.

We give an upper bound for $\mathbf{w}(G)$ . Similarly to the root stretch analysis, we decompose $\pi_{ps}$ into three parts, $ps_{0}$ , $(s_{0},s_{1},\ldots,s_{k-1})$ , and $s_{k-1}s$ , and then bound the weight of the union of each.

We first analyze the total weight of the union of edges $s_{i-1}(p)\,s_{i}(p)$ of the paths $\pi_{ps}$ over all $p\in P$ . For lines $L_{a}\in\mathcal{L}_{i-1}$ and $L_{b}\in\mathcal{L}_{i}$ , let $G(L_{a},L_{b})$ denote the set of all edges $uv\in E(G)$ such that $u\in I(L_{a})$ and $v\in I(L_{b})$ . Recall that $\mathsf{OPT}_{\epsilon}$ is a minimum-weight Steiner $(1+\epsilon)$ -ST for $P\cup\{s\}$ rooted at $s$ ( $\mathbf{w}(\mathsf{OPT}_{\epsilon})=\mathsf{opt}_{\epsilon}$ ). We denote by $\mathsf{OPT}_{\epsilon}\cap\llbracket L_{a},L_{b}\rrbracket$ the part of $\mathsf{OPT}_{\epsilon}$ clipped in the vertical strip $\llbracket L_{a},L_{b}\rrbracket$ . Our main lemma is as follows.

Lemma 13.

For every $p\in P$ and $i\in\{1,\ldots,k-1\}$ , we have

\mathbf{w}(G(L_{i-1}(p),L_{i}(p)))\leq O(\mathbf{w}(\mathsf{OPT}_{\epsilon}% \cap\llbracket L_{i-1}(p),L_{i}(p)\rrbracket)).

Before the proof of Lemma 13, we observe that it implies the bound on the total weight of the interior edges of the paths $\pi_{ps}$ over all $p\in P$ .

Corollary 14 ( $\star$ ).

$\mathbf{w}\left(\bigcup_{p\in P}(s_{0}(p),\ldots,s_{k-1}(p))\right)\leq O(\log% \epsilon^{-1}\cdot\mathsf{opt}_{\epsilon})$ .

It remains to prove Lemma 13. We do this in a sequence of lemmas, using geometric properties of ellipses and interval graphs. We start with an easy observation.

Observation 15 ( $\star$ ).

For every $p\in P$ and every $i\in\{1,\ldots,k-1\}$ , we have

\mathbf{w}(\mathsf{OPT}_{\epsilon}\cap\llbracket L_{i-1}(p),L_{i}(p)\rrbracket% \cap\mathcal{E}_{p})\geq{\rm dist}(L_{i-1}(p),L_{i}(p)).

Lemma 16.

For every $i\in\{1,\ldots,k-1\}$ and every $p\in P$ , there exists a set $Q\subset P(L_{i-1}(p))$ of size $|Q|\geq\Omega(|H(L_{i}(p))|)$ such that the regions in $\{\mathcal{E}_{q}\cap\llbracket L_{i-1}(p),L_{i}(p)\rrbracket:q\in Q\}$ are disjoint.

Proof.

Each interval in $I(L_{i}(p))$ has weight $\Theta(2^{i}\cdot\epsilon)$ by Lemma 10. Let $c\geq 1$ be the ratio of the maximum to the minimum weight of an interval in $I(L_{i}(p))$ . Each interval in $I(L_{i}(p))$ is of the form $L_{i}(p)\cap\mathcal{E}_{r}$ for some point $r\in P(L_{i}(p))$ . For every $r\in P(L_{i}(p))$ , let $B_{r}$ be the axis-aligned bounding box of $\mathcal{E}_{r}\cap\llbracket L_{i-1}(p),L_{i}(p)\rrbracket$ ; see Figure 6. Note that the major axis of $\mathcal{E}_{r}$ is horizontal, and its minor axis is to the right of $L_{i}$ by Equation 4. Consequently, for every vertical line $L\subset\llbracket L_{i-1}(p),L_{i}(p)\rrbracket$ , we have $\mathbf{w}(L\cap\mathcal{E}_{r})\leq\mathbf{w}(L_{i}(p)\cap\mathcal{E}_{r})$ , which holds with equality for $L=L_{i}(p)$ . In particular, the height of $B_{r}$ is $\mathbf{w}(L_{i}(p)\cap\mathcal{E}_{r})=\Theta(2^{i}\cdot\epsilon)$ .

Figure 6: A point

p\in P

and ellipses

\mathcal{E}_{r}

for five points in

P(L_{i-1}(p))

. The boxes

B_{r}

corresponding to the three light blue ellipses are disjoint. A minimum hitting set

H(L_{i}(p))

has size 3.

Now consider a maximum set $Q_{0}\subset P(L_{i}(p))$ such that the intervals $\{L_{i}(p)\cap\mathcal{E}_{q}:q\in Q_{0}\}$ are disjoint. Note that $|Q_{0}|=|H(L_{i}(p))|$ , that is, the maximum independent set has the same size as a hitting set for intervals in a line.

A set of disjoint intervals along the line $L_{i}(p)$ have a well-defined total order, which defines a total order on $Q_{0}$ . Let $Q\subset Q_{0}$ be the subset that corresponds to the first and every $\lceil c\rceil$ -th interval. Then $|Q_{0}|=\Theta(|Q|)=\Theta(|H(L_{i}(p))|)$ . Furthermore, the intervals $\{L_{i}(p)\cap\mathcal{E}_{q}:q\in Q\}$ are disjoint. This, in turn, implies that the boxes $\{B_{q}:q\in Q\}$ are disjoint. Thus, the regions $\{\mathcal{E}_{q}\cap\llbracket L_{i-1}(p),L_{i}(p)\rrbracket:q\in Q\}$ are also disjoint. $\hfill\blacktriangleleft$

Observation 15 and Lemma 16 imply the following corollary.

Corollary 17 ( $\star$ ).

For every $p\in P$ and $i\in\{1,\ldots,k-1\}$ , we have

\Omega(|H(L_{i}(p))|)\cdot{\rm dist}(L_{i-1}(p),L_{i}(p))\leq\mathbf{w}\big(% \mathsf{OPT}_{\epsilon}\cap\llbracket L_{i-1}(p),L_{i}(p)\rrbracket\big).

Lemma 18.

For every $p\in P$ and $i\in\{1,\ldots,k-1\}$ , we have

\mathbf{w}(G(L_{i-1}(p),L_{i}(p)))\leq O(|H(L_{i}(p)|)\cdot{\rm dist}(L_{i-1}(% p),L_{i}(p)).

Proof.

We first show that every edge in $G(L_{i-1}(p),L_{i}(p))$ has weight $\Theta({\rm dist}(L_{i-1}(p),L_{i}(p)))$ . Every edge of $G(L_{i-1}(p),L_{i}(p))$ is the edge $s_{i-1}(r)s_{i}(r)$ of $\pi_{rs}$ for some point $r\in P(L_{i-1}(p))$ . By Corollary 11, $|\mathrm{slope}(s_{i-1}(r)s_{i}(r))|\leq O(2^{-i})$ , where $i=O(\log_{4}\epsilon^{-1})$ . Consequently, we have $|\mathrm{slope}(s_{i-1}(r)s_{i}(r))|\leq O(1)$ for all $i=1,\ldots,k-1$ . Therefore,

\mathbf{w}(s_{i-1}(r)s_{i}(r))\leq O(1)\cdot|\mathrm{proj}(s_{i-1}(r)s_{i}(r))% |\leq O({\rm dist}(L_{i-1}(p),L_{i}(p))).

Next, we show that every vertex $v\in H(L_{i}(p))$ of $G(L_{i-1}(p),L_{i}(p))$ has $O(1)$ degree. Lemma 10 gives $\mathbf{w}(L_{i-1}(p)\cap\mathcal{E}_{r})=\Theta(2^{i})$ and $\mathbf{w}(L_{i}(p)\cap\mathcal{E}_{r})=\Theta(2^{i-1})$ for all $r\in P(L_{i-1}(p))$ . Note also that both $L_{i-1}(p)\cap\mathcal{E}_{r}$ and $L_{i}(p)\cap\mathcal{E}_{r}$ have a reflection symmetry in the horizontal major axis of $\mathcal{E}_{r}$ , implying $\bigcup\{L_{i}(p)\cap\mathcal{E}_{r}:r\in P(L_{i}(p))\mbox{ \rm and }v\in% \mathcal{E}_{r}\}$ is contained in an interval of length $2\cdot\Theta(2^{i})=\Theta(2^{i})$ centered at $v$ . Similarly, $\bigcup\{L_{i-1}(p)\cap\mathcal{E}_{r}:r\in P(L_{i-1}(p))\mbox{ \rm and }v\in% \mathcal{E}_{r}\}$ is contained in an interval $I\subset L_{i-1}$ of length $2\cdot\Theta(2^{i-1})=\Theta(2^{i})$ . Since $\mathbf{w}(L_{i-1}(p)\cap\mathcal{E}_{r})=\Theta(2^{i})$ for all $r\in P(L_{i-1}(p))$ , then the hitting set $H(L_{i-1}(p))$ contains $O(1)$ points in the interval $I$ . In the graph $G(L_{i-1}(p),L_{i}(p))$ , all neighbors of vertex $v$ are in the interval $I$ and in $H(L_{i-1}(p))$ . This proves that $v$ has $O(1)$ neighbors in $G(L_{i-1}(p),L_{i}(p))$ .

Overall, every edge of $G(L_{i-1}(p),L_{i}(p))$ has weight $\Theta({\rm dist}(L_{i-1}(p),L_{i}(p)))$ ; and every vertex $v\in H(L_{i}(p))$ of $G(L_{i-1}(p),L_{i}(p))$ has $O(1)$ degree. Since $G(L_{i-1}(p),L_{i}(p))$ is a bipartite graph with partite sets $H(L_{i-1}(p))$ and $H(L_{i}(p))$ , then the total weight of $G(L_{i-1}(p),L_{i}(p))$ is $O(|H(L_{i}(p)|)\cdot{\rm dist}(L_{i-1}(p),L_{i}(p))$ , as claimed. $\hfill\blacktriangleleft$

Combining Lemma 18 and Corollary 17, we obtain Lemma 13. We conclude:

Lemma 19.

For a $\epsilon$ -cnet $P\subset[0,1]\times[-\sqrt{\epsilon},\sqrt{\epsilon}]$ and $s=(0,2)$ , the weight of $G$ is $O(\log\epsilon^{-1})\cdot\mathsf{opt}_{\epsilon}$ , where $\mathsf{opt}_{\epsilon}$ denotes the minimum weight of a Steiner $(1+\epsilon)$ -ST for $P$ .

Proof.

We have shown that for every $p\in P$ , the first edge of $\pi_{ps}$ has weight $O(\epsilon)$ . Consequently, the total weight of the union of first segments of $\pi_{ps}$ over all $p\in P$ is $O(\epsilon\cdot|P|)$ . Since $P$ is a $\epsilon$ -cnet, then this is bounded by $O(\mathsf{opt}_{\epsilon})$ . By Corollary 14, the total weight of the interior edges of the paths $\pi_{ps}$ over all $p\in P$ , namely, $\mathbf{w}\left(\bigcup_{p\in P}(s_{0}(p),\ldots,s_{k-1}(p))\right)$ is bounded by $O(\log\epsilon^{-1})\cdot\mathsf{opt}_{\epsilon}$ .

Finally, we bound the total weight of the last edges of the paths $\pi_{ps}=(p,s_{0}(p),\ldots,s_{k-1}(p),s)$ for all $p\in P$ . By Observation 8, there are $O(1)$ vertical lines in $\mathcal{L}_{k-1}$ between $o=(0,0)$ and $s=(2,0)$ . By Corollary 11, we have $\mathbf{w}(\mathcal{E}_{p}\cap L_{k-1}(p))=\Theta(\sqrt{\epsilon})$ . Consequently, each piercing set $H(L_{k-1}(p))$ has $O(1)$ size. Overall, there are $O(1)$ distinct segments in $\{s_{k-1}(p)s:p\in P\}$ , and the weight of each segment is $O(1)$ . Consequently, the total weight of these segments is also $O(1)$ . Since ${\rm dist}(P,s)\geq 1$ , then $\mathbf{w}(OPT_{\epsilon})\geq 1$ , and so $\mathbf{w}(\{s_{k-1}(p)s:p\in P\})\leq O(1)\leq O(\mathbf{w}(\mathsf{OPT}_{% \epsilon}))$ . $\hfill\blacktriangleleft$

Running time.

The running time is $O(n\log n\cdot{\rm polylog}(\epsilon^{-1}))$ .

5 Shallow Trees for Points in a Tile

In this section, we prove Theorem 2. By Theorem 6 and Lemma 7, we may reduce to the problem of finding a tile-restricted $(1+\epsilon)$ -ST for points in a tile $\tau$ . Let $P$ be a set of $n$ points in the plane, $\tau\in\mathcal{T}$ be a tile, and $N_{\tau}$ an $\epsilon$ -cnet for the point set $P\cap\tau$ . We present an algorithm constructing a net-restricted ST $T$ for $N_{\tau}$ . Then we show that $T$ is a net-restricted $(1+O(\epsilon\log\epsilon^{-1}))$ -ST and its weight is $O(\mathsf{opt}\cdot\log^{2}(\epsilon^{-1}))$ , where $\mathsf{opt}$ denotes the minimum weight of a net-restricted $(1+\epsilon)$ -ST for $N_{\tau}\subset P$ ; and let $\mathsf{OPT}$ be one such a $(1+\epsilon)$ -ST.

Lemma 20 ( $\star$ ).

Let $\mathsf{opt}(\tau)$ be the weight of the lightest net-restricted $(1+\epsilon)$ -ST for $N_{\tau}\cup\{s\}$ . There is a polynomial time algorithm returns a net-restricted $(1+\epsilon\cdot\log(\epsilon^{-1}))$ ST $T$ for $N_{\tau}\cup\{s\}$ of weight $O(\log^{2}(\epsilon^{-1})\cdot\mathsf{opt}(\tau))$ .

Shallow tree construction algorithm.

Similar to Section 4, we assume that $\tau\subset[0,1]\times[-\sqrt{\epsilon},\sqrt{\epsilon}]$ and $s=(2,0)$ (see Figure 4). For each point $p\in N_{\tau}$ , we use the same set of vertical lines $L_{0}(p),L_{1}(p),\ldots$ defined in Equation 3. For each point $p$ and each integer $i$ , let $\mathcal{E}_{p}(i)$ denote the intersection of $\mathcal{E}_{ps}$ with the strip between the two lines $L_{i}(p)$ and $L_{i+1}(p)$ and $B_{i}(p)$ be the smallest axis-parallel rectangle containing $\mathcal{E}_{p}(i)$ . The point $p$ is associated with the rectangles $B_{0}(p),B_{1}(p),\ldots,B_{k}(p)$ with $k=O(\log{\epsilon^{-1}})$ . A rectangle $R$ lies on two distinct vertical lines $L_{1}$ and $L_{2}$ if two of its vertical sides are contained in $L_{1}$ and $L_{2}$ .

We construct minimum hitting sets in $k$ iterations. Starting from $i=0$ , let $\mathcal{R}_{i}$ be the set of rectangles $\{B_{i}(p):p\in P_{\tau}\}$ . Consider every pair of lines $L_{i}\in\mathcal{L}_{i},L_{i+1}\in\mathcal{L}_{i+1}$ such that there are some rectangles in $\mathcal{R}_{i}$ lying on $L_{i}$ and $L_{i+1}$ . Let $\mathcal{R}_{i}(L_{i},L_{i+1})$ be the set of rectangles in $\mathcal{R}_{i}$ lying on $L_{i}$ and $L_{i+1}$ that have nonempty intersection with $P$ . We find the minimum hitting set of $\mathcal{R}_{i}(L_{i},L_{i+1})$ from $P$ . For each point $u$ in the hitting set, let $\mathsf{iter}_{p}(u)=i$ for every $p\in P(L_{i})$ (and define $\mathsf{iter}_{p}(s):=k+1$ for all $p\in P_{\tau}$ ).

We build a graph $G$ on $P$ as follows: For every point $p\in N_{\tau}$ , let $s_{0},s_{1},\ldots s_{h}$ be a sequence of hitting points so that for $i=0,1,\ldots h$ , if $B_{i}(p)\cap P\neq\emptyset$ , then we choose an arbitrary point from the minimum hitting set of $\mathcal{R}(L_{i}(p),L_{i+1}(p))$ that hits $B_{i}(p)$ (otherwise no point is chosen from $B_{i}(p)$ . We add the path $(p,s_{0},s_{1},\ldots,s_{h},s)$ to $G$ . The path $(p,s_{0},s_{1},\ldots,s_{h},s)$ is called the candidate path of $p$ in $G$ .

For each point $p\in N_{\tau}$ , let $H(p)=(p,s_{0},s_{1},\ldots s_{h},s)$ be the candidate path of $p$ in $G$ . We prune the path $H(p)$ to eliminate some of the vertices: Initialize $H^{\prime}(p):=H(p)$ . While there exist two consecutive interior vertices $v$ and $v^{\prime}$ in $H^{\prime}(p)$ such that $\mathsf{iter}_{p}(v^{\prime})=\mathsf{iter}_{p}(v)+1$ , then let the first such pair be $v,v^{\prime}$ and eliminate $v^{\prime}$ from $H^{\prime}(p)$ . Assume that $H^{\prime}(p)=(p,s^{\prime}_{0},s^{\prime}_{1},\ldots s^{\prime}_{l},s)$ is the result of the pruning process. Observe that $H^{\prime}(p)$ is a path from $p$ to $s$ . We call $H^{\prime}(p)$ the approximate path of $p$ . Let $G^{\prime}$ be the union of paths $H^{\prime}(p)$ for all $p\in N_{\tau}$ . We return the shortest-path tree $\mathsf{SPT}(G^{\prime})$ of $G^{\prime}$ rooted at $s$ .

Lemma 21 ( $\star$ ).

Let $p$ be a point in $N_{\tau}$ , and let $\pi=(p,s_{0},s_{1},\ldots,s_{h-1},s)$ be the approximate path of $p$ in $G^{\prime}$ , we have $\mathbf{w}(\pi)\leq(1+\epsilon\log{\epsilon^{-1}})\,d(u,s)$ .

The proof of Lemma 21 is similar to the one with Steiner points. Since $\mathsf{SPT}(G^{\prime})$ is the shortest-path tree of $G^{\prime}$ , it contains $p s$ -paths of weight $(1+O(\epsilon\log\epsilon^{-1}))\,d(p,s)$ for all $p\in N_{\tau}$ .

Weight Analysis.

We show that $\mathbf{w}(G)\leq O(\mathsf{opt}\cdot\log\epsilon^{-1})$ , and then prove that $\mathbf{w}(G^{\prime})\leq O(\mathbf{w}(G)\cdot\log\epsilon^{-1})$ . Combined with the trivial bound $\mathbf{w}(\mathsf{SPT}(G^{\prime}))\leq\mathbf{w}(G^{\prime})$ , we obtain $\mathbf{w}(\mathsf{SPT}(G^{\prime}))\leq O(\mathsf{opt}\cdot\log^{2}\epsilon^{% -1}))$ , as required.

Proof Overview.

To bound the weight of $G$ , we partition its edges into two types: local edges, which connect vertices in consecutive strips, and crossing edges, which connect vertices in non-consecutive strips. The contribution of local edges can be bounded using the number of paths in $\mathsf{OPT}$ that intersect the upper strip. For crossing edges, we charge each such edge to an appropriate representative edge of $\mathsf{OPT}$ . The key observation is that if $G$ contains a long edge $e$ , then there must exist an edge $e^{\prime}\in\mathsf{OPT}$ whose length is at least $\mathbf{w}(e)$ , and we charge $e$ to this $e^{\prime}$ . Because the lengths at different scale differ by exponential factors, each edge of $\mathsf{OPT}$ can be charged only by $O(\log(1/\varepsilon))$ edges of $G$ at the same scale. Therefore, each such representative edge $e^{\prime}$ is charged at most $\log(1/\varepsilon)$ times, which yields the desired bound. The bound on the weight of $G^{\prime}$ follows from the fact that each consecutive edge can appear in at most $O(\log(1/\varepsilon))$ candidate paths in $G$ .

References

[1] Charles J Alpert, Te C Hu, Jen-Hsin Huang, Andrew B Kahng, and David Karger. Prim-dijkstra tradeoffs for improved performance-driven routing tree design. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 14(7):890–896, 2002.
[2] Baruch Awerbuch, Alan E. Baratz, and David Peleg. Cost-sensitive analysis of communication protocols. In Proc. 9th ACM Symposium on Principles of Distributed Computing, (PODC), pages 177–187, 1990. doi:10.1145/93385.93417.
[3] Baruch Awerbuch, Alan E. Baratz, and David Peleg. Efficient broadcast and light-weighted spanners. manuscript, 1991.
[4] Yehuda Ben-Shimol, Amit Dvir, and Michael Segal. SPLAST: A novel approach for multicasting in mobile wireless ad hoc networks. In Proc. 15th IEEE Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC), volume 2, pages 1011–1015, 2004. doi:10.1109/PIMRC.2004.1373851.
[5] Gengjie Chen and Evangeline F. Y. Young. SALT: provably good routing topology by a novel Steiner shallow-light tree algorithm. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., 39(6):1217–1230, 2020. doi:10.1109/TCAD.2019.2894653.
[6] Otfried Cheong and Changryeol Lee. Single-source dilation-bounded minimum spanning trees. Int. J. Comput. Geom. Appl., 23(3):159–170, 2013. doi:10.1142/S0218195913500052.
[7] Jason Cong, Andrew B. Kahng, Gabriel Robins, Majid Sarrafzadeh, and C. K. Wong. Performance-driven global routing for cell based ICs. In Proc. IEEE International Conference on Computer Design: VLSI in Computer & Processors (ICCD), pages 170–173, 1991. doi:10.1109/ICCD.1991.139874.
[8] Jason Cong, Andrew B. Kahng, Gabriel Robins, Majid Sarrafzadeh, and Chak-Kuen Wong. Provably good performance-driven global routing. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., 11(6):739–752, 1992. doi:10.1109/43.137519.
[9] Razvan Cristescu, Baltasar Beferull-Lozano, Martin Vetterli, and Roger Wattenhofer. Network correlated data gathering with explicit communication: Np-completeness and algorithms. IEEE/ACM Trans. Netw., 14(1):41–54, 2006. doi:10.1145/1133553.1133557.
[10] Ludwig Danzer and Branko Grünbaum. Intersection properties of boxes in $\mathbb{R}^{d}$ . Comb., 2(3):237–246, 1982. doi:10.1007/BF02579232.
[11] Yefim Dinitz, Michael Elkin, and Shay Solomon. Low-light trees, and tight lower bounds for Euclidean spanners. Discret. Comput. Geom., 43(4):736–783, 2010. doi:10.1007/S00454-009-9230-Y.
[12] Michael Elkin and Shay Solomon. Narrow-shallow-low-light trees with and without Steiner points. SIAM Journal on Discrete Mathematics, 25(1):181–210, 2011. doi:10.1137/090776147.
[13] Michael Elkin and Shay Solomon. Steiner shallow-light trees are exponentially lighter than spanning ones. SIAM J. Comput., 44(4):996–1025, 2015. doi:10.1137/13094791X.
[14] Stephan Held and Daniel Rotter. Shallow-light Steiner arborescences with vertex delays. In Proc. 16th Conference on Integer Programming and Combinatorial Optimization (IPCO), volume 7801 of LNCS, pages 229–241. Springer, 2013. doi:10.1007/978-3-642-36694-9_20.
[15] Dorit S. Hochbaum and Wolfgang Maass. Approximation schemes for covering and packing problems in image processing and VLSI. J. ACM, 32(1):130–136, 1985. doi:10.1145/2455.214106.
[16] Xiaohua Jia, Ding-Zhu Du, Xiao-Dong Hu, Man-Kei Lee, and Jun Gu. Optimization of wavelength assignment for QoS multicast in WDM networks. IEEE Trans. Commun., 49(2):341–350, 2001. doi:10.1109/26.905896.
[17] Ardalan Khazraei and Stephan Held. An improved approximation algorithm for the uniform cost-distance Steiner tree problem. In Proc. 18th Workshop on Approximation and Online Algorithms (WAOA), volume 12806 of LNCS, pages 189–203, 2020. doi:10.1007/978-3-030-80879-2_13.
[18] Samir Khuller, Balaji Raghavachari, and Neal E. Young. Balancing minimum spanning trees and shortest-path trees. Algorithmica, 14(4):305–321, 1995. Preliminary version at SODA 1993. doi:10.1007/BF01294129.
[19] Vachaspathi P. Kompella, Joseph Pasquale, and George C. Polyzos. Multicast routing for multimedia communication. IEEE/ACM Trans. Netw., 1(3):286–292, 1993. doi:10.1109/90.234851.
[20] Dejan Kostic and Amin Vahdat. Latency versus cost optimizations in hierarchical overlay networks. Technical report, Technical report, Duke University,(CS-2001-04), 2002.
[21] Wei Li, Yuxiao Qu, Gengjie Chen, Yuzhe Ma, and Bei Yu. Treenet: Deep point cloud embedding for routing tree construction. In Proc. 26th Asia and South Pacific Design Automation Conference (ASPDAC), pages 164–169. ACM Press, 2021. doi:10.1145/3394885.3431566.
[22] Weifa Liang and Yuzhen Liu. Online data gathering for maximizing network lifetime in sensor networks. IEEE Trans. Mob. Comput., 6(1):2–11, 2007. doi:10.1109/TMC.2007.250667.
[23] Hong Luo, Jun Luo, Yonghe Liu, and Sajal K Das. Adaptive data fusion for energy efficient routing in wireless sensor networks. IEEE Transactions on Computers, 55(10):1286–1299, 2006. doi:10.1109/TC.2006.157.
[24] Frank Nielsen. Fast stabbing of boxes in high dimensions. Theor. Comput. Sci., 246(1-2):53–72, 2000. doi:10.1016/S0304-3975(98)00336-3.
[25] David Peleg. Distributed Computing: A Locality-Sensitive Approach. SIAM, 2000. doi:10.1137/1.9780898719772.
[26] F. Sibel Salman, Joseph Cheriyan, R. Ravi, and S. Subramanian. Buy-at-bulk network design: Approximating the single-sink edge installation problem. In Proc. 8th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 619–628, 1997. URL: http://dl.acm.org/citation.cfm?id=314161.314397.
[27] Anees Shaikh and Kang Shin. Destination-driven routing for low-cost multicast. IEEE Journal on Selected Areas in Communications, 15(3):373–381, 1997. doi:10.1109/49.564135.
[28] Hanan Shpungin and Michael Segal. Near-optimal multicriteria spanner constructions in wireless ad hoc networks. IEEE/ACM Transactions on etworking, 18(6):1963–1976, 2010. doi:10.1109/TNET.2010.2053381.
[29] Shay Solomon. Euclidean Steiner shallow-light trees. J. Comput. Geom., 6(2):113–139, 2015. doi:10.20382/JOCG.V6I2A7.
[30] Jürgen Vogel, Jörg Widmer, Dirk Farin, Martin Mauve, and Wolfgang Effelsberg. Priority-based distribution trees for application-level multicast. In Proceedings of the 2nd Workshop on Network and System Support for Games (NETGAMES), pages 148–157. ACM, 2003. doi:10.1145/963900.963914.
[31] Pascal Von Rickenbach and Rogert Wattenhofer. Gathering correlated data in sensor networks. In Proceedings of the DIALM-POMC Joint Workshop on Foundations of Mobile Computing, pages 60–66, 2004. doi:10.1145/1022630.1022640.
[32] Bang Ye Wu, Kun-Mao Chao, and Chuan Yi Tang. Light graphs with small routing cost. Networks, 39(3):130–138, 2002. doi:10.1002/NET.10019.

[bib.bib1] [1] Charles J Alpert, Te C Hu, Jen-Hsin Huang, Andrew B Kahng, and David Karger. Prim-dijkstra tradeoffs for improved performance-driven routing tree design. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 14(7):890–896, 2002.

[bib.bib2] [2] Baruch Awerbuch, Alan E. Baratz, and David Peleg. Cost-sensitive analysis of communication protocols. In Proc. 9th ACM Symposium on Principles of Distributed Computing, (PODC), pages 177–187, 1990. doi:10.1145/93385.93417.

[bib.bib3] [3] Baruch Awerbuch, Alan E. Baratz, and David Peleg. Efficient broadcast and light-weighted spanners. manuscript, 1991.

[bib.bib4] [4] Yehuda Ben-Shimol, Amit Dvir, and Michael Segal. SPLAST: A novel approach for multicasting in mobile wireless ad hoc networks. In Proc. 15th IEEE Symposium on Personal, Indoor and Mobile Radio Communications (PIMRC), volume 2, pages 1011–1015, 2004. doi:10.1109/PIMRC.2004.1373851.

[bib.bib5] [5] Gengjie Chen and Evangeline F. Y. Young. SALT: provably good routing topology by a novel Steiner shallow-light tree algorithm. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., 39(6):1217–1230, 2020. doi:10.1109/TCAD.2019.2894653.

[bib.bib6] [6] Otfried Cheong and Changryeol Lee. Single-source dilation-bounded minimum spanning trees. Int. J. Comput. Geom. Appl., 23(3):159–170, 2013. doi:10.1142/S0218195913500052.

[bib.bib7] [7] Jason Cong, Andrew B. Kahng, Gabriel Robins, Majid Sarrafzadeh, and C. K. Wong. Performance-driven global routing for cell based ICs. In Proc. IEEE International Conference on Computer Design: VLSI in Computer & Processors (ICCD), pages 170–173, 1991. doi:10.1109/ICCD.1991.139874.

[bib.bib8] [8] Jason Cong, Andrew B. Kahng, Gabriel Robins, Majid Sarrafzadeh, and Chak-Kuen Wong. Provably good performance-driven global routing. IEEE Trans. Comput. Aided Des. Integr. Circuits Syst., 11(6):739–752, 1992. doi:10.1109/43.137519.

[bib.bib9] [9] Razvan Cristescu, Baltasar Beferull-Lozano, Martin Vetterli, and Roger Wattenhofer. Network correlated data gathering with explicit communication: Np-completeness and algorithms. IEEE/ACM Trans. Netw., 14(1):41–54, 2006. doi:10.1145/1133553.1133557.

[bib.bib10] [10] Ludwig Danzer and Branko Grünbaum. Intersection properties of boxes in $\mathbb{R}^{d}$ . Comb., 2(3):237–246, 1982. doi:10.1007/BF02579232.

[bib.bib11] [11] Yefim Dinitz, Michael Elkin, and Shay Solomon. Low-light trees, and tight lower bounds for Euclidean spanners. Discret. Comput. Geom., 43(4):736–783, 2010. doi:10.1007/S00454-009-9230-Y.

[bib.bib12] [12] Michael Elkin and Shay Solomon. Narrow-shallow-low-light trees with and without Steiner points. SIAM Journal on Discrete Mathematics, 25(1):181–210, 2011. doi:10.1137/090776147.

[bib.bib13] [13] Michael Elkin and Shay Solomon. Steiner shallow-light trees are exponentially lighter than spanning ones. SIAM J. Comput., 44(4):996–1025, 2015. doi:10.1137/13094791X.

[bib.bib14] [14] Stephan Held and Daniel Rotter. Shallow-light Steiner arborescences with vertex delays. In Proc. 16th Conference on Integer Programming and Combinatorial Optimization (IPCO), volume 7801 of LNCS, pages 229–241. Springer, 2013. doi:10.1007/978-3-642-36694-9_20.

[bib.bib15] [15] Dorit S. Hochbaum and Wolfgang Maass. Approximation schemes for covering and packing problems in image processing and VLSI. J. ACM, 32(1):130–136, 1985. doi:10.1145/2455.214106.

[bib.bib16] [16] Xiaohua Jia, Ding-Zhu Du, Xiao-Dong Hu, Man-Kei Lee, and Jun Gu. Optimization of wavelength assignment for QoS multicast in WDM networks. IEEE Trans. Commun., 49(2):341–350, 2001. doi:10.1109/26.905896.

[bib.bib17] [17] Ardalan Khazraei and Stephan Held. An improved approximation algorithm for the uniform cost-distance Steiner tree problem. In Proc. 18th Workshop on Approximation and Online Algorithms (WAOA), volume 12806 of LNCS, pages 189–203, 2020. doi:10.1007/978-3-030-80879-2_13.

[bib.bib18] [18] Samir Khuller, Balaji Raghavachari, and Neal E. Young. Balancing minimum spanning trees and shortest-path trees. Algorithmica, 14(4):305–321, 1995. Preliminary version at SODA 1993. doi:10.1007/BF01294129.

[bib.bib19] [19] Vachaspathi P. Kompella, Joseph Pasquale, and George C. Polyzos. Multicast routing for multimedia communication. IEEE/ACM Trans. Netw., 1(3):286–292, 1993. doi:10.1109/90.234851.

[bib.bib20] [20] Dejan Kostic and Amin Vahdat. Latency versus cost optimizations in hierarchical overlay networks. Technical report, Technical report, Duke University,(CS-2001-04), 2002.

[bib.bib21] [21] Wei Li, Yuxiao Qu, Gengjie Chen, Yuzhe Ma, and Bei Yu. Treenet: Deep point cloud embedding for routing tree construction. In Proc. 26th Asia and South Pacific Design Automation Conference (ASPDAC), pages 164–169. ACM Press, 2021. doi:10.1145/3394885.3431566.

[bib.bib22] [22] Weifa Liang and Yuzhen Liu. Online data gathering for maximizing network lifetime in sensor networks. IEEE Trans. Mob. Comput., 6(1):2–11, 2007. doi:10.1109/TMC.2007.250667.

[bib.bib23] [23] Hong Luo, Jun Luo, Yonghe Liu, and Sajal K Das. Adaptive data fusion for energy efficient routing in wireless sensor networks. IEEE Transactions on Computers, 55(10):1286–1299, 2006. doi:10.1109/TC.2006.157.

[bib.bib24] [24] Frank Nielsen. Fast stabbing of boxes in high dimensions. Theor. Comput. Sci., 246(1-2):53–72, 2000. doi:10.1016/S0304-3975(98)00336-3.

[bib.bib25] [25] David Peleg. Distributed Computing: A Locality-Sensitive Approach. SIAM, 2000. doi:10.1137/1.9780898719772.

[bib.bib26] [26] F. Sibel Salman, Joseph Cheriyan, R. Ravi, and S. Subramanian. Buy-at-bulk network design: Approximating the single-sink edge installation problem. In Proc. 8th ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 619–628, 1997. URL: http://dl.acm.org/citation.cfm?id=314161.314397.

[bib.bib27] [27] Anees Shaikh and Kang Shin. Destination-driven routing for low-cost multicast. IEEE Journal on Selected Areas in Communications, 15(3):373–381, 1997. doi:10.1109/49.564135.

[bib.bib28] [28] Hanan Shpungin and Michael Segal. Near-optimal multicriteria spanner constructions in wireless ad hoc networks. IEEE/ACM Transactions on etworking, 18(6):1963–1976, 2010. doi:10.1109/TNET.2010.2053381.

[bib.bib29] [29] Shay Solomon. Euclidean Steiner shallow-light trees. J. Comput. Geom., 6(2):113–139, 2015. doi:10.20382/JOCG.V6I2A7.

[bib.bib30] [30] Jürgen Vogel, Jörg Widmer, Dirk Farin, Martin Mauve, and Wolfgang Effelsberg. Priority-based distribution trees for application-level multicast. In Proceedings of the 2nd Workshop on Network and System Support for Games (NETGAMES), pages 148–157. ACM, 2003. doi:10.1145/963900.963914.

[bib.bib31] [31] Pascal Von Rickenbach and Rogert Wattenhofer. Gathering correlated data in sensor networks. In Proceedings of the DIALM-POMC Joint Workshop on Foundations of Mobile Computing, pages 60–66, 2004. doi:10.1145/1022630.1022640.

[bib.bib32] [32] Bang Ye Wu, Kun-Mao Chao, and Chuan Yi Tang. Light graphs with small routing cost. Networks, 39(3):130–138, 2002. doi:10.1002/NET.10019.

	$\displaystyle\|\mathrm{proj}(ab)\|\cdot\left(1+\frac{1}{3}\cdot\|\mathrm{slope}(% ab)\|^{2}\right)\nobreak\ \leq\nobreak\$	$\displaystyle d(a,b)\nobreak\ \leq\nobreak\ \|\mathrm{proj}(ab)\|\cdot\left(1+% \frac{1}{2}\cdot\|\mathrm{slope}(ab)\|^{2}\right)$		(1)
	$\displaystyle\frac{1}{3}\cdot\|\mathrm{slope}(ab)\|^{2}\nobreak\ \leq\nobreak\$	$\displaystyle\frac{\mathrm{slack}(ab)}{\|\mathrm{proj}(ab)\|}\nobreak\ \leq% \nobreak\ \frac{1}{2}\cdot\|\mathrm{slope}(ab)\|^{2}.$		(2)

Approximating Euclidean Shallow-Light Trees

Abstract

Keywords and phrases:

Funding:

Copyright and License:

2012 ACM Subject Classification:

Related Version:

DOI:

Event:

Editors:

Series and Publisher:

1 Introduction

Low-dimensional Euclidean spaces.

Approximation algorithms and hardness.

1.1 Our Contribution

Theorem 1.

Theorem 2.

Theorem 3.

1.2 Technical Overview

2 Preliminaries

Slopes, slack, and stretch.

Lemma 4 (⋆).

Lemma 5.

3 Reduction to Net Points in a Trapezoid

Theorem 6 (⋆).

Lemma 7 (⋆).

4 Steiner Shallow Trees for Points in a Tile

Steiner shallow tree construction: Overview.

Steiner shallow tree construction: Details.

Observation 8.

Corollary 9 (⋆).

Root stretch analysis.

Lemma 10.

Proof.

Corollary 11 (⋆).

Lemma 12.

Proof.

Weight analysis.

Lemma 13.

Corollary 14 (⋆).

Observation 15 (⋆).

Lemma 16.

Proof.

Corollary 17 (⋆).

Lemma 18.

Proof.

Lemma 19.

Proof.

Running time.

5 Shallow Trees for Points in a Tile

Lemma 20 (⋆).

Shallow tree construction algorithm.

Lemma 21 (⋆).

Weight Analysis.

Proof Overview.

References

Lemma 4 ( $\star$ ).

Theorem 6 ( $\star$ ).

Lemma 7 ( $\star$ ).

Corollary 9 ( $\star$ ).

Corollary 11 ( $\star$ ).

Corollary 14 ( $\star$ ).

Observation 15 ( $\star$ ).

Corollary 17 ( $\star$ ).

Lemma 20 ( $\star$ ).

Lemma 21 ( $\star$ ).