## 1 Introduction
### Ball refinement
For \(\pi/2<\theta\leqslant\pi\), this weighted distance is more than  
Figure 3: Curve segment between \(x\) and \(y\) is being covered. Aiding balls are shown with solid boundaries. Notice how the centers of \(b_{1}\) and \(b_{2}\) are placed with the aiding balls. The end game with enlarged aiding ball is shown on left, the other case is shown on right. when \(r>-r^{\prime}/2\cos\theta\) which is satisfied for \(\theta>2\pi/3\). The curve \(\sigma(c,c^{\prime})\) can be assumed to lie within cones having apexes at \(c\) and \(c^{\prime}\) and arbitrarily small aperture angles if \(r\) and hence \(d(c,c^{\prime})\) is sufficiently small. Since \(\mathrm{seg}_{\sigma}(b)\) and \(\mathrm{seg}_{\sigma}(b^{\prime})\) do not intersect if \(r\) is small enough (Proof of Lemma 3), the curve \(\sigma(c,c^{\prime})\) needs to avoid the common intersection of \(b\) and \(b^{\prime}\). These two constraints force the angle \(\theta\) to be close to \(\pi\) as \(r\) approaches zero. In other words, there is a fixed positive constant \(\lambda_{1}\) so that if \(r\leqslant\lambda_{1}\), the weighted distance between \(b\) and \(b^{\prime}\) becomes larger than \(r^{\prime}\). Next, assume that \(b\) and \(b^{\prime}\) have centers on different 1-faces. We need to consider the special case of vertex balls before we argue about this case. A vertex ball \(b\) can intersect a ball whose center lies on a different 1-face only if \(b\)'s radius is more than a fixed positive constant. This is true because we always refine the larger of the two such intersecting balls and there is a positive distance between a vertex and any 1-faces that do not contain it. This observation with the argument in the previous paragraph imply that a vertex ball is refined by Separate only if its size is more than a fixed positive constant. Since no vertex balls can be smaller than a fixed positive constant, two balls centered on two different 1-faces intersect only if the larger ball has a radius more than a fixed positive constant \(\lambda_{2}>0\). It follows that the lemma holds with \(\delta=\min\{\lambda_{1},\lambda_{2}\}\). RefineBall(\(b\))  
If \(b\) covers \(\sigma\in\mathcal{D}_{1}\), let \(r_{\sigma}\) be the minimum of the radii of balls adjacent to \(b\) on \(\sigma\) and \(b\) itself. 1. If \(b=B(v,r)\) is a vertex ball, shrink \(b\) to \(b^{\prime}=B(v,r/2)\). For each \(\sigma\) covered by \(b\) let \(b_{\sigma}\) be the adjacent ball to \(b\) on \(\sigma\). Compute \(\mathcal{B}_{\sigma}:=\textsc{RefineBall}(b_{\sigma})\). Return Separate(\(\cup_{\sigma}\mathcal{B}_{\sigma}\)). 2. If \(b\) is not a vertex ball, let \(\sigma(x,y)\) be the segment between \(\mathrm{seg}_{\sigma}(b_{1})\) and \(\mathrm{seg}_{\sigma}(b_{2})\) where \(b_{1}\) and \(b_{2}\) are adjacent to \(b\). Remove \(b\) and return Cover\((x,y,\alpha)\) where \(\alpha=r_{\sigma}/4\). **Lemma 6**: _(i) RefineBall terminates and (ii) maintains C1, C2, C3.a, and C3.b._  
(i) : Observe that RefineBall makes recursive calls to itself and through Separate. Consider the trees of ball refinements made by these recursive calls. An internal node \(b\) in the trees represents a ball \(b\) that is refined into smaller balls (children). We observe that every internal node except the roots is refined by Separate. The only way RefineBall can call itself is when a ball \(b_{\sigma}\) is to be refined in step 1. But, then \(b_{\sigma}\) becomes a root. All other calls to RefineBall are generated by Separate. By Lemma 5, Separate calls RefineBall on a ball \(b\) only if the size of \(b\) is larger than a fixed positive constant \(\delta>0\). The children of a node \(b\) are created by Cover which, by construction, creates only finitely many balls with radius at most \((1/4\times 7/6)=7/24\)th the radius of \(b\). The height of any refinement tree is finite since any path from the root to a leaf has internal nodes with radius larger than \(\delta>0\) and each level decreases the radius by a factor \(7/24\) or less. Also, each node has finitely many children.