## 1 Introduction
### Covering 1-faces
This is the maximum weighted distance between vertices of \(t\) and the points where the dual Voronoi edge of \(t\) intersects \(\sigma\). \(\lambda\)-property: We say \(S\) has the \(\lambda\)-_weight_ property if each point in \(S\) has a weight at most \(\lambda\geqslant 0\). We say \(S\) has the \(\lambda\)-_size_ property if \(\operatorname{size}(t,\sigma)\leqslant\lambda\) for each triangle \(t\in\operatorname{Skl}^{2}S|_{\sigma}\) and \(S\) has the \(\lambda\)-weight property. The following observation is at the heart of our refinement algorithm (see Section 7. in appendix for a proof sketch). **Lemma 2**: _Let \(S\subset\mathcal{D}\) be an admissible point set and \(p\in S\) be a point on a 2-face \(\sigma\). Let \(\sigma_{p}\subset\sigma\) be the set of all connected components in \(V_{p}|_{\sigma}\) that intersect a Voronoi edge. There exists a constant \(\lambda>0\) so that hypotheses \(\mathrm{H1}\) and \(\mathrm{H2}\) imply results \(\mathrm{R1}\) and \(\mathrm{R2}\) where_  
1. \(S\) _satisfies_ \(\lambda\)_-size property._
2. _Weighted points in_ \(S\) _satisfy_ C1-C3_._
3. \(\sigma_{p}\) _is a 2-disk where any edge of_ \(V_{p}\) _intersects_ \(\sigma_{p}\) _at most once and any facet of_ \(V_{p}\) _intersects_ \(\sigma_{p}\) _in an empty set or an open curve._
4. _If_ \(p\in\operatorname{bd}\sigma\)_, at least two Voronoi facets of_ \(V_{p}\) _intersect_ \(\operatorname{bd}\sigma\)_, each intersecting one of the curve segments between_ \(p\) _and its adjacent weighted points (possibly two) in_ \(\operatorname{bd}\sigma\)_._  
Interpreted in terms of the Delaunay triangulation, the conclusion of the above lemma implies that the triangles incident to \(p\) and restricted with respect to \(\sigma\) form a topological disk around \(p\). This disk has \(p\) at the boundary if and only if \(p\) is in \(\operatorname{bd}\sigma\). Furthermore, if \(p\) is in \(\operatorname{bd}\sigma\), it is connected to its two adjacent weighted points in \(\operatorname{bd}\sigma\) on this disk. We will formulate a _disk condition_ with these properties. Our refinement algorithm is primarily driven by this disk condition. The conclusion of Lemma 2 fails only if either there is a protecting ball with radius more than \(\lambda\), or there is a triangle \(t\in\operatorname{Skl}^{2}S|_{\sigma}\) for which \(\operatorname{size}(t,\sigma)>\lambda\) for some \(\lambda>0\). However, since we do not know which of the above two cases has happened, we take a conservative approach. We compute the maximum radius \(r_{\max}\) of all protecting balls and also compute the maximum \(d_{\max}=\operatorname{size}(t,\sigma)\) over all \(t\) and \(\sigma\). Let \(x\) be the point of intersection of a Voronoi edge with \(\mathcal{D}\) which realizes \(d_{\max}\). If \(r_{\max}>d_{max}\) we refine the largest protecting ball. Otherwise, we insert \(x\). In the first case we are ensured that we are refining balls of size larger than a fixed positive constant. In the second case, we are inserting a point in a compact domain with a positive lower bound on its distances to every other points. Termination by packing argument follows. For the above algorithm to work, it is important that the balls satisfy C1-C3 when balls are sufficiently small. It turns out that it is difficult to maintain the condition C3 at early phases when the balls are relatively large. We replace C3 by the following two conditions that are maintained by the ball refinement algorithm. These conditions imply C3 when the balls are small enough. For a 1-face \(\sigma(u,v)\) covered by balls \(b_{0},b_{1},..,b_{k}\) these conditions are:  
1. Let \(b=B(c,r)\) be any ball in \(\{b_{0},b_{1},...,b_{k}\}\). For an adjacent ball \(b^{\prime}=B(c^{\prime},r^{\prime})\), if \(c^{\prime}\) is contained in \(\mathrm{seg}_{\sigma}(b)\), then \(d_{\sigma}(c,c^{\prime})\geqslant\frac{7}{6}r\). 2. Any two balls centered in different 1-faces do not intersect and any two non-adjacent balls centered on a common 1-face have a weighted distance larger than the radius of the smaller ball.