Proof. Denote \(N = \{x_1, x_2, \dots, x_s\}\) for \(s \geq 2\). Since \(T^*\) is a tree, there is a traversal of \(T^*\) that traverses every edge of \(T^*\) twice and every point in \(X\) at least once. Without loss of generality, assume this traversal goes through \(N\) in the order \(x_1, x_2, \dots, x_s\), and denote the path between \(x_i\) and \(x_{i + 1}\) by \(P(x_i, x_{i + 1}) \subseteq T^*\). Then \[\sum_{i = 1}^s w(P(x_i, x_{i + 1})) = 2w(T^*) = 2\mathop{\mathrm{MST}}(X).\] Fix \(i \in [s]\), and consider the following two cases for \(P(x_i, x_{i + 1})\).

If every edge in \(P(x_i, x_{i + 1})\) has at least one endpoint in \(B(A, \mathop{\mathrm{\operatorname{diam}}}(A))\), then by definition we have \(P(x_i, x_{i + 1}) = P(x_i, x_{i + 1}) \cap B(A, \mathop{\mathrm{\operatorname{diam}}}(A))\). By the triangle inequality, \[w\Big(P(x_i, x_{i + 1}) \cap B(A, \mathop{\mathrm{\operatorname{diam}}}(A))\Big) = w(P(x_i, x_{i + 1})) \geq \mathop{\mathrm{\mathbf{d}}}(x_i, x_{i + 1}).\]

If there exists an edge in \(P(x_i, x_{i + 1})\) for which neither endpoint lies in \(B(A, \mathop{\mathrm{\operatorname{diam}}}(A))\), let \((p, q)\) be the first such edge. Namely, there exist edges \((x_i, p_1), (p_1, p_2), \dots, (p_{k-1}, p_k), (p_k, p) \in P(x_i, x_{i + 1}) \cap B(A, \mathop{\mathrm{\operatorname{diam}}}(A))\), but \((p, q) \notin P(x_i, x_{i + 1}) \cap B(A, \mathop{\mathrm{\operatorname{diam}}}(A))\). Then \[\begin{align} &\qquad w\Big(P(x_i, x_{i + 1}) \cap B(A, \mathop{\mathrm{\operatorname{diam}}}(A))\Big) \\ &\geq \mathop{\mathrm{\mathbf{d}}}(x_i, p_1) + \sum_{j = 1}^{k - 1} \mathop{\mathrm{\mathbf{d}}}(p_j, p_{j + 1}) + \mathop{\mathrm{\mathbf{d}}}(p_k, p) \\ &\geq \mathop{\mathrm{\mathbf{d}}}(x_i, p) &&\text{by triangle inequality}\\ &\geq \mathop{\mathrm{\operatorname{diam}}}(A) &&\text{since } x_i \in A \text{ and } p \notin B(A, \mathop{\mathrm{\operatorname{diam}}}(A))\\ &\geq \mathop{\mathrm{\mathbf{d}}}(x_i, x_{i + 1}) &&\text{since } x_i, x_{i + 1} \in A. \end{align}\]

In conclusion, for every \(i \in [s]\) we have \(w\Big(P(x_i, x_{i + 1}) \cap B(A, \mathop{\mathrm{\operatorname{diam}}}(A))\Big) \geq \mathop{\mathrm{\mathbf{d}}}(x_i, x_{i + 1})\). Hence, \[\begin{align} 2 w\Big(B(A, \mathop{\mathrm{\operatorname{diam}}}(A)) \cap T^*\Big) = \sum_{i = 1}^s w\Big(P(x_i, x_{i + 1}) \cap B(A, \mathop{\mathrm{\operatorname{diam}}}(A))\Big) \geq \sum_{i = 1}^s \mathop{\mathrm{\mathbf{d}}}(x_i, x_{i + 1}) \geq s \cdot \rho, \end{align}\] where the last inequality holds since \(N\) is \(\rho\)-packing for \(A\). Rearranging concludes the proof. ◻

Proof of 2. Let \(\Psi\) be the collection of pairs of net points constructed in Line [line:WSPC]. Denote \(\Phi := \{(B(u, 2^{\mathop{\mathrm{lev}}(u)}), B(v, 2^{\mathop{\mathrm{lev}}(v)})) \colon (u, v) \in \Psi\}\). Then \(\Phi\) is a \(32\)-WSPC of \(X\) by [lemma:WSPC95doubling]. For each pair \((u, v) \in \Psi\), Assume \((p, q)\) is the edge that 1 adds to \(G\) in Line [line:U95V95ends]. Ideally, \(\mathop{\mathrm{\mathbf{d}}}(p, q)\) is a \((1 + \epsilon)\)-approximation of the distance between \(B(u, 2^{\mathop{\mathrm{lev}}(u)})\) and \(B(v, 2^{\mathop{\mathrm{lev}}(v)})\); otherwise, we consider bounding the difference between \(\mathop{\mathrm{\mathbf{d}}}(p, q)\) and \(\mathop{\mathrm{\mathbf{d}}}(B(u, 2^{\mathop{\mathrm{lev}}(u)}), B(v, 2^{\mathop{\mathrm{lev}}(v)}))\). This motivates us to define the error incurred by the pair \((u, v)\) as \[\begin{align} \mathrm{err}(u, v) := \max\left\{0, \mathop{\mathrm{\mathbf{d}}}(p, q) - (1 + \epsilon) \mathop{\mathrm{\mathbf{d}}}\left(B(u, 2^{\mathop{\mathrm{lev}}(u)}), B(v, 2^{\mathop{\mathrm{lev}}(v)})\right)\right\}. \end{align}\] Our goal is to show that \[\label{eqn:err95bound95goal} \sum_{(u, v) \in \Psi} \mathrm{err}(u, v) \leq 2^{O(\mathop{\mathrm{\operatorname{ddim}}})} \epsilon \cdot \mathop{\mathrm{MST}}(X).\tag{3}\]

Let us first assume that 3 holds, and see how it implies 2. For the \(i\)-th edge \(e_i^*\) of \(T^*\), let \((u_i, v_i) \in \Psi\) be an arbitrary pair such that \(e_i^* \in B(u_i, 2^{\mathop{\mathrm{lev}}(u_i)}) \times B(v_i, 2^{\mathop{\mathrm{lev}}(v_i)})\), and assume 1 adds \((p_i, q_i)\) to \(G\) in Line [line:U95V95ends] for \((u_i, v_i)\).

We first show that \(\{(p_i, q_i)\}_{i = 1}^{n - 1}\) is a spanning tree of \(G\). We cannot directly apply [lemma:WSPC95MST] [it:WSPC95spanning] to \(\{(p_i, q_i)\}_{i = 1}^{n - 1}\) and \(\Phi\), as \((p_i, q_i)\) is not necessarily contained in \(B(u_i, 2^{\mathop{\mathrm{lev}}(u_i)}) \times B(v_i, 2^{\mathop{\mathrm{lev}}(v_i)})\). The idea is to enlarge the radius of each pair \((B(u, 2^{\mathop{\mathrm{lev}}(u)}), B(v, 2^{\mathop{\mathrm{lev}}(v)})) \in \Phi\) by a constant factor, so that \((p_i, q_i)\) is contained in the expanded pair, and all expanded pairs still form an \(\Omega(1)\)-WSPC. Specifically, for each pair \((u, v) \in \Psi\), define the expanded pairs \(\Phi'\) as follows: If \(\mathop{\mathrm{lev}}(u) = \mathop{\mathrm{lev}}(v) = 0\), then add \((\{u\}, \{v\})\) to \(\Phi'\); otherwise, add the pair \((B(u, 2^{\mathop{\mathrm{lev}}(u) + 2}), B(v, 2^{\mathop{\mathrm{lev}}(v) + 2}))\) to \(\Phi'\). We claim that \(\Phi'\) is a \(7\)-WSPC of \(X\). Indeed, for each pair of points \((x, y) \in \binom{X}{2}\), assume \((x, y) \in B(u, 2^{\mathop{\mathrm{lev}}(u)}) \times B(v, 2^{\mathop{\mathrm{lev}}(v)})\) for some \((u, v) \in \Psi\). Then \((x, y) \in B(u, 2^{\mathop{\mathrm{lev}}(u) + 2}) \times B(v, 2^{\mathop{\mathrm{lev}}(v) + 2})\). Hence, 5 [it:WSPC95covering] is satisfied. Regarding 5 [it:WSPC95separation], for each \((u, v) \in \Psi\) where \(u, v\) are not both at level-\(0\), by [lemma:WSPC95doubling] [it:separation] we have \(\mathop{\mathrm{\mathbf{d}}}(u, v) > 66 \max\{2^{\mathop{\mathrm{lev}}(u)}, 2^{\mathop{\mathrm{lev}}(v)}\}\). Thus, \[\begin{align} \mathop{\mathrm{\mathbf{d}}}(B(u, 2^{\mathop{\mathrm{lev}}(u) + 2}), B(v, 2^{\mathop{\mathrm{lev}}(v) + 2})) \geq \mathop{\mathrm{\mathbf{d}}}(u, v) - 2^{\mathop{\mathrm{lev}}(u) + 2} - 2^{\mathop{\mathrm{lev}}(v) + 2} > 7 \max\{2^{\mathop{\mathrm{lev}}(u) + 3}, 2^{\mathop{\mathrm{lev}}(v) + 3}\}, \end{align}\] indicating each \((B(u, 2^{\mathop{\mathrm{lev}}(u) + 2}), B(v, 2^{\mathop{\mathrm{lev}}(v) + 2})) \in \Phi'\) is \(7\)-separated. Therefore, \(\Phi'\) is a \(7\)-WSPC of \(X\). By the construction of \((p_i, q_i)\) in Lines [line:low95level], [line:edge95middle95lev] and [line:edge95high95lev] and [lemma:descendants95packing95covering] [it:desc95packing], we have \((p_i, q_i) \in B(u, 2^{\mathop{\mathrm{lev}}(u) + 2}) \times B(v, 2^{\mathop{\mathrm{lev}}(v) + 2})\). Applying [lemma:WSPC95MST] [it:WSPC95spanning] to \(\{(p_i, q_i)\}_{i = 1}^{n - 1}\) and \(\Phi'\), we conclude that \(\{(p_i, q_i)\}_{i = 1}^{n - 1}\) is a spanning tree of \(G\). Therefore, \[\begin{align} \mathop{\mathrm{MST}}(G) &\leq \sum_{i = 1}^{n - 1} \mathop{\mathrm{\mathbf{d}}}(p_i, q_i) \leq \sum_{i = 1}^{n - 1} \Big((1 + \epsilon) \mathop{\mathrm{\mathbf{d}}}(B(u_i, 2^{\mathop{\mathrm{lev}}(u_i)}), B(v_i, 2^{\mathop{\mathrm{lev}}(v_i)})) + \mathrm{err}(u_i, v_i) \Big) \\ &\leq \sum_{i = 1}^{n - 1} (1 + \epsilon) w(e_i^*) + \sum_{(u, v) \in \Psi} \mathrm{err}(u, v) \leq (1 + \epsilon) \mathop{\mathrm{MST}}(X) + 2^{O(\mathop{\mathrm{\operatorname{ddim}}})} \epsilon \cdot \mathop{\mathrm{MST}}(X) \\ &= (1 + 2^{O(\mathop{\mathrm{\operatorname{ddim}}})} \epsilon) \mathop{\mathrm{MST}}(X), \end{align}\] proving 2.

In our following analysis we focus on the proof of 3 . In particular, we upper bound the error for each of the three different types of levels. Recall that \((u, v) \in \Psi\) is called a low-level (resp. middle-level, high-level) pair if \(\max\{\mathop{\mathrm{lev}}(u), \mathop{\mathrm{lev}}(v)\} < \ell^* - 10 \log(1/\epsilon)\) (resp. \(\in [\ell^* - 10 \log(1/\epsilon), \ell^* + 10 \log(1/\epsilon)]\), \(> \ell^* + 10 \log(1/\epsilon)\)).

3.2.0.1 Low levels.

Assume \((u, v) \in \Psi\) is a low-level pair, and wlog that \(\mathop{\mathrm{lev}}(u) = \max\{\mathop{\mathrm{lev}}(u), \mathop{\mathrm{lev}}(v)\} = \ell < \ell^* - 10 \log(1/\epsilon)\). We trivially bound the error of \((u, v)\) by \(\mathrm{err}(u, v) \leq 2^{\mathop{\mathrm{lev}}(u)} + 2^{\mathop{\mathrm{lev}}(v)} \leq 2^{\ell + 1}.\) Thus the total error of low level clusters can be bounded by \[\begin{align} \mathrm{Err}_{\mathrm{low}} &\leq \sum_{\ell < \ell^* - 10 \log(1/\epsilon)} \sum_{u \in N_\ell} 2^{\ell + 1} \cdot |\{v \colon (u, v) \in \Psi\}| \notag \mathrel{\overset{\textrm{\tiny(I1)}}{\leq}} 2^{O(\mathop{\mathrm{\operatorname{ddim}}})} \sum_{\ell < \ell^* - 10 \log(1/\epsilon)} 2^\ell |N_\ell| \notag\\ &= 2^{O(\mathop{\mathrm{\operatorname{ddim}}})} \sum_{\ell < \ell^* - 10 \log(1/\epsilon)} 2^{\ell / 2} \cdot 2^{\ell/2} |N_\ell| \notag \mathrel{\overset{\textrm{\tiny(I2)}}{\leq}} 2^{O(\mathop{\mathrm{\operatorname{ddim}}})} \sum_{\ell < \ell^* - 10 \log(1/\epsilon)} 2^{\ell / 2} \cdot 2^{\ell^*/2} |N_{\ell^*}| \notag\\ &\mathrel{\overset{\textrm{\tiny(I3)}}{\leq}} 2^{O(\mathop{\mathrm{\operatorname{ddim}}})} \epsilon^5 2^{\ell^*} |N_{\ell^*}| \notag \mathrel{\overset{\textrm{\tiny(I4)}}{\leq}} 2^{O(\mathop{\mathrm{\operatorname{ddim}}})} \epsilon^5 \mathop{\mathrm{MST}}(X). \label{eqn:Err95low} \end{align}\tag{4}\] In (I1), we use [it:bounded95deg] of [lemma:WSPC95doubling] to get \(|\{v \colon (u, v) \in \Psi\}| \leq 2^{O(\mathop{\mathrm{\operatorname{ddim}}})}\). In (I2) we use the definition of \(\ell^*\) in 2 . In (I3), we use that \[\sum_{\ell < \ell^* - 10 \log(1/\epsilon)} 2^{\ell/2} = O\!\left(2^{(\ell^* - 10 \log(1/\epsilon))/2}\right) = O\!\left(\epsilon^5 2^{\ell^*/2}\right),\] because the sum is geometric. (I4) follows from 3 by setting \(A = X\) and \(N = N_{\ell^*}\).

3.2.0.2 Middle levels.

Assume \((u, v) \in \Psi\) is a middle-level pair. Assume wlog that \(\mathop{\mathrm{lev}}(u) = \max\{\mathop{\mathrm{lev}}(u), \mathop{\mathrm{lev}}(v)\} = \ell\), where \(\ell^* - 10 \log(1/\epsilon) \leq \ell \leq \ell^* + 10 \log(1/\epsilon)\). Recall that \(p \in D_{\mathop{\mathrm{lev}}(u) - k}(u)\) and \(q \in D_{\mathop{\mathrm{lev}}(v) - k}(v)\), where the set of descendants \(D_{\mathop{\mathrm{lev}}(u) - k}(u)\) and \(D_{\mathop{\mathrm{lev}}(v) - k}(v)\) are either dense enough (i.e., \(k = \log(1/\epsilon)\)) or large enough (i.e., \(\max\{|D_{\mathop{\mathrm{lev}}(u) - k - 1}(u)|, |D_{\mathop{\mathrm{lev}}(v) - k - 1}(v)|\} \geq \gamma\) for some \(k < \log(1/\epsilon)\)).

If \(k = \lceil \log(1/\epsilon) \rceil\), then by [lemma:descendants95packing95covering] [it:desc95covering], every point of \(B(u, 2^{\mathop{\mathrm{lev}}(u)})\) and \(B(v, 2^{\mathop{\mathrm{lev}}(v)})\) is within distance \((\epsilon / 4) 2^{\mathop{\mathrm{lev}}(u)}\) and \((\epsilon / 4) 2^{\mathop{\mathrm{lev}}(v)}\) from a net point in \(D_{\mathop{\mathrm{lev}}(u) - k}(u)\) and \(D_{\mathop{\mathrm{lev}}(v) - k}(v)\), respectively. Let \((x^*, y^*) := \mathop{\mathrm{argmin}}_{x \in B(u, 2^{\mathop{\mathrm{lev}}(u)}), y \in B(v, 2^{\mathop{\mathrm{lev}}(v)})} \mathop{\mathrm{\mathbf{d}}}(x, y),\) i.e., \(\mathop{\mathrm{\mathbf{d}}}(x^*, y^*)\) realizes \(\mathop{\mathrm{\mathbf{d}}}(B(u, 2^{\mathop{\mathrm{lev}}(u)}), B(v, 2^{\mathop{\mathrm{lev}}(v)}))\). Let \(p^* \in D_{\mathop{\mathrm{lev}}(u) - k}(u)\) such that \(\mathop{\mathrm{\mathbf{d}}}(x^*, p^*) \leq (\epsilon/4) 2^{\mathop{\mathrm{lev}}(u)}\) and \(q^* \in D_{\mathop{\mathrm{lev}}(v) - k}(v)\) such that \(\mathop{\mathrm{\mathbf{d}}}(y^*, q^*) \leq (\epsilon/4) 2^{\mathop{\mathrm{lev}}(v)}\). Then \[\begin{align} \mathop{\mathrm{\mathbf{d}}}(p, q) &\leq \mathop{\mathrm{\mathbf{d}}}(p^*, q^*) && \text{by definition of } p, q \text{ in Line \ref{line:edge95middle95lev}}\\ &\leq \mathop{\mathrm{\mathbf{d}}}(x^*, y^*) + \mathop{\mathrm{\mathbf{d}}}(x^*, p^*) + \mathop{\mathrm{\mathbf{d}}}(y^*, q^*) && \text{by triangle inequality}\\ &\leq \mathop{\mathrm{\mathbf{d}}}(B(u, 2^{\mathop{\mathrm{lev}}(u)}), B(v, 2^{\mathop{\mathrm{lev}}(v)})) + (\epsilon/4) 2^{\mathop{\mathrm{lev}}(u)} + (\epsilon/4) 2^{\mathop{\mathrm{lev}}(v)} \\ &\leq (1 + \epsilon) \mathop{\mathrm{\mathbf{d}}}(B(u, 2^{\mathop{\mathrm{lev}}(u)}), B(v, 2^{\mathop{\mathrm{lev}}(v)})) && \text{since } \Phi \text{ is } 32\text{-WSPC}. \end{align}\] Therefore, by definition \(\mathrm{err}(u, v) = 0.\)

We now focus on the case that \(\max\{|D_{\mathop{\mathrm{lev}}(u) - k - 1}(u)|, |D_{\mathop{\mathrm{lev}}(v) - k - 1}(v)|\} > \gamma\): Similar calculation gives \[\begin{align} \mathop{\mathrm{\mathbf{d}}}(p, q) &\leq \mathop{\mathrm{\mathbf{d}}}(p^*, q^*) && \text{by definition of } p, q \text{ in Line \ref{line:edge95middle95lev}}\\ &\leq \mathop{\mathrm{\mathbf{d}}}(x^*, y^*) + \mathop{\mathrm{\mathbf{d}}}(x^*, p^*) + \mathop{\mathrm{\mathbf{d}}}(y^*, q^*) && \text{by triangle inequality}\\ &\leq \mathop{\mathrm{\mathbf{d}}}(B(u, 2^{\mathop{\mathrm{lev}}(u)}), B(v, 2^{\mathop{\mathrm{lev}}(v)})) + 2^{\mathop{\mathrm{lev}}(u) - k - 2} + 2^{\mathop{\mathrm{lev}}(v) - k - 2} \end{align}\] Therefore, \[\label{eqn:err95UV95bound} \mathrm{err}(u, v) \leq 2^{\mathop{\mathrm{lev}}(u) - k - 2} + 2^{\mathop{\mathrm{lev}}(v) - k - 2} \leq 2^{\mathop{\mathrm{lev}}(u) - k - 1} \leq 2^{\mathop{\mathrm{lev}}(v) - k},\tag{5}\] where the last inequality follows from [it:bounded95lev95diff] of [lemma:WSPC95doubling].

If \(|D_{\mathop{\mathrm{lev}}(u) - k - 1}(u)| > \gamma\), then since \(D_{\mathop{\mathrm{lev}}(u) - k - 1}(u)\) is \(2^{\mathop{\mathrm{lev}}(u) - k - 4}\)-packing for \(B(u, 2^{\mathop{\mathrm{lev}}(u) + 2})\) ([lemma:descendants95packing95covering] [it:desc95packing]), by 3 (applied to \(A = B(u, 2^{\mathop{\mathrm{lev}}(u) + 2})\) and \(N = D_{\mathop{\mathrm{lev}}(u) - k - 1}\)) we obtain \[2^{\mathop{\mathrm{lev}}(u) - k - 4} \leq \frac{2\, w(B(u, 2^{\mathop{\mathrm{lev}}(u) + 4}) \cap T^*)}{|D_{\mathop{\mathrm{lev}}(u) - k - 1}(u)|} \leq \frac{2}{\gamma} w(B(u, 2^{\mathop{\mathrm{lev}}(u) + 4}) \cap T^*).\] If \(|D_{\mathop{\mathrm{lev}}(v) - k - 1}(v)| > \gamma\), analogously we have \[2^{\mathop{\mathrm{lev}}(v) - k - 4} \leq \frac{2}{\gamma} w(B(v, 2^{\mathop{\mathrm{lev}}(v) + 4}) \cap T^*).\] We therefore conclude that \[\mathrm{err}(u, v) \leq 2^{\mathop{\mathrm{lev}}(v) - k} \leq \frac{32}{\gamma} \Big( w(B(u, 2^{\mathop{\mathrm{lev}}(u) + 4}) \cap T^*) + w(B(v, 2^{\mathop{\mathrm{lev}}(v) + 4}) \cap T^*) \Big).\]

Thus, the total error incurred by all middle level pairs is bounded by \[\begin{align} \mathrm{Err}_{\mathrm{mid}} &\leq \sum_{\substack{(u, v) \in \Psi \text{ is a} \\ \text{middle-level pair}}} \frac{32}{\gamma} \Big( w(B(u, 2^{\mathop{\mathrm{lev}}(u) + 4}) \cap T^*) + w(B(v, 2^{\mathop{\mathrm{lev}}(v) + 4}) \cap T^*) \Big). \notag \\ &\leq \sum_{\ell = \ell^* - 10 \log(1/\epsilon) - 1}^{\ell^* + 10 \log(1/\epsilon)} \sum_{u \in N_\ell} \frac{32}{\gamma} w(B(u, 2^{\ell + 4}) \cap T^*) \cdot |\{v \colon (u, v) \in \Psi\}| \notag \\ &\leq \frac{2^{O(\mathop{\mathrm{\operatorname{ddim}}})}}{\gamma} \sum_{\ell = \ell^* - 10 \log(1/\epsilon) - 1}^{\ell^* + 10 \log(1/\epsilon)} \sum_{u \in N_\ell} \sum_{e \in B(u, 2^{\ell + 4}) \cap T^*} w(e) \tag{6}\\ &= \frac{2^{O(\mathop{\mathrm{\operatorname{ddim}}})}}{\gamma} \sum_{e \in T^*} w(e) \sum_{\ell = \ell^* - 10 \log(1/\epsilon) - 1}^{\ell^* + 10 \log(1/\epsilon)} |\{u \in N_\ell \colon e \in B(u, 2^{\ell + 4})\}| \notag\\ &\leq \frac{2^{O(\mathop{\mathrm{\operatorname{ddim}}})}}{\gamma} 20 \log(1/\epsilon) \sum_{e \in T^*} w(e) \tag{7}\\ &\leq 2^{O(\mathop{\mathrm{\operatorname{ddim}}})} \epsilon\cdot \mathop{\mathrm{MST}}(X). \notag \end{align}\] In 6 , we use \(|\{v \colon (u, v) \in \Psi\}| \leq 2^{O(\mathop{\mathrm{\operatorname{ddim}}})}\) by [it:bounded95deg] of [lemma:WSPC95doubling]. In 7 , we use that for every edge \(e\) and every level \(\ell\), \(|\{u \in N_\ell \colon e \in B(u, 2^{\ell + 4})\}| \leq 2^{O(\mathop{\mathrm{\operatorname{ddim}}})}\). We explain the reason below: Denote \(e = (x, y)\); if \(u \in N_\ell\) satisfies \(e \in B(u, 2^{\ell + 4})\), then either \(\mathop{\mathrm{\mathbf{d}}}(u, x) \leq 2^{\ell + 4}\) or \(\mathop{\mathrm{\mathbf{d}}}(u, y) \leq 2^{\ell + 4}\). Equivalently, \(u \in N_\ell \cap (B(x, 2^{\ell + 4}) \cup B(y, 2^{\ell + 4}))\), so by 1 the number of such \(u\) is bounded by \(2^{O(\mathop{\mathrm{\operatorname{ddim}}})}\). The last inequality follows from our choice \(\gamma = \epsilon^{-1} \log(1/\epsilon)\).

3.2.0.3 High levels.

Assume \((u, v) \in \Psi\) is a high-level pair. Assume wlog that \(\mathop{\mathrm{lev}}(u) = \max\{\mathop{\mathrm{lev}}(u), \mathop{\mathrm{lev}}(v)\} = \ell\), where \(\ell > \ell^* + 10 \log(1/\epsilon)\). Analogous to the middle levels, we focus on the case that \(\max\{|D_{\mathop{\mathrm{lev}}(u) - k - 1}(u)|, |D_{\mathop{\mathrm{lev}}(v) - k - 1}(v)|\} > \tau_\ell\) (as \(\mathrm{err}(u, v) = 0\) in the other case). By 5 , \(\mathrm{err}(u, v) \leq 2^{\mathop{\mathrm{lev}}(v) - k}\).

If \(|D_{\mathop{\mathrm{lev}}(u) - k - 1}(u)| > \tau_\ell\), then by [lemma:descendants_packing_covering,lemma:net_size_MST] we have \[2^{\mathop{\mathrm{lev}}(u) - k - 4} \leq \frac{2}{\tau_\ell} w(B(u, 2^{\mathop{\mathrm{lev}}(u) + 4}) \cap T^*).\] Similarly, if \(|D_{\mathop{\mathrm{lev}}(v) - k - 1}(v)| > \tau_\ell\), then \[2^{\mathop{\mathrm{lev}}(v) - k - 4} \leq \frac{2}{\tau_\ell} w(B(v, 2^{\mathop{\mathrm{lev}}(v) + 4}) \cap T^*) \leq \frac{2}{\tau_{\mathop{\mathrm{lev}}(v)}} w(B(v, 2^{\mathop{\mathrm{lev}}(v) + 4}) \cap T^*).\] In conclusion, \[\begin{align} \mathrm{err}(u, v) \leq \frac{32}{\tau_{\mathop{\mathrm{lev}}(u)}} w(B(u, 2^{\mathop{\mathrm{lev}}(u) + 4}) \cap T^*) + \frac{32}{\tau_{\mathop{\mathrm{lev}}(v)}} w(B(v, 2^{\mathop{\mathrm{lev}}(v) + 4}) \cap T^*) \end{align}\]

Therefore, the total error incurred by high levels can be bounded by \[\begin{align} \mathrm{Err}_{\mathrm{high}} &\leq \sum_{\substack{(u, v) \in \Psi \text{ is a} \\ \text{high-level pair}}} \left( \frac{32}{\tau_{\mathop{\mathrm{lev}}(u)}} w(B(u, 2^{\mathop{\mathrm{lev}}(u) + 4}) \cap T^*) + \frac{32}{\tau_{\mathop{\mathrm{lev}}(v)}} w(B(v, 2^{\mathop{\mathrm{lev}}(v) + 4}) \cap T^*) \right)\\ &\leq \sum_{\ell \geq \ell^* + 10 \log(1/\epsilon)} \sum_{u \in N_\ell} \frac{32}{\tau_\ell} w(B(u, 2^{\ell + 4}) \cap T^*) \cdot |\{v \colon (u, v) \in \Psi\}| \\ &\leq 2^{O(\mathop{\mathrm{\operatorname{ddim}}})} \sum_{\ell \geq \ell^* + 10 \log(1/\epsilon)} \frac{1}{\tau_\ell} \sum_{u \in N_\ell} \sum_{e \in B(u, 2^{\ell + 4}) \cap T^*} w(e) \\ &= 2^{O(\mathop{\mathrm{\operatorname{ddim}}})} \sum_{e \in T^*} w(e) \sum_{\ell \geq \ell^* + 10 \log(1/\epsilon)} \frac{1}{\tau_\ell} |\{u \in N_\ell \colon e \in B(u, 2^{\ell + 4})\}| \\ &\leq 2^{O(\mathop{\mathrm{\operatorname{ddim}}})} \sum_{e \in T^*} w(e) \sum_{\ell \geq \ell^* + 10 \log(1/\epsilon)} \frac{1}{\tau_\ell} \\ &\leq 2^{O(\mathop{\mathrm{\operatorname{ddim}}})} \sum_{e \in T^*} w(e) \sum_{j = 10 \log(1/\epsilon)}^\infty 1.1^{-j} \\ &\leq 2^{O(\mathop{\mathrm{\operatorname{ddim}}})} \epsilon \cdot \mathop{\mathrm{MST}}(X). \end{align}\] For the last inequality, we use that \[\sum_{j = 10 \log(1/\epsilon)}^\infty 1.1^{-j} = O\!\left(1.1^{-10 \log(1/\epsilon)}\right) \leq O(\epsilon).\]

3.2.0.4 Wrapping up.

The total error is bounded by \[\begin{align} \mathrm{Err}_{\mathrm{low}} + \mathrm{Err}_{\mathrm{mid}} + \mathrm{Err}_{\mathrm{high}} \leq 2^{O(\mathop{\mathrm{\operatorname{ddim}}})} \epsilon \mathop{\mathrm{MST}}(X), \end{align}\] concluding the proof of 3 . ◻

Proof. By [lemma:net95hierarchy95construction], \(\mathcal{N}\) can be constructed in \(2^{O(\mathop{\mathrm{\operatorname{ddim}}})} n \log(n/\epsilon)\) time in Line [line:net95hierarchy]. Finding the level \(\ell^*\) takes \(O(n \log(n/\epsilon))\) time in Line [line:critical95level]. In Line [line:WSPC], \(\Psi\) can be constructed in \(2^{O(\mathop{\mathrm{\operatorname{ddim}}})} n \log(n/\epsilon)\) time by [lemma:WSPC95doubling]. Hence, the preprocessing stage (Lines [line:net95hierarchy]-[line:G95initial]) takes \(2^{O(\mathop{\mathrm{\operatorname{ddim}}})} n \log(n/\epsilon)\) time. Below we focus on the time complexity of constructing \(G\) (Lines [line:U95V95starts]-[line:U95V95ends]). We bound the time complexity of the three types of levels respectively.

3.3.0.1 Low levels.

For every low-level pair \((u, v)\), processing \((u, v)\) takes \(O(1)\) time. Therefore, the total time complexity of low levels is \(O(|\Psi|) \leq 2^{O(\mathop{\mathrm{\operatorname{ddim}}})} n \log(n / \epsilon)\).

3.3.0.2 Middle levels.

Let \((u, v) \in \Psi\) be a middle-level pair. To find \(k\) in Line [line:middle95level], the algorithm maintains \(D_{\mathop{\mathrm{lev}}(u) - j}(u)\) for each \(1 \leq j \leq \log(1/\epsilon)\) — given \(D_{\mathop{\mathrm{lev}}(u) - j + 1}(u)\), construct \(D_{\mathop{\mathrm{lev}}(u) - j}(u) := \bigcup_{x \in D_{\mathop{\mathrm{lev}}(u) - j + 1}(u)} C(x)\), until \(|D_{\mathop{\mathrm{lev}}(u) - j}(u)| > \gamma\). By [lemma:num95children95parent], \(|C(x)| \leq 2^{O(\mathop{\mathrm{\operatorname{ddim}}})}\), and the net hierarchy data structure stores pointers from \(x\) to all its children. Hence, each \(D_{\mathop{\mathrm{lev}}(u) - j}(u)\) can be constructed in \(2^{O(\mathop{\mathrm{\operatorname{ddim}}})} \gamma \log \gamma\) time, so the time complexity of finding \(k\) (Line [line:middle95level]) is \(2^{O(\mathop{\mathrm{\operatorname{ddim}}})} \gamma \log \gamma \log(1/\epsilon)\).

The time complexity of finding \((p, q) \in D_{\mathop{\mathrm{lev}}(u) - k}(u) \times D_{\mathop{\mathrm{lev}}(v) - k}(v)\) in Line [line:edge95middle95lev] is \(|D_{\mathop{\mathrm{lev}}(u) - k}(u)| \cdot |D_{\mathop{\mathrm{lev}}(v) - k}(v)| \leq \gamma \cdot |B(u, 2^{\mathop{\mathrm{lev}}(u) + 2})|\). Therefore, the total time complexity of middle levels is \[\begin{align} &\quad \sum_{\ell = \ell^* - 10 \log(1/\epsilon)}^{\ell^* + 10 \log(1/\epsilon)} \sum_{u \in N_\ell} \Big( 2^{O(\mathop{\mathrm{\operatorname{ddim}}})} \gamma \log \gamma \log(1/\epsilon) + \gamma \cdot |B(u, 2^{\mathop{\mathrm{lev}}(u) + 2})| \Big) \cdot |\{v \colon (u, v) \in \Psi\}| \\ &\leq 2^{O(\mathop{\mathrm{\operatorname{ddim}}})} \gamma \log \gamma \log(1/\epsilon) \sum_{\ell = \ell^* - 10 \log(1/\epsilon)}^{\ell^* + 10 \log(1/\epsilon)} |N_\ell| + 2^{O(\mathop{\mathrm{\operatorname{ddim}}})} \gamma \sum_{\ell = \ell^* - 10 \log(1/\epsilon)}^{\ell^* + 10 \log(1/\epsilon)} \sum_{u \in N_\ell} |B(u, 2^{\ell + 2})| \\ &\leq 2^{O(\mathop{\mathrm{\operatorname{ddim}}})} n \gamma \log \gamma \cdot 20 \log^2(1/\epsilon) + 2^{O(\mathop{\mathrm{\operatorname{ddim}}})} \gamma \sum_{\ell = \ell^* - 10 \log(1/\epsilon)}^{\ell^* + 10 \log(1/\epsilon)} \sum_{x \in X} |\{u \in N_\ell \colon \mathop{\mathrm{\mathbf{d}}}(x, u) \leq 2^{\ell + 2}\}|\\ &\leq 2^{O(\mathop{\mathrm{\operatorname{ddim}}})} n \gamma \log \gamma \cdot 20 \log^2(1/\epsilon) + 2^{O(\mathop{\mathrm{\operatorname{ddim}}})} \gamma n \cdot 20 \log(1/\epsilon) \\ &\leq 2^{O(\mathop{\mathrm{\operatorname{ddim}}})} n \epsilon^{-1} \log^4(1/\epsilon). \end{align}\] The last inequality follows from our choice of \(\gamma = \epsilon^{-1} \log(1/\epsilon)\).

3.3.0.3 High levels.

Let \((u, v)\) be a high-level pair, and assume that \(\mathop{\mathrm{lev}}(u) = \max\{\mathop{\mathrm{lev}}(u), \mathop{\mathrm{lev}}(v)\} = \ell\), where \(\ell > \ell^* + 10 \log(1/\epsilon)\). Analogous to the middle levels, the time complexity of finding \(k\) in Line [line:high95level] is \(2^{O(\mathop{\mathrm{\operatorname{ddim}}})} \tau_\ell \log \tau_\ell \log(1/\epsilon)\), and the time complexity of computing \((p, q) \in D_{\mathop{\mathrm{lev}}(u) - k}(u) \times D_{\mathop{\mathrm{lev}}(v) - k}(v)\) in Line [line:edge95high95lev] is \(|D_{\mathop{\mathrm{lev}}(u) - k}(u)| \cdot |D_{\mathop{\mathrm{lev}}(v) - k}(v)| \leq \tau_\ell^2\). Hence, the time complexity of high levels is \[\begin{align} &\quad \sum_{\ell > \ell^* + 10\log(1/\epsilon)} \sum_{u \in N_\ell} \Big( 2^{O(\mathop{\mathrm{\operatorname{ddim}}})} \tau_\ell \log \tau_\ell \log(1/\epsilon) + \tau_\ell^2 \Big) \cdot |\{v \colon (u, v) \in \Psi\}| \\ &\leq 2^{O(\mathop{\mathrm{\operatorname{ddim}}})} \log(1/\epsilon) \sum_{\ell > \ell^* + 10\log(1/\epsilon)} \tau_\ell^2 \cdot |N_\ell| \\ &= 2^{O(\mathop{\mathrm{\operatorname{ddim}}})} \log(1/\epsilon) \sum_{\ell > \ell^* + 10\log(1/\epsilon)} \frac{\tau_\ell^2}{2^{\ell/2}} \cdot 2^{\ell/2} |N_\ell| \\ &\leq 2^{O(\mathop{\mathrm{\operatorname{ddim}}})} \log(1/\epsilon) \sum_{\ell > \ell^* + 10 \log(1/\epsilon)} \frac{\tau_\ell^2}{2^{\ell/2}} \cdot 2^{\ell^*/2} |N_{\ell^*}| &&\text{by the definition of }\ell^* \\ &= 2^{O(\mathop{\mathrm{\operatorname{ddim}}})} \log(1/\epsilon) |N_{\ell^*}| \sum_{\ell > \ell^* + 10 \log(1/\epsilon)} \left(\frac{1.21}{\sqrt{2}}\right)^{\ell - \ell^*} &&\text{by the choice of } \tau_\ell \\ &\leq 2^{O(\mathop{\mathrm{\operatorname{ddim}}})} n \log(1/\epsilon). \end{align}\]

Combining the three cases above, the total complexity of constructing the graph \(G\) (Lines [line:U95V95starts]-[line:U95V95ends]) is bounded by \(2^{O(\mathop{\mathrm{\operatorname{ddim}}})} n (\log n + \epsilon^{-1} \log^4(1/\epsilon))\).

Finally, note that \(G\) has \(n\) vertices and \(m = |\Psi| = 2^{O(\mathop{\mathrm{\operatorname{ddim}}})} n \log(n/\epsilon)\) edges. The MST of \(G\) can be computed in time \(O(m + n \log n) = 2^{O(\mathop{\mathrm{\operatorname{ddim}}})} n \log(n/\epsilon)\), using Prim’s algorithms implemented with a Fibonacci Heap [19].

In conclusion the total time complexity of 1 is \(2^{O(\mathop{\mathrm{\operatorname{ddim}}})} n (\log n + \epsilon^{-1} \log^4(1/\epsilon))\). ◻

Proof of [thm:MST95alg95improved]. One can first compute an \(O(1)\)-approximation of the doubling dimension \(\mathop{\mathrm{\operatorname{ddim}}}= \mathop{\mathrm{\operatorname{ddim}}}(X)\) in time \(2^{O(\mathop{\mathrm{\operatorname{ddim}}})} n \log(n/\epsilon)\) using [lemma:ddim95apx]. Then run 1 with parameter \(\epsilon' = \epsilon/2^{O(\mathop{\mathrm{\operatorname{ddim}}})}\). By 2, the algorithm returns a \((1 + \epsilon)\)-approximate MST. By 4, the time complexity is \[\begin{align} 2^{O(\mathop{\mathrm{\operatorname{ddim}}})} n (\log n + \epsilon^{-1} 2^{O(\mathop{\mathrm{\operatorname{ddim}}})} \log^4(2^{O(\mathop{\mathrm{\operatorname{ddim}}})}/\epsilon)) = 2^{O(\mathop{\mathrm{\operatorname{ddim}}})} n (\log n + \epsilon^{-1} \log^4(1/\epsilon)). \end{align}\] ◻

Proof. Fix a vertex \(p\) and let its neighbors in \(T\) be \(q_1,\dots,q_k\), ordered so that \[r_i := \mathop{\mathrm{\mathbf{d}}}(p,q_i), \qquad r_1 \le r_2 \le \dots \le r_k.\]

We claim the following separation property: For every \(i<j\), \[\mathop{\mathrm{\mathbf{d}}}(q_i,q_j) \ge r_j.\] Indeed, if \(\mathop{\mathrm{\mathbf{d}}}(q_i,q_j) < r_j\), then replacing the edge \(p q_j\) (of length \(r_j\)) by the edge \(q_i q_j\) would strictly decrease the total weight of the tree, contradicting minimality of the MST.

Next, we partition the neighbors of \(p\) into geometric scales. Fix a constant \(C \ge 2\). For each integer \(t\), define \[S_t := \{\, i : C^t \le r_i < C^{t+1} \,\}.\]

We will bound the size of each \(S_t\). Let \(i<j\) both lie in \(S_t\). Then \(r_j \ge C^t\). By the separation property, \[\mathop{\mathrm{\mathbf{d}}}(q_i,q_j) \ge r_j \ge C^t.\] Moreover, every \(q_i\) with \(i \in S_t\) lies in the ball \(B(p, C^{t+1})\). Thus, the points \(\{q_i : i \in S_t\} \subseteq B(p,C^{t+1})\) form a set that is \(C_t\)-packing and has diameter at most \(2\cdot C^{t+1}\). By Lemma 1 we therefore get that the size of \(S_t\) is bounded by \(|S_t| = |\{q_i : i \in S_t\}| = 2^{O(\mathop{\mathrm{\operatorname{ddim}}})}\).

Finally, note that we can bound the total number of scales as follows: The smallest radius is \(r_1\) and the largest is \(r_k\). The number of indices \(t\) for which \(S_t\) is nonempty is at most \[O\!\left( \log_C \frac{r_k}{r_1} \right) = O(\log \Delta).\]

Summing over all scales, we obtain \[\deg_T(p) = \sum_t |S_t| \le 2^{O(\mathop{\mathrm{\operatorname{ddim}}})} \cdot O(\log \Delta),\] as claimed. ◻

Proof. Fix \(n \in \mathbb{N}\). We construct a point set \(X \subset \mathbb{R}^{2n}\) as follows. Let \(o = (0,\dots,0)\) be the origin. For every \(i \in \{1,\dots,n\}\) define four points \[a_i^+ = 2^i e_{2i-1}, \qquad a_i^- = -2^i e_{2i-1}, \qquad b_i^+ = 2^i e_{2i}, \qquad b_i^- = -2^i e_{2i},\] where \(e_j\) denotes the \(j\)-th standard basis vector. Let \[X = \{o\} \cup \{a_i^+,a_i^-,b_i^+,b_i^- : i=1,\dots,n\}.\] Thus \(|X| = 4n+1\).

First, we claim that the doubling dimension is bounded, i.e., \(\mathop{\mathrm{\operatorname{ddim}}}(X)=O(1)\). Observe that all points in \(\{a_i^\pm,b_i^\pm\}\) have distance \(2^i\) from the origin, so the points occur at exponentially separated scales. Consider the ball \(B(o,2^k)\). It contains the origin and all points \(\{a_i^\pm,b_i^\pm\}\) with \(i \le k\). The four points \(\{a_k^+,a_k^-,b_k^+,b_k^-\}\) lie on the sphere of radius \(2^k\) and have pairwise distance at least \(2^k\sqrt{2}\). Hence any ball of radius \(2^{k-1}\) can contain at most one of them, so at least four such balls are required to cover them. All remaining points lie inside \(B(o,2^{k-1})\) and can therefore be covered by a constant number of balls of radius \(2^{k-1}\). Consequently \(B(o,2^k)\) can be covered by a constant number of balls of radius \(2^{k-1}\). A similar argument applies to balls centered at other points of \(X\), so the doubling constant is bounded by a universal constant. Therefore \(\mathop{\mathrm{\operatorname{ddim}}}(X)=O(1)\).

Next, we show that the degree of the MST is unbounded. For every \(i\) we have \[\mathop{\mathrm{\mathbf{d}}}(o,a_i^\pm) = 2^i, \qquad \mathop{\mathrm{\mathbf{d}}}(o,b_i^\pm) = 2^i.\] Moreover, \[\mathop{\mathrm{\mathbf{d}}}(a_i^+,a_i^-) = 2^{i+1}, \qquad \mathop{\mathrm{\mathbf{d}}}(a_i^\pm,b_i^\pm) = 2^i\sqrt{2},\] and distances between points corresponding to different indices \(i<j\) are at least \(2^j\).

Thus for every point \(p \in X \setminus \{o\}\) the closest point in \(X\) is the origin. By the cut property of minimum spanning trees, the edge \((o,p)\) must belong to every minimum spanning tree. Therefore the minimum spanning tree of \(X\) is the star centered at \(o\).

Since \(|X|-1 = 4n\), the degree of \(o\) in the minimum spanning tree is \(4n\), while all other vertices have degree \(1\). Hence the maximum degree of the minimum spanning tree is \(4n = \Omega(n)\). Since \(n\) was arbitrary while \(\mathop{\mathrm{\operatorname{ddim}}}(X)=O(1)\), the maximum degree of a minimum spanning tree in metrics of bounded doubling dimension is unbounded. ◻

Proof. Let \(T^*\) be the MST of \(X\). By [lemma:MST95degree], the maximum degree of \(T^*\) is \(2^{O(\mathop{\mathrm{\operatorname{ddim}}})} \log \Delta\). Fix a threshold \(\tau = 2^{O(\mathop{\mathrm{\operatorname{ddim}}})} \log(1/\epsilon)\). Say a point \(x \in X\) is heavy w.r.t. \(T^*\), if \(\deg_{T^*}(x) \geq \tau\), and light otherwise. Denote by \(H_{T^*} \subseteq X\) the set of heavy points w.r.t. \(T^*\). The overall plan is to start with \(T^*\), and modify the edge connection around each heavy point \(x \in H_{T^*}\) to make it light. The final spanning tree will be the desired \(T\).

We treat \(T^*\) as a rooted tree. Initially, all points in \(H_{T^*}\) is marked as active. At each step, we find the lowest level active (heavy) point, denoted by \(x \in H_{T^*}\). Denote \(\mathop{\mathrm{wdeg}}_{T^*}(x) := \sum_{(x, y) \in E(T^*)} \mathop{\mathrm{\mathbf{d}}}(x, y)\) as the weighted degree of \(x\). For \(1 \leq \ell \leq \log( \mathop{\mathrm{wdeg}}_{T^*}(x))\), denote the level \(\ell\) neighbor of \(x\) by \(N_{T^*}^\ell(x) := \{y \in B(x, 2^\ell) \setminus B(x, 2^{\ell - 1}) \colon (x, y) \in E(T^*)\}\). By [lemma:MST95degree], we have \(|N_{T^*}^\ell(x)| \leq 2^{O(\mathop{\mathrm{\operatorname{ddim}}})}\). Let \(p(x)\) be the parent of \(x\) on \(T^*\). We do the following modification to the edges incident to \(x\):

(1) For every \(1\leq \ell \leq \log(\epsilon \mathop{\mathrm{wdeg}}_{T^*}(x))\), remove all edges \(\{(x, y) \colon y \in N_{T^*}^\ell(x) \setminus \{p(x)\}\}\) from the current tree, pick an arbitrary \(c_\ell \in N_{T^*}^\ell(x) \setminus \{p(x)\}\), and add edges \(\{(c_\ell, y) \colon y \in N_{T^*}^\ell(x) \setminus \{p(x)\}\}\). Add a path \((x, c_1, c_2, \dots, c_{\log(\epsilon \mathop{\mathrm{wdeg}}_{T^*}(x))})\).⁶

(2) For \(\ell > \log(\epsilon \mathop{\mathrm{wdeg}}_{T^*}(x))\), keep the edges \(\{(x, y) \colon y \in N_{T^*}^\ell(x)\}\) untouched.

(3) Keep the edge \((x, p(x))\) untouched.

(4) Mark \(x\) as inactive.

Roughly speaking, we remove all “low level” edges incident to \(x\), and add an arbitrary star at each level (whose center is guaranteed not to be \(p(x)\)). To make everything connected, we then add a path through the star centers. Crucially, we never touch \(p(x)\) and thus all modifications are made between \(x\) and its children on \(T^*\). This ensures that the degree of \(p(x)\) stays unchanged during the modification around \(x\).

After all heavy points in \(H_T^*\) are marked as inactive, we terminate the procedure and denote the resulting tree by \(T\). Before we show the degree and weight bounds for \(T\), let us first check that \(T\) is indeed a spanning tree of \(X\). This follows immediately as our algorithm maintains connectivity, and does not change the total number of edges.

We now show that the maximum degree of \(T\) is at most \(2^{O(\mathop{\mathrm{\operatorname{ddim}}})} \log(1/\epsilon)\). We first state the following observation, which follows directly from our procedure:

We prove \(\deg_T(x) \leq 2^{O(\mathop{\mathrm{\operatorname{ddim}}})} \log(1/\epsilon)\) for every \(x \in X\). If \(x \notin H_{T^*}\), then by 1, \(\deg_T(x)\) changes only at the step when \(p(x)\) becomes inactive. By our procedure, \(\deg_T(x)\) increases only if \(x\) is the center of the star at a certain level \(\ell\). In this case, \(x\) is incident to \(|N_{T^*}^\ell(p(x))| - 1\) edges of the star and \(2\) edges of the path. Thus \[\deg_T(x) \leq \deg_{T^*}(x) + (|N_{T^*}^\ell(p(x))| + 1) \leq \tau + 2^{O(\mathop{\mathrm{\operatorname{ddim}}})} + 1 = \log (\frac{1}{\epsilon})2^{O(\mathop{\mathrm{\operatorname{ddim}}})}.\] If \(x \in H_{T^*}\), then by 1, \(\deg_T(x)\) changes at the steps when \(x\) or \(p(x)\) becomes inactive. At the step when \(x\) becomes inactive, edges are modified in such a way that \(x\) is only adjacent to (i) all point in \(N_{T^*}^\ell(x)\) for \(\ell > \log(\epsilon \mathop{\mathrm{wdeg}}_{T^*}(x))\), (ii) its parent \(p(x)\) and (iii) the center \(c_1\) of the first level star. Hence for this step, \[\begin{align} \deg_T(x) \leq \sum_{\ell = \log(\epsilon \mathop{\mathrm{wdeg}}_{T^*}(x))}^{\log(\mathop{\mathrm{wdeg}}_{T^*}(x))} |N_{T^*}^\ell(x)| + 2 \leq 2^{O(\mathop{\mathrm{\operatorname{ddim}}})} \log\frac{1}{\epsilon} + 2. \end{align}\] At the stage when \(p(x)\) becomes inactive, \(\deg_T(x)\) increases by at most \(2^{O(\mathop{\mathrm{\operatorname{ddim}}})} + 1\) (if it is selected as a star center \(c_\ell\)). Therefore, the final degree of \(x\) in \(T\) is bounded by \[\begin{align} \deg_T(x) \leq 2^{O(\mathop{\mathrm{\operatorname{ddim}}})} \log\frac{1}{\epsilon} + 2 + 2^{O(\mathop{\mathrm{\operatorname{ddim}}})} + 1 \leq 2^{O(\mathop{\mathrm{\operatorname{ddim}}})} \log\frac{1}{\epsilon} + 3. \end{align}\] We thus conclude that the maximum degree of \(T\) is \(2^{O(\mathop{\mathrm{\operatorname{ddim}}})} \log(1/\epsilon)\).

We next prove that \(T\) is a \((1 + 2^{O(\mathop{\mathrm{\operatorname{ddim}}})} \epsilon)\)-approximate MST of \(X\). For this purpose, let us bound the increase of edge weight at each step. Assume the current step marks a point \(x \in H_{T^*}\) as inactive. Recall that the newly added edges are (i) edges in the star \(\{(c_\ell, y) \colon y \in N_{T^*}^\ell(x) \setminus \{p(x)\}\}\) for \(\ell \leq \log(\epsilon \mathop{\mathrm{wdeg}}_{T^*}(x))\) and (ii) edges in the path \((x, c_1, c_2, \dots, c_{\log(\epsilon \mathop{\mathrm{wdeg}}_{T^*}(x))})\). The total length of the newly added edges is \[\begin{align} &\qquad \sum_{\ell = 1}^{\log(\epsilon \mathop{\mathrm{wdeg}}_{T^*}(x))} \sum_{y \in N_{T^*}^\ell(x) \setminus \{p(x)\}} \mathop{\mathrm{\mathbf{d}}}(y, c_\ell) + \sum_{\ell = 0}^{\log(\epsilon \mathop{\mathrm{wdeg}}_{T^*}(x))} \mathop{\mathrm{\mathbf{d}}}(c_\ell, c_{\ell + 1}) \\ & \leq \sum_{\ell = 1}^{\log(\epsilon \mathop{\mathrm{wdeg}}_{T^*}(x))} 2^{O(\mathop{\mathrm{\operatorname{ddim}}})} \cdot 2 \cdot 2^\ell + \sum_{\ell = 0}^{\log(\epsilon \mathop{\mathrm{wdeg}}_{T^*}(x))} 2 \cdot 2^{\ell + 1} \\ & \leq 2^{O(\mathop{\mathrm{\operatorname{ddim}}})} \epsilon \mathop{\mathrm{wdeg}}_{T^*}(x). \end{align}\] Summing the increased length up over all steps, we have \[\begin{align} w(T) - w(T^*) \leq \sum_{x \in H_{T^*}} 2^{O(\mathop{\mathrm{\operatorname{ddim}}})} \epsilon \mathop{\mathrm{wdeg}}_{T^*}(x) \leq 2^{O(\mathop{\mathrm{\operatorname{ddim}}})} \epsilon \sum_{x \in X} \mathop{\mathrm{wdeg}}_{T^*}(x) \leq 2^{O(\mathop{\mathrm{\operatorname{ddim}}})} \epsilon \cdot w(T^*). \end{align}\] Therefore, \(w(T) \leq (1 + 2^{O(\mathop{\mathrm{\operatorname{ddim}}})} \epsilon) w(T^*) = (1 + 2^{O(\mathop{\mathrm{\operatorname{ddim}}})} \epsilon) \mathop{\mathrm{MST}}(X)\). Rescaling \(\epsilon\) concludes the proof. ◻

Proof. We first show that \(D_k(u) \subseteq B(u, 2^{\ell + 2})\). To this end, we inductively prove that for every \(k < \ell\), \[\begin{align} D_k(u) \subseteq B\left(u, \sum_{j = k + 2}^{\ell + 1} 2^j\right) \subseteq B(u, 2^{\ell + 2}). \label{eqn:descendant95is95subset} \end{align}\tag{8}\] For \(k = \ell - 1\), we have \(D_{\ell - 1}(u) = C(u) \subseteq B(u, 2^{\ell + 1})\) by [def:children,def:descendants]. Now assume 8 holds for \(k < \ell\). For every \(v \in D_{k - 1}(u)\), by 4, there exists \(w \in D_k(u)\), such that \(v\) is a child of \(w\). Hence, \[\begin{align} \mathop{\mathrm{\mathbf{d}}}(v, u) \leq \mathop{\mathrm{\mathbf{d}}}(v, w) + \mathop{\mathrm{\mathbf{d}}}(w, u) \leq 2^{k + 1} + \sum_{j = k + 2}^{\ell - 1} 2^j = \sum_{j = k + 1}^{\ell - 1} 2^j. \end{align}\] Therefore, \(D_{k - 1}(u) \subseteq B(u, \sum_{j = k + 1}^{\ell - 1} 2^j)\), concluding the induction. Finally, since \(N_k\) is \(2^{k - 3}\)-packing (1 and [lemma:net95hierarchy95construction]), \(D_k(u)\) is also \(2^{k - 3}\)-packing for \(B(u, 2^{\ell + 2})\).

For [it:desc95covering], since \(N_k\) is \(2^{k - 2}\)-covering for \(X\), there exists \(v \in N_k\), such that \(\mathop{\mathrm{\mathbf{d}}}(x, v) \leq 2^{k - 2}\). It remains to prove that \(v \in D_k(u)\): Denote \(v_k := v\); for \(k + 1 \leq j \leq \ell - 1\), denote \(v_j \in N_j\) as the level-\(j\) net point closest to \(v_{j - 1}\). Then \(\mathop{\mathrm{\mathbf{d}}}(v_j, v_{j - 1}) \leq 2^{j - 2}\), and thus \(v_{j - 1} \in C(v_j)\). Note that \[\begin{align} \mathop{\mathrm{\mathbf{d}}}(v_{\ell - 1}, u) \leq \mathop{\mathrm{\mathbf{d}}}(u, x) + \mathop{\mathrm{\mathbf{d}}}(x, v) + \sum_{j = k + 1}^{\ell - 1} \mathop{\mathrm{\mathbf{d}}}(v_{j - 1}, v_j) \leq 2^{\ell} + 2^{k - 2} + \sum_{j = k + 1}^{\ell - 1} 2^{j -2} \leq 2^\ell + 2^{\ell - 2} < 2^{\ell + 1}. \end{align}\] Therefore, \(v_{\ell - 1} \in C(u)\), and consequently, \(v \in D_k(u)\). ◻

Proof. By [it:desc95packing] of [lemma:descendants95packing95covering], \(C(u)\) is \(2^{\ell - 4}\)-packing for \(B(u, 2^{\ell + 2})\). Hence by 1, \(|C(u)| \leq 2^{O(\mathop{\mathrm{\operatorname{ddim}}})}\).

Assume \(u\) is a child of \(u'\). Then by 3, \(\mathop{\mathrm{\mathbf{d}}}(u, u') \leq 2^{\mathop{\mathrm{lev}}(u') + 1} = 2^{\ell + 2}\). Since \(u' \in N_{\ell + 1}\), which is \(2^{\ell - 2}\)-packing, the number of such \(u'\), by 1, is at most \(2^{O(\mathop{\mathrm{\operatorname{ddim}}})}\). ◻

Proof. For the purpose of construction, each net point \(u \in N_\ell\) maintains, apart from its children \(C(u)\), two auxiliary sets: (i) the group \(G(u) := \{x \in X \colon u = \mathop{\mathrm{argmin}}_{u' \in N_\ell} \mathop{\mathrm{\mathbf{d}}}(x, u')\}\) (i.e., \(G(u)\) contains all points \(x \in X\) such that \(u\) is the point in \(N_\ell\) closest to \(x\), breaking tie arbitrarily), and (ii) the neighbors \(H(u) := B(u, 2^{\ell + 2}) \cap N_\ell\), i.e., all net points in \(N_\ell\) within distance \(2^{\ell + 2}\) from \(u\).

The data structure is constructed inductively in a top-down manner. At level \(L\), \(N_L\) contains one arbitrary point \(u \in X\). Its group and neighbors, by definition, are \(G(u) = X\) and \(H(u) = \{u\}\), respectively. Assume \(N_{\ell + 1}\) together with \(\{G(u)\}_{u \in N_{\ell + 1}}\) and \(\{H(u)\}_{u \in N_{\ell + 1}}\) is already constructed, we construct \(N_\ell\), \(\{C(u)\}_{u \in N_{\ell + 1}}\), \(\{G(v)\}_{v \in N_{\ell}}\) and \(\{H(v)\}_{v \in N_{\ell}}\) by the following steps.

6.1.0.1 Step 1: Construct nets within each group.

For each \(u \in N_{\ell + 1}\), construct a \(2^{\ell - 3}\)-net \(N_\ell'(u)\) of \(G(u)\), such that \(u \in N_\ell'(u)\). Denote \(N_\ell'\) as the union of all these nets, i.e., \[N_\ell' := \bigcup_{u \in N_{\ell + 1}} N_\ell'(u).\]

In particular, each \(N_\ell'(u) \subseteq G(u)\) can be constructed greedily in time \(|N_\ell'(u)| \cdot |G(u)|\). Hence, the total complexity of constructing \(N_\ell'\) is \[\begin{align} \sum_{u \in N_{\ell + 1}} |N_\ell'(u)| \cdot |G(u)| \leq \sum_{u \in N_{\ell + 1}} 2^{O(\mathop{\mathrm{\operatorname{ddim}}})} \cdot |G(u)| = 2^{O(\mathop{\mathrm{\operatorname{ddim}}})} n. \end{align}\] In the first inequality, we use that \(|N_\ell'(u)| \leq 2^{O(\mathop{\mathrm{\operatorname{ddim}}})}\), this is because \(N_\ell'(u)\) is \(2^{\ell - 3}\)-packing for \(G(u)\) and \(\mathop{\mathrm{\operatorname{diam}}}(G(u)) \leq 2^{\ell - 1} + 2^{\ell - 1} = 2^\ell\).

6.1.0.2 Step 2: Construct \(N_\ell\) by eliminating non-packing points in \(N_\ell'\).

\(N_\ell'\) is already \(2^{\ell - 3}\)-covering for \(X\) by construction, but may not be \(2^{\ell - 3}\)-packing, as two net points from different groups can be very close to each other. More concretely, if \(v, v' \in N_\ell'\) satisfies \(\mathop{\mathrm{\mathbf{d}}}(v, v') < 2^{\ell - 3}\), and assume \(v \in N_\ell'(u)\) and \(v' \in N_\ell'(u')\), we then have \[\begin{align} \mathop{\mathrm{\mathbf{d}}}(u, u') \leq \mathop{\mathrm{\mathbf{d}}}(v, v') + \mathop{\mathrm{\mathbf{d}}}(v, u) + \mathop{\mathrm{\mathbf{d}}}(v', u') \leq 2^{\ell - 3} + 2^{\ell - 1} + 2^{\ell - 1} < 2^{\ell + 3}. \end{align}\] Equivalently, \(u' \in H(u)\) and \(v' \in \bigcup_{u' \in H(u)} N_\ell'(u')\). We thus have the following procedure to eliminate the close points in \(N_\ell'\):

Let \(\sigma\) be an arbitrary ordering over \(N_\ell'\), such that for \(u \in N_{\ell + 1} \subseteq N_\ell'\), \(\sigma(u) \leq |N_{\ell + 1}|\). Initially, let \(N_\ell = N_\ell'\). Each time we pick one unexplored point \(v \in N_\ell\) with the smallest order \(\sigma(v)\), and find \(u \in N_{\ell + 1}\) such that \(v \in N_\ell'(u)\). Then, for each point \(v' \in \bigcup_{u' \in H(u)} N_\ell'(u')\), if \(\mathop{\mathrm{\mathbf{d}}}(v, v') < 2^{\ell - 3}\) and \(\sigma(v) < \sigma(v')\), delete \(v'\) from \(N_\ell\). The remaining set after all points are explored is defined as the level-\(\ell\) net \(N_\ell\).

Note that \(|H(u)| \leq 2^{O(\mathop{\mathrm{\operatorname{ddim}}})}\) and \(|N_\ell'(u')| \leq 2^{O(\mathop{\mathrm{\operatorname{ddim}}})}\) for each \(u' \in H(u)\), hence the time complexity of exploring each \(v \in N_\ell'\) is \(2^{O(\mathop{\mathrm{\operatorname{ddim}}})}\). Therefore, the time complexity of the above elimination procedure is \(2^{O(\mathop{\mathrm{\operatorname{ddim}}})} |N_\ell'| \leq 2^{O(\mathop{\mathrm{\operatorname{ddim}}})} n\).

We claim that \(N_\ell\) is \(2^{\ell - 3}\)-packing and \(2^{\ell - 2}\)-covering for \(X\). Indeed, the packing property follows directly from the way \(N_\ell\) is constructed. Regarding the covering property, let us fix a point \(x \in X\) and prove that \(\mathop{\mathrm{\mathbf{d}}}(x, N_\ell) \leq 2^{\ell - 2}\). Let \(v \in N_\ell'\) be the closest point to \(x\) in \(N_\ell'\). Recall that \(N_\ell'\) is \(2^{\ell - 3}\)-packing, so \(\mathop{\mathrm{\mathbf{d}}}(x, v) \leq 2^{\ell - 3}\). If \(v \in N_{\ell}\), then we already have \(\mathop{\mathrm{\mathbf{d}}}(x, N_\ell) \leq \mathop{\mathrm{\mathbf{d}}}(x, v) \leq 2^{\ell - 3}\). If \(v \notin N_\ell\), then it must be deleted during the aforementioned procedure. Assume \(v\) is deleted while the procedure is exploring \(v'\). We then have \(\mathop{\mathrm{\mathbf{d}}}(v, v') < 2^{\ell- 3}\), and \(v'\) must be contained in \(N_\ell\). Therefore, \(\mathop{\mathrm{\mathbf{d}}}(x, N_\ell) \leq \mathop{\mathrm{\mathbf{d}}}(x, v') \leq \mathop{\mathrm{\mathbf{d}}}(x, v) + \mathop{\mathrm{\mathbf{d}}}(v, v') \leq 2^{\ell - 2}\). In conclusion, \(N_\ell\) is \(2^{\ell - 3}\)-packing and \(2^{\ell - 2}\)-covering for \(X\).

6.1.0.3 Step 3: Maintain the children \(C(u)\) for each \(u \in N_{\ell + 1}\).

Recall that for each \(u \in N_{\ell + 1}\), its children are \(C(u) = \{v \in N_\ell \colon \mathop{\mathrm{\mathbf{d}}}(u, v) \leq 2^{\ell + 2}\}\). Hence, it suffices to find for each \(v \in N_\ell\) all \(u' \in N_{\ell + 1}\) with \(\mathop{\mathrm{\mathbf{d}}}(v, u') \leq 2^{\ell + 2}\), and add \(v\) to \(C(u')\). Let \(u \in N_{\ell + 1}\) be such that \(v \in N_\ell'(u) \subseteq G(u)\), we then have \[\begin{align} \mathop{\mathrm{\mathbf{d}}}(u, u') \leq \mathop{\mathrm{\mathbf{d}}}(u, v) + \mathop{\mathrm{\mathbf{d}}}(u', v) \leq 2^{\ell - 1} + 2^{\ell + 2} < 2^{\ell + 3}, \end{align}\] implying \(u' \in H(u)\). We thus have the following procedure:

For each \(v \in N_\ell\), find \(u \in N_{\ell + 1}\) such that \(v \in G(u)\). Enumerate all \(u' \in H(u)\); if \(\mathop{\mathrm{\mathbf{d}}}(u', v) \leq 2^{\ell + 2}\), then add \(v\) to \(C(u')\).

Since \(|H(u)| \leq 2^{O(\mathop{\mathrm{\operatorname{ddim}}})}\), the total time complexity is \(2^{O(\mathop{\mathrm{\operatorname{ddim}}})} |N_\ell| \leq 2^{O(\mathop{\mathrm{\operatorname{ddim}}})} n\).

6.1.0.4 Step 4: Maintain the grouping \(\{G(v)\}_{v \in N_\ell}\).

It suffices to find for every \(x \in X\) its closest point \(v\) in \(N_\ell\), and add \(x\) to \(G(v)\). To this end, let \(u \in N_{\ell + 1}\) be such that \(x \in G(u)\). Then \[\begin{align} \mathop{\mathrm{\mathbf{d}}}(u, v) \leq \mathop{\mathrm{\mathbf{d}}}(x, u) + \mathop{\mathrm{\mathbf{d}}}(x, v) \leq 2^{\ell - 1} + 2^{\ell - 2} < 2^{\ell + 2}. \end{align}\] This implies that \(v \in C(u)\). We thus have the following procedure:

For each \(x \in X\), find \(u \in N_{\ell + 1}\) such that \(x \in G(u)\). Find the point in \(C(u)\) closest to \(x\), denoted by \(v\). Add \(x\) to \(G(v)\).

By [lemma:num95children95parent], \(|C(u)| \leq 2^{O(\mathop{\mathrm{\operatorname{ddim}}})}\), so the time complexity is \(2^{O(\mathop{\mathrm{\operatorname{ddim}}})} n\).

6.1.0.5 Step 5: Maintain the neighbors \(\{H(v)\}_{v \in N_\ell}\).

Recall that \(H(v) = \{v' \in N_\ell \colon \mathop{\mathrm{\mathbf{d}}}(v, v') \leq 2^{\ell + 2}\}\) for each \(v \in N_\ell\). Consider \(v \in N_\ell\) and \(v' \in H(v)\), and denote \(u, u' \in N_{\ell + 1}\) to be such that \(v \in G(u)\) and \(v' \in G(u')\), respectively. Then \[\begin{align} \mathop{\mathrm{\mathbf{d}}}(u, u') \leq \mathop{\mathrm{\mathbf{d}}}(v, v') + \mathop{\mathrm{\mathbf{d}}}(u, v) + \mathop{\mathrm{\mathbf{d}}}(u', v') \leq 2^{\ell + 2} + 2^{\ell - 1} + 2^{\ell - 1} < 2^{\ell + 3}. \end{align}\] Hence, \(u' \in H(u)\) and \(v' \in \bigcup_{u' \in H(u)} N_\ell'(u')\). We thus have the following procedure:

For each \(v \in N_\ell\), find \(u \in N_{\ell + 1}\) such that \(v \in G(u)\). Enumerate \(v' \in \bigcup_{u' \in H(u)} N_\ell'(u')\); if \(\mathop{\mathrm{\mathbf{d}}}(v, v') \leq 2^{\ell + 2}\), then add \(v'\) to \(H(v)\).

Since \(|H(u)| \leq 2^{O(\mathop{\mathrm{\operatorname{ddim}}})}\) and \(|N_\ell'(u')| \leq 2^{O(\mathop{\mathrm{\operatorname{ddim}}})}\) for each \(u' \in H(u)\), the time complexity is \(2^{O(\mathop{\mathrm{\operatorname{ddim}}})} |N_\ell| \leq 2^{O(\mathop{\mathrm{\operatorname{ddim}}})} n\).

6.1.0.6 Wrapping up.

The time complexity of constructing each level (including \(N_\ell\), \(\{C(u)\}_{u \in N_{\ell + 1}}\), \(\{G(v)\}_{v \in N_{\ell}}\) and \(\{H(v)\}_{v \in N_{\ell}}\)) is \(2^{O(\mathop{\mathrm{\operatorname{ddim}}})} n\). Since we have \(\log \Delta\) levels, the total time complexity of constructing the data structure is \(2^{O(\mathop{\mathrm{\operatorname{ddim}}})} n \log \Delta\). ◻

Proof. For (1), assume by contradiction that there exists a pair \((U, V) \in \Psi\) and two different edges \((u, v), (u', v') \in U \times V\) in the MST \(T^*\). One can then replace \((u', v')\) by two edges \((u, u')\) and \((v, v')\). Such replacement does not change the connectivity, and \[\begin{align} \mathop{\mathrm{\mathbf{d}}}(u, u') + \mathop{\mathrm{\mathbf{d}}}(v, v') < \frac{1}{t} \mathop{\mathrm{\mathbf{d}}}(U, V) + \frac{1}{t} \mathop{\mathrm{\mathbf{d}}}(U, V) \leq \frac{2}{t} \mathop{\mathrm{\mathbf{d}}}(u', v') \leq \mathop{\mathrm{\mathbf{d}}}(u', v'), \end{align}\] contradicting the minimality of \(T^*\).

For (2), it suffices to show that the resulting graph is connected. Denote the MST edges by \(\{e_1^*, e_2^*, \dots, e_{n - 1}^*\}\), where \(w(e_1^*) \leq w(e_2^*) \leq \dots \leq w(e_{n - 1}^*)\), and suppose \((U_i, V_i) \in \Psi\) is the selected pair with \(e_i^* \in U_i \times V_i\). Let \(e_i\) be an arbitrary edge in \(U_i \times V_i\). For \(1 \leq i \leq n - 1\), let \(G_i^*\) (resp. \(G_i\)) be the graph formed by \(\{e_1^*, e_2^*, \dots, e_{i}^*\}\) (resp. \(\{e_1, e_2, \dots, e_{i}\}\)). Let \(\mathcal{C}_i^* \subseteq 2^X\) (resp. \(\mathcal{C}_i \subseteq 2^X\)) be the collection of connected components in \(G_i^*\) (resp. \(G_i\)). We prove by induction that \(\mathcal{C}_i^* = \mathcal{C}_i\). (2) then follows by setting \(i = n - 1\).

The equation holds for \(i = 0\), as initially both \(\mathcal{C}_0^*\) and \(\mathcal{C}_0\) are collections of singletons. Assume \(\mathcal{C}_{i - 1}^* = \mathcal{C}_{i - 1}\). We first claim that \(U_i\) is connected in \(G_{i - 1}^*\) (and thus in \(G_{i - 1}\)). In fact, if there are two points \(u_1, u_2 \in U_i\) which are not connected in \(G_{i - 1}^*\), then since \(\mathop{\mathrm{\mathbf{d}}}(u_1, u_2) \leq \mathop{\mathrm{\operatorname{diam}}}(U_i) < \mathop{\mathrm{\mathbf{d}}}(U, V) \leq w(e_i^*)\), replacing \(e_i^*\) by \((u_1, u_2)\) yields a cheaper solution, which contradicts the minimality of \(T^*\). Similarly, \(V_i\) is also connected in \(G_{i - 1}^*\) (and thus in \(G_{i - 1}\)).

Therefore, \(e_i^*\) merges the connected components in \(G_{i - 1}^*\) which contain \(U_i\) and \(V_i\), and \(e_i\) merges the connected components in \(G_{i - 1}\) which contain \(U_i\) and \(V_i\). Since \(\mathcal{C}_{i - 1}^* = \mathcal{C}_{i - 1}\), we have \(\mathcal{C}_i^* = \mathcal{C}_i\), concluding the proof. ◻

Proof. The algorithm is given in 2.

To construct \(\Psi\), we call 2 with \(\mathrm{WSPC}(r, r)\) and parameter \(t\), where \(r\) is the “root” of the net hierarchy (i.e., the only net point in \(N_L\)). Properties [it:bounded95lev95diff] and [it:separation] follow directly from 2.

For property [it:Psi95covering], let us fix a pair of points \((x, y) \in \binom{X}{2}\), and show that there exists \((u, v) \in \Psi\) such that \((x, y) \in B(u, 2^{\mathop{\mathrm{lev}}(u)}) \times B(v, 2^{\mathop{\mathrm{lev}}(v)})\). To this end, assume 2 makes a call to \(\mathrm{WSPC}(u, v)\), where \(x \in B(u, 2^{\mathop{\mathrm{lev}}(u)})\) and \(y \in B(v, 2^{\mathop{\mathrm{lev}}(v)})\); we show that the call \(\mathrm{WSPC}(u, v)\) either returns \((u, v)\), or makes a call to some \(\mathrm{WSPC}(u', v)\), such that \(x \in B(u', 2^{\mathop{\mathrm{lev}}(u')})\) and \(y \in B(v, 2^{\mathop{\mathrm{lev}}(v)})\). Indeed, it suffices to prove \[\begin{align} B(u, 2^{\mathop{\mathrm{lev}}(u)}) \subseteq \bigcup_{u' \in C(u)} B(u', 2^{\mathop{\mathrm{lev}}(u')}). \end{align}\] This follows directly from [it:desc95covering] of [lemma:descendants95packing95covering].

For property [it:bounded95deg], we will show a slightly stronger result: For each net point \(u\), the number of net points \(v\) such that 2 makes a call to \(\mathrm{WSPC}(u, v)\) is at most \(t^{O(\mathop{\mathrm{\operatorname{ddim}}})}\).

If \(u = r\) then the claim holds, as 2 calls \((r, v)\) only if \(v = r\) or \(v\) is a child of \(r\). By [lemma:num95children95parent], \(|C(r)| \leq 2^{O(\mathop{\mathrm{\operatorname{ddim}}})}\). Assume \(u \neq r\), and the procedure calls \((u, v)\) for some net point \(v\). We consider the last call that invokes \((u, v)\). We have two cases:

If the last call is \((u', v)\), where \(u\) is the child of \(u'\), then by property [it:bounded95lev95diff] we have \(\mathop{\mathrm{lev}}(v) \leq \mathop{\mathrm{lev}}(u) + 1\) and \(\mathop{\mathrm{lev}}(v) \geq \mathop{\mathrm{lev}}(u') - 1 = \mathop{\mathrm{lev}}(u)\). Moreover, since the call to \((u', v)\) does not return \(\{(u, v)\}\), we have \(\mathop{\mathrm{\mathbf{d}}}(u', v) \leq (2t + 2) \max\{2^{\mathop{\mathrm{lev}}(u')}, 2^{\mathop{\mathrm{lev}}(v)}\} = (2 t + 2) 2^{\mathop{\mathrm{lev}}(u')}\). By triangle inequality, \[\begin{align} \mathop{\mathrm{\mathbf{d}}}(u, v) \leq \mathop{\mathrm{\mathbf{d}}}(u, u') + \mathop{\mathrm{\mathbf{d}}}(u', v) \leq 2^{\mathop{\mathrm{lev}}(u') + 1} + (2 t + 2) 2^{\mathop{\mathrm{lev}}(u')} = (2t + 4) 2^{\mathop{\mathrm{lev}}(u')} = (4t + 8) 2^{\mathop{\mathrm{lev}}(u)}. \end{align}\] As \(\mathop{\mathrm{lev}}(u) \leq \mathop{\mathrm{lev}}(v) \leq \mathop{\mathrm{lev}}(u) + 1\), all possible such \(v\) are in \[B(u, (4t + 8) 2^{\mathop{\mathrm{lev}}(u)}) \cap (N_{\mathop{\mathrm{lev}}(u)} \cup N_{\mathop{\mathrm{lev}}(u) + 1}).\] The number of such \(v\) is at most \((64 t + 128)^{O(\mathop{\mathrm{\operatorname{ddim}}})}\).

If the last call is \((u, v')\), where \(v\) is a child of \(v'\), then by property [it:bounded95lev95diff] we have \(\mathop{\mathrm{lev}}(v') \leq \mathop{\mathrm{lev}}(u) + 1\) and \(\mathop{\mathrm{lev}}(v') = \mathop{\mathrm{lev}}(v) + 1 \geq \mathop{\mathrm{lev}}(u)\). Since the call to \((u, v')\) does not return \(\{(u, v')\}\), we have \(\mathop{\mathrm{\mathbf{d}}}(u, v') \leq (2t + 2) \max\{2^{\mathop{\mathrm{lev}}(u)}, 2^{\mathop{\mathrm{lev}}(v')}\} \leq (4t + 4) 2^{\mathop{\mathrm{lev}}(u)}\). So all such \(v'\) are in \[B(u, (4t + 4) 2^{\mathop{\mathrm{lev}}(u)}) \cap (N_{\mathop{\mathrm{lev}}(u)} \cup N_{\mathop{\mathrm{lev}}(u) + 1}).\] The number of such \(v'\) is at most \((64 t + 64)^{O(\mathop{\mathrm{\operatorname{ddim}}})}\). As \(v\) is one child of \(v'\), by [lemma:num95children95parent], the number of \(v\) is at most \((64 t + 64)^{O(\mathop{\mathrm{\operatorname{ddim}}})} \cdot 2^{O(\mathop{\mathrm{\operatorname{ddim}}})}\).

In conclusion, the number of net points \(v\) such that the procedure makes a call to \((u, v)\) is at most \(t^{O(\mathop{\mathrm{\operatorname{ddim}}})}\). Property [it:bounded95deg] thus follows, and the time complexity of constructing \(\Psi\) also follows.

To prove the “In particular” part, let us check that \(\Phi\) satisfies 5. The covering property (5 [it:WSPC95covering]) follows directly from property [it:Psi95covering]. Regarding the separation (5 [it:WSPC95separation]), note that for a pair \((u, v) \in \Psi\), if \(\mathop{\mathrm{lev}}(u) = \mathop{\mathrm{lev}}(v) = 0\), then both \(B(u, 2^{\mathop{\mathrm{lev}}(u)})\) and \(B(v, 2^{\mathop{\mathrm{lev}}(v)})\) are singletons, thus have diameter \(0\). Otherwise, by property [it:separation], \(\mathop{\mathrm{\mathbf{d}}}(u, v) > (2t + 2) \max\{2^{\mathop{\mathrm{lev}}(u)}, 2^{\mathop{\mathrm{lev}}(v)}\}\). Hence, \[\begin{align} \mathop{\mathrm{\mathbf{d}}}(B(u, 2^{\mathop{\mathrm{lev}}(u)}), B(v, 2^{\mathop{\mathrm{lev}}(v)})) \geq \mathop{\mathrm{\mathbf{d}}}(u, v) - 2^{\mathop{\mathrm{lev}}(u)} - 2^{\mathop{\mathrm{lev}}(v)} > 2t \cdot \max\{2^{\mathop{\mathrm{lev}}(u)}, 2^{\mathop{\mathrm{lev}}(v)}\}. \end{align}\] So \(\Phi\) is a \(t\)-WSPC of \(X\).

To construct \(\Phi\) from \(\Psi\), it suffices to construct \(B(u, 2^{\mathop{\mathrm{lev}}(u)})\) for every net point \(u\) on the net hierarchy. For each \(x \in X\) and \(0 \leq \ell \leq L\), denote \(P_\ell(x) := \{u \in N_\ell \colon \mathop{\mathrm{\mathbf{d}}}(u, x) \leq 2^\ell\}\). The problem then reduces to computing \(P_\ell(x)\) for all \(x \in X\) and \(0 \leq \ell \leq L\). We can construct \(P_\ell(x)\) inductively: The base case is \(P_0(x) = \{x\}\). For \(\ell \geq 1\), assume we already have \(P_{\ell - 1}(x)\). Note that for every \(u \in P_\ell(x)\) and \(v \in P_{\ell - 1}(x)\), \(\mathop{\mathrm{\mathbf{d}}}(u, v) \leq \mathop{\mathrm{\mathbf{d}}}(u, x) + \mathop{\mathrm{\mathbf{d}}}(v, x) \leq 2^\ell + 2^{\ell - 1} < 2^{\ell + 1}\), so \(v \in C(u)\). Hence to construct \(P_\ell(x)\), we pick an arbitrary point \(v \in P_{\ell - 1}(x)\), construct the set \(A = \{u \in N_\ell \colon v \in C(u)\}\) using pointers to \(v\), and compute \(P_\ell(x) := A \cap B(x, 2^\ell)\). Since \(|A| \leq 2^{O(\mathop{\mathrm{\operatorname{ddim}}})}\) by [lemma:num95children95parent], the time complexity of constructing \(P_\ell(x)\) is \(2^{O(\mathop{\mathrm{\operatorname{ddim}}})}\), thus \(P_\ell(x)\) for all \(0 \leq \ell \leq L\) and \(x \in X\) can be constructed in \(2^{O(\mathop{\mathrm{\operatorname{ddim}}})} n \log \Delta\) time. Therefore, \(\Phi\) can be constructed from \(\Psi\) in time \(2^{O(\mathop{\mathrm{\operatorname{ddim}}})} n \log \Delta + t^{O(\mathop{\mathrm{\operatorname{ddim}}})} n \log \Delta = t^{O(\mathop{\mathrm{\operatorname{ddim}}})} n \log \Delta\). ◻

Proof. Our approximation algorithm is rather simple: We first construct the net hierarchy \(\mathcal{N}= \{N_0, N_1, \dots, N_L\}\) over \(X\) by [lemma:net95hierarchy95construction]. (Note that the construction of \(\mathcal{N}\) in the proof of [lemma:net95hierarchy95construction] does not require knowing \(\mathop{\mathrm{\operatorname{ddim}}}(X)\) in advance.) We then output \[\begin{align} t = \max_{u \in \bigcup_{\ell = 0}^L N_\ell} \log |C(u)| \end{align}\] as an approximation of \(\mathop{\mathrm{\operatorname{ddim}}}\).

The running time follows directly from [lemma:net95hierarchy95construction]. It then remains to prove that \(t = \Theta(\mathop{\mathrm{\operatorname{ddim}}})\). For the upper bound, by [lemma:num95children95parent], we have that for each net point \(u\), \(|C(u)| \leq 2^{O(\mathop{\mathrm{\operatorname{ddim}}})}\), so \(t = O(\mathop{\mathrm{\operatorname{ddim}}})\).

For the lower bound, fix an arbitrary point \(x \in X\) and a radius \(r \in [1, \Delta]\), we show that the ball \(B(x, r)\) can be covered by at most \(2^{O(t)}\) balls of half the radius, implying the desired bound \(\mathop{\mathrm{\operatorname{ddim}}}= O(t)\). In fact, let \(\ell\) be such that \(2^{\ell - 1} < r \leq 2^\ell\); let \(u \in N_{\ell + 2}\) be the closest net point to \(x\) in \(N_{\ell + 2}\). By 1 , \(\mathop{\mathrm{\mathbf{d}}}(x, u) \leq 2^{\ell}\), so \[B(x, r) \subseteq B(u, 2^{\ell + 1}).\] Moreover, by [lemma:descendants95packing95covering] [it:desc95covering], \[B(u, 2^{\ell + 1}) \subseteq \bigcup_{v \in D_{\ell}(u)} B(v, 2^{\ell - 2}) \subseteq \bigcup_{v \in D_{\ell}(u)} B(v, r/2).\] Therefore, \(B(x, r)\) can be covered by \(|D_\ell(u)| \leq 2^{2t}\) balls of half the radius. Hence, \(\mathop{\mathrm{\operatorname{ddim}}}\leq 2 t\) as \(x\) and \(r\) are arbitrarily chosen. ◻

Proof. Assume the interpoint distance of \(X\) is \(1\) and the diameter of \(X\) is \(\Delta\). The subset \(X'\) is constructed as follows:

Let \(\ell_0\) be the largest integer \(\ell\) with \(2^{\ell - 3} \leq \epsilon \Delta / n^{10}\). We run the algorithm in 6.1 to construct the highest \(L - \ell_0 + 1\) levels of the net hierarchy, i.e., \(N_L, N_{L - 1}, \dots, N_{\ell_0}\), and maintain the grouping \(\{G(u)\}_{u \in N_{\ell_0}}\) at level \(\ell_0\). Define \(X' := N_{\ell_0}\).

By the construction in the proof of [lemma:net95hierarchy95construction] computing each level takes \(2^{O(\mathop{\mathrm{\operatorname{ddim}}})} n\) time. Since we have \(L - \ell_0 + 1 = O(\log(n/\epsilon))\) levels, the time complexity of constructing \(X'\) is \(2^{O(\mathop{\mathrm{\operatorname{ddim}}})} n \log(n/\epsilon)\).

Property (1) follows directly from the construction, as \(\mathop{\mathrm{\operatorname{diam}}}(X') = \Delta\) and the minimum interpoint distance of \(X'\), by [lemma:net95hierarchy95construction], is at least \(2^{\ell_0 - 3} \leq \epsilon \Delta / n^{10}\).

For property (2), we first show that \[\begin{align} \mathop{\mathrm{MST}}(X') \leq \mathop{\mathrm{MST}}(X) + \frac{4 \epsilon \Delta}{n^9}. \label{eqn:MST95change} \end{align}\tag{9}\] Indeed, let \(T^*\) be the MST of \(X\); we construct a spanning tree \(T'\) of \(X'\) as follows: For every edge \(e = (x, y) \in T^*\), let \(u\) and \(v\) be points in \(X' = N_{\ell_0}\) such that \(x \in G(u)\) and \(y \in G(v)\); add the edge \(e' = (u, v)\) to \(T'\). Clearly \(T'\) is connected in \(X'\), as each path in \(T^*\) has a corresponding path in \(T'\). Thus, after removing cycles and duplicated edges, \(T'\) becomes a spanning tree of \(X'\). On the other hand, recall the definition of grouping that \(u\) (resp. \(v\)) is the closest point to \(x\) (resp. \(y\)) in \(N_{\ell_0}\), so \(\mathop{\mathrm{\mathbf{d}}}(x, u) \leq 2^{\ell_0 - 2} \leq 2 \epsilon \Delta / n^{10}\) (resp. \(\mathop{\mathrm{\mathbf{d}}}(y, v) \leq 2 \epsilon \Delta / n^{10}\)). Therefore, for each edge \(e = (x, y) \in T^*\), \[\begin{align} w(e') - w(e) = \mathop{\mathrm{\mathbf{d}}}(u, v) - \mathop{\mathrm{\mathbf{d}}}(x, y) \leq \mathop{\mathrm{\mathbf{d}}}(x, u) + \mathop{\mathrm{\mathbf{d}}}(y, v) \leq \frac{4 \epsilon \Delta}{n^{10}}. \end{align}\] We hence have \[\begin{align} w(T') - w(T^*) \leq \sum_{e \in T^*} \frac{4 \epsilon \Delta}{n^{10}} \leq \frac{4 \epsilon \Delta}{n^9}, \end{align}\] completing the proof of 9 .

Given an arbitrary \((1 + \epsilon)\)-approximate MST \(T'\) of \(X'\), we can construct a spanning tree \(T\) of \(X\) in \(O(n)\) time as follows: For each \(x \in X \setminus X'\), find \(u \in X' = N_{\ell_0}\) such that \(x \in G(u)\) and connect the edge \((x, u)\). Moreover, \[\begin{align} w(T) &= w(T') + \sum_{x \in X \setminus X'} \mathop{\mathrm{\mathbf{d}}}(x, X') \\ &\leq (1 + \epsilon) \mathop{\mathrm{MST}}(X') + n \cdot \frac{2 \epsilon \Delta}{n^{10}} \\ &\leq (1 + \epsilon) (\mathop{\mathrm{MST}}(X) + \frac{4 \epsilon \Delta}{n^9}) + \frac{2\epsilon \Delta}{n^9} &&\text{by \eqref{eqn:MST95change}} \\ &\leq (1 + \epsilon) \mathop{\mathrm{MST}}(X) + \frac{10 \epsilon \Delta}{n^9} \\ &\leq (1 + 2 \epsilon) \mathop{\mathrm{MST}}(X) &&\text{since } \mathop{\mathrm{MST}}(X) \geq \Delta \text{ and } n \geq 2. \end{align}\] This concludes the proof of property (2). ◻