## 3 Meshing Algorithm
Else if D3 or D4 in **DiskCondition**(\(p\)) is violated insert \(x\) into \(S\) 3. Else if \(\mathrm{size}(t,\sigma)>\lambda\) for some tuple \((t,\sigma)\) where \(t\in\mathrm{Skl}^{2}\,S|_{\sigma}\) insert \(x\in V_{t}|_{\mathcal{D}}\) that realizes \(\mathrm{size}(t,\sigma)\) into \(S\). 3. If \(S\) has grown in the last execution of step 2, repeat step 2. 4. Return \(\bigcup_{i}\mathrm{Skl}^{i}\,S|_{\mathcal{D}}\). Notice that in step 2(a) we refine either a ball or a triangle if either D1 or D2 is violated. However, for D3 or D4 violations in step 2(b), we only refine a triangle. This is important because D3 and D4 are not covered by Lemma 2 and may be violated no matter how small the balls are. We argue separately for D3 and D4 in the termination proof. In step 2(c) we refine triangles to reach the refinement level of the input scale. We observe that DelPSC never inserts unweighted points inside any protecting ball. If the inserted point \(x\) in step 2(a) lies in a protecting ball \(b=B(q,r)\), its weighted distance to \(q\) would be non-positive. Its weighted distance to its nearest Voronoi neighbor in \(S\) would even be smaller. Since the largest ball has a positive radius, \(x\) would not be inserted (we would call RefineBall(b) instead). If \(x\) is inserted in step 2(b), the point \(p\) is connected to a point \(q\) where either \(q\
ot\in\sigma\) or \(p\) and \(q\) are non-adjacent weightedpoints on a \(1\)-face. In both cases \(p\) and \(q\) have a positive weighted distance ensured by C3.b. Therefore, a restricted triangle \(t\) incident to \(pq\) has \(\operatorname{size}(t,\sigma)\) positive. It follows that the point \(x\) which realizes the maximum of \(\operatorname{size}(t,\sigma)\) over all \(t\) and \(\sigma\) has a positive weighted distance to its nearest Voronoi neighbor in \(S\). Hence \(x\) cannot lie in a protecting ball. Finally, since \(\lambda>0\), any point \(x\) inserted in step 2(c) has a positive distance to its Voronoi neighbors, and thus outside of every protecting ball. Therefore, point \(x\) has a positive weighted distance from \(p\) and hence cannot be inside a ball. **Guarantees**: The analysis of the algorithm establishes two main facts: (i) the algorithm terminates, and (ii) at termination the output mesh has guarantees G1 and G2:  
1. For each \(\sigma\in\mathcal{D}_{2}\), \(\operatorname{Skl}^{2}S|_{\sigma}\) is a \(2\)-manifold with vertices only in \(\sigma\). Further, \(\operatorname{bd}\left(\operatorname{Skl}^{2}S|_{\sigma}\right)\) is homeomorphic to \(\operatorname{bd}\sigma\) with vertices only in \(\operatorname{bd}\sigma\). 2. There exists a \(\lambda_{c}>0\) so that if \(\lambda\leqslant\lambda_{c}\), the output mesh of \(\mathsf{DelPSC}(\mathcal{D},\lambda)\) is homeomorphic to \(|\mathcal{D}|\). Further, this homeomorphism respects stratification with vertex restrictions, that is, for \(0\leqslant i\leqslant 2\), \(\operatorname{Skl}^{i}S|_{\sigma}\) is homeomorphic to \(\sigma\in\mathcal{D}_{i}\) where \(\operatorname{bd}\operatorname{Skl}^{i}S|_{\sigma}=\operatorname{Skl}^{i-1}S| _{\operatorname{bd}\sigma}\) and vertices of \(\operatorname{Skl}^{i}S|_{\sigma}\) lie in \(\sigma\). **Theorem 1**: \(\mathsf{DelPSC}\) _terminates._  
First, we argue that if the algorithm refines a ball, its radius is larger than a fixed positive constant. Assume that \(d_{1}\) and \(d_{2}\) have been defined as in the algorithm. Consider a vertex \(p\) on a 2-face \(\sigma\). The conclusion of Lemma 2 implies disk conditions D1 and D2. Therefore, if it does not hold for \(p\), at least one of the premises of Lemma 2 does not hold. (H1) \(S\) does not satisfy the \(\lambda_{1}\)-property for some \(\lambda_{1}>0\). (H2) Protecting balls do not satisfy C1-C3. But, when the disk condition is checked, the protecting balls satisfy condition C1, C2, C3.a, and C3.b due to Lemma 6(ii). Therefore, if H2 has failed, at least one ball has a radius more than \(\lambda_{2}\) where \(\lambda_{2}\) satisfies Lemma 3.