## 1 Introduction
### Covering 1-faces  
Let \(\sigma(x,y)\) denote the curve segment oriented from \(x\) to \(y\) on any 1-face \(\sigma\). In this notation \(\sigma=\sigma(u,v)\) where \(\sigma\) is oriented from the end point \(u\) to the other end point \(v\). Let \(b=B(c,r)\) be a ball with \(c\in\sigma(x,y)\). The intersection \(b\cap\sigma\) is a set of curve segments. Among them the curve segment containing \(c\) is called the _segment of \(b\) in \(\sigma\)_, \(\mathrm{seg}_{\sigma}(b)\), see Figure 2. Two balls \(b\) and \(b^{\prime}\) with their centers \(c\) and \(c^{\prime}\) respectively on a \(1\)-face \(\sigma\) are _adjacent_ if \(\sigma(c,c^{\prime})\) does not contain any other ball center. In this case the corresponding weighted vertices of \(b\) and \(b^{\prime}\) are also called _adjacent_. Any two balls or weighted vertices that are not adjacent are called _non-adjacent_. We use \(d(x,y)\) to denote the Euclidean distance between two points \(x,y\) and use \(d_{\sigma}(x,y)\) to denote the length of a curve segment \(\sigma(x,y)\). Let \(b_{0},b_{1},...,b_{k}\) be a set of balls that protect \(\sigma\) where \(b_{i}=B(c_{i},r_{i})\) with \(c_{i}\in\sigma\). We require that the balls satisfy the following conditions:  
1. \(b_{0}\) and \(b_{k}\) are centered at \(u\) and \(v\) respectively. These will be called the _vertex balls_. 2. \(\sigma\) is covered by the balls, that is, \(\sigma\subseteq\cup_{i}\mathrm{seg}_{\sigma}(b_{i})\) and any two adjacent balls \(b=B(c,r)\) and \(b^{\prime}=B(c^{\prime},r^{\prime})\) intersect deeply, that is, \(d(c,c^{\prime})\leqslant r+\frac{6r^{\prime}}{7}\) where \(r^{\prime}\leqslant r\). 3. No point in \(\mathrm{seg}_{\sigma}(b_{i})\) is contained in a ball non-adjacent to \(b_{i}\). Notice that the choice of the constant \(\frac{6}{7}\) in C2 is a little arbitrary. We need only a factor of \(r^{\prime}\) in the expression and a follow-up analysis with other constants are also possible. **Figure 2.** Covering 1-faces : (left) A 1-face \(\sigma\) between \(u\) and \(v\) is being protected. The ball \(b\) shown with solid boundary has \(\mathrm{seg}_{\sigma}(b)\) as the curve segment between \(x_{1}\) and \(x_{2}\). The balls satisfy C1 and C2 but intersect arbitrarily. (right) Balls are refined and they start satisfying separation properties C1-C3. We will maintain a point set \(S\subset\mathcal{D}\) with the following properties throughout the algorithm: all points in \(S\) except those in \(\mathcal{D}_{\leqslant 1}\) are unweighted and no unweighted point has a negative weighted distance to any other point. This means each unweighted point \(p\in S\) has \(V_{p}\) non-empty. We call such a point set _admissible_. It is worthwhile to note that one of the consequences of conditions C1-C3 would be the following result which would imply R2 in Lemma 2. **Lemma 1**: _Let \(S\) be an admissible point set satisfying conditions C1-C3. Let \(p\) and \(q\) be adjacent weighted vertices on a 1-face \(\sigma\). \(V_{pq}\) is the only Voronoi facet in \(\mathrm{Vor}\,S\) that intersects \(\sigma(p,q)\)._Let \(z\) be any point in \(\sigma(p,q)\). Let \(b_{p}\) and \(b_{q}\) be the balls centered at \(p\) and \(q\) respectively. The point \(z\) is contained in \(b_{p}\cup b_{q}\). Due to property C3, \(z\) being a point in \(\sigma(p,q)\) cannot lie inside any ball other than \(b_{p}\) and \(b_{q}\). We remark that \(b_{p}\) and \(b_{q}\) may have a common intersection with another ball, but \(z\) cannot be contained in that ball. Therefore, \(z\) cannot lie on any Voronoi facet partly defined by a point other than \(p\) and \(q\). However, \(\sigma(p,q)\) has to intersect at least one Voronoi facet since \(p\) and \(q\) lie in two different Voronoi cells. Therefore, the only Voronoi facet which intersects \(\sigma(p,q)\) is \(V_{pq}\). For any \(\sigma\in\mathcal{D}_{2}\) and any triangle \(t\in\operatorname{Skl}^{2}S|_{\sigma}\), define \(\operatorname{size}(t,\sigma)\) to be the maximum weighted distance between the vertices of \(t\) and points in \(V_{t}|_{\sigma}\).