## 3 Meshing Algorithm  
Protect(\(\mathcal{D}\),\(\lambda\))  
1. Protect each vertex \(v\in\mathcal{D}_{0}\) with a ball \(B_{v}=B(v,r_{v})\) where \(r_{v}\) is \(1/3\)rd the distance of \(v\) to any other vertex in \(\mathcal{D}_{0}\). Let \(\mathcal{B}\) be the set of vertex balls. 2. For each \(\sigma\in\mathcal{D}_{1}\) do the following. Let \(u\) and \(v\) be the end points of \(\sigma\) where \(\operatorname{seg}_{\sigma}(B_{u})=ux\) and \(\operatorname{seg}_{\sigma}(B_{v})=yv\). Let \(\alpha=\min\{r_{u},r_{v}\}\). \(\mathcal{B}:=\mathcal{B}\cup\textsc{{Cover}}(x,y,\alpha)\). 3. Find a ball \(b\in\mathcal{B}\) with radius larger than \(\lambda\). If found, compute \(\mathcal{B}:=\{\mathcal{B}\setminus b\}\cup\textsc{RefineBall}(b)\) and repeat step 3. 4. return Separate(\(\mathcal{B}\)). **Lemma 7**: Protect _terminates with balls satisfying C1, C2, C3.a, and C3.b._  
Observe that at the end of step 2, Protect creates a set \(\mathcal{B}\) of finitely many balls (most likely quite large). Each call to RefineBall on a ball \(b\) creates only finitely many balls as output (Lemma 6). Since a ball is refined only if its radius is more than \(\lambda>0\), and since each refine shrinks the radii by at least a factor of 2, there are only finitely many balls created in step 3. Termination of step 4 follows from Lemma 5. Hence Protect terminates. At termination it must satisfy C1, C2, C3.a, and C3.b since it refines balls with Cover and calls Separate to enforce C3.b. After the initial protection of \(\mathcal{D}_{1}\), refinement of \(\mathcal{D}_{2}\) begins. In this phase Delaunay refinement is run with a _disk condition_ which can be seen as a generalization of a similar condition used in [3, 4]. See Figure 4 for more explanations. Let \(p\) be a point on a \(2\)-face \(\sigma\) and let \(\operatorname{Umb}_{\sigma}(p)\) be the set of triangles in \(\operatorname{Skl}^{2}S|_{\sigma}\) that are incident to \(p\). **DiskCondition(\(p\))** : (D1) For each \(\sigma\in\mathcal{D}_{2}\) containing \(p\), the underlying space of \(\operatorname{Umb}_{\sigma}(p)\) is a \(2\)-disk, (D2) point \(p\) is in the interior of this \(2\)-disk if and only if \(p\in\operatorname{int}\sigma\), (D3) in \(\operatorname{Umb}_{\sigma}(p)\), \(p\) is not connected to any other point on \(\mathcal{D}_{1}\) which is not adjacent to it, (D4) all vertices of \(\operatorname{Umb}_{\sigma}(p)\) are in \(\sigma\). Once the restricted Delaunay triangles are collected, the above checks are only combinatorial. One may notice that D1 and D2 are dual to R1 and R2 of Lemma 2. We assume that as we insert points, weighted or unweighted, \(\operatorname{Vor}S\) and \(\operatorname{Del}S\) get updated appropriately. **Figure 4.** Disk condition: (left) Triangles incident to point \(p\in\sigma\) are assumed to be restricted to \(\sigma\); they do not form a disk since they form two disks pinched at \(p\) violating condition D1. (middle) The point \(p\in\sigma\) has a topological disk but some of its vertices (lightly shaded) belong to \(\tau\) violating condition D4. (right) Points \(p\) and \(q\) satisfy the disk condition. Point \(p\), an interior point in \(\sigma\), lies in the interior of its disk in \(\sigma\). The point \(q\), a boundary point, has three disks for each of the three \(2\)-faces. DelPSC (\(\mathcal{D},\lambda\))  
1. Protection. Let \(\mathcal{B}\):= Protect(\(\mathcal{D},\lambda\)). Let \(S\) be the current weighted point set. 2. Mesh2 Complex. Let \((p,\sigma)\) be any tuple where \(p\in\sigma\). Let \(t\in\mathrm{Skl}^{2}\,S|_{\sigma}\) be the triangle that maximizes \(\mathrm{size}(t,\sigma)\) over all \(t\) and \(\sigma\). Let \(x\in V_{t}|_{\sigma}\) realize this maximum, say \(d_{1}\). Let \(d_{2}\) be the maximum radius of all vertices realized by ball, say \(b\). 1. If condition D1 or D2 in **DiskCondition**(\(p\)) is violated if \(d_{1}\geqslant d_{2}\) insert \(x\) into \(S\) else compute \(\mathcal{B}:=\{\mathcal{B}\setminus b\}\cup\textsc{RefineBall}(b)\). 2.