## 1 Introduction
### Ball refinement  
The ball refinement routine simply removes a ball and covers the curve segment between the centers of its adjacent balls with balls of smaller radii. Therefore, we encounter the generic situation where a curve segment \(\sigma(x,y)\) needs to be covered by protecting balls whose radii are determined by a given parameter \(\alpha>0\). The points \(x\) and \(y\) are the right and left end points of some segments, say \(\mathrm{seg}_{\sigma}(b_{0})\) and \(\mathrm{seg}_{\sigma}(b_{k})\) respectively, see Figure 3. We call this routine Cover(\(x,y,\alpha\)). We proceed from \(x\) toward \(y\) along the curve while computing the balls that satisfy conditions C1, C2, and C3.a. Condition C3.b is taken care of by another routine called Separate. As we walk from \(x\) to \(y\), each step places a new ball of radius \(\alpha\) that intersects deeply with the previous ball while covering a new piece of the curve. When we reach \(y\), we place a ball that intersects deeply with both the endpoint ball and the previous one in the walk. More specifically, suppose that \(b_{i}=B(c_{i},r_{i})\) is already computed. Let \(\sigma(x_{i},y_{i})=\mathrm{seg}_{\sigma}(b_{i})\). We compute a small ball \(\beta_{i+1}=B(y_{i},\alpha/3)\) that _aids_ the computation of \(b_{i+1}\), see Figure 3. The aiding ball helps compute the next ball so that its center is not contained in the segment of the previous ball. Among the two end points of segment \(\mathrm{seg}_{\sigma}(\beta_{i+1})\), we use the one which is further from \(x\). Let this end point be \(z_{i+1}\). The center of the next ball \(b_{i+1}\) is placed at \(z_{i+1}\). We will eventually encounter one of two situations near the end: either \(z_{i+1}\) extends past \(\sigma(x,y)\) or \(\mathrm{seg}_{\sigma}(b_{i+1})\) contains \(y\). These situations are shown in the left and right images of Figure 3, respectively. In the first case \(b_{k}\) may violate C3.a and in the second case \(b_{i+1}\) may not intersect \(b_{k}\) deeply violating C2. In these cases we conduct an _end game_. If \(z_{i+1}\in\mathrm{seg}_{\sigma}(b_{k})\), we throw away \(z_{i+1}\) and take \(b_{i+1}\) as \(\beta_{i+1}\) enlarged concentrically to a radius \(\frac{2\alpha}{3}\). In the other case when \(\mathrm{seg}_{\sigma}(b_{i+1})\) contains \(y\), we enlarge \(b_{i+1}\) to a radius of \(\frac{7\alpha}{6}\). Cover terminates after the end game. Lemma 4 is proved in the appendix. **Lemma 4**: _Let \(b\) be a ball adjacent to \(b^{\prime}\) and \(b^{\prime\prime}\) in a set of balls that satisfy C1, C2, and C3.a. Suppose we replace \(b\) with Cover\((x,y,\alpha)\) where \(\sigma(x,y)\) is the segment between \(\mathrm{seg}_{\sigma}(b)\) and \(\mathrm{seg}_{\sigma}(b^{\prime\prime})\). Then, for \(\alpha\) less than the radii of the balls \(b,b^{\prime}\), and \(b^{\prime\prime}\), C1, C2, and C3.a remain satisfied after Cover\((x,y,\alpha)\) terminates._  
Cover does not necessarily satisfy C3.b. We use the routine Separate to enforce C3.b on a set of balls \(\mathcal{B}\). This routine calls RefineBall(\(b\)) which removes the ball \(b\) and replaces it with smaller balls. Separate(\(\mathcal{B}\))  
1. while (\(\exists\) balls \(b,b^{\prime}\in\mathcal{B}\) with \(r\geqslant r^{\prime}\) violating C3.b) \(\mathcal{B}:=(\mathcal{B}\setminus b)\cup\textsc{RefineBall}(b)\) endwhile. 2. return \(\mathcal{B}\). **Lemma 5**: _If Separate issues a call to refine a ball \(b\), its radius must be more than a fixed positive constant \(\delta>0\)._  
First assume that the two balls \(b=B(c,r)\) and \(b^{\prime}=B(c^{\prime},r^{\prime})\) considered by Separate belong to the same 1-face \(\sigma\). By assumption \(r\geqslant r^{\prime}\). Let \(x\) be any point where the boundary spheres of \(b\) and \(b^{\prime}\) meet. If \(\theta\) is the angle between the normals to \(b\) and \(b^{\prime}\) at \(x\), the squared weighted distance between \(b\) and \(b^{\prime}\) is given by \(d(c,c^{\prime})^{2}-r^{2}-r^{\prime 2}=-2 rr^{\prime}\cos\theta\).