## 8 Proofs of lemmas in Section 4. [Proof of Lemma 8.] Recall that \(\sigma_{p}\) denotes the set of connected components in \(V_{p}|_{\sigma}\) intersecting a Voronoi edge. We are required to prove that \(V_{p}|_{\mathscr{D}}=\bigcup_{\sigma\
i p}\sigma_{p}\). Assume to the contrary that \(\bigcup\sigma_{p}\subset V_{p}|_{\mathscr{D}}\). Let \(C\) be any connected component in \(V_{p}|_{\mathscr{D}}\setminus\bigcup\sigma_{p^{\prime}}\) and \(C\subset\sigma^{\prime}\) where \(\sigma^{\prime}\
eq\sigma\). Voronoi cells partition \(\sigma^{\prime}\). A path on \(\sigma^{\prime}\) from \(\mathrm{bd}\,C\) to a sample point \(q\in\sigma^{\prime}\) passes through the connected components of this partition. We must encounter two adjacent components along this path, say \(C^{\prime}\) and \(C^{\prime\prime}\), where \(C^{\prime}=\sigma^{\prime}_{s}\) for \(s\
ot\in\sigma^{\prime}\) and \(C^{\prime\prime}=\sigma^{\prime}_{r}\) for some \(r\in\sigma^{\prime}\). This holds because the first and last components satisfy this property. Then, by PSC Lemma (Lemma 2), \(C^{\prime\prime}=\sigma^{\prime}_{r}\) is a topological disk intersecting Voronoi edges of \(V_{r}\). Since \(C^{\prime}\) and \(C^{\prime\prime}\) are adjacent, there is a Voronoi edge \(e\) incident to both \(V_{r}\) and \(V_{s}\) which is intersected by \(\sigma^{\prime}_{r}\). This means \(\mathrm{Umb}_{r}\) has a triangle with a vertex \(s\) which is not in \(\sigma^{\prime}\), a condition forbidden by **DiskCondition**. Since we are considering the point set output by DelPSC, the **DiskCondition** must have been satisfied. [Proof of Lemma 9.] Case 1: \(F\) is a Voronoi cell \(V_{p}\). Let \(\sigma_{F}\in\mathscr{D}\) be the lowest dimensional element containing \(p\). We claim all elements in \(\mathscr{D}\) intersecting \(F\) have \(\sigma_{F}\) in their boundaries and thus \(\sigma_{F}\) is unique. If not, let there be another \(\sigma^{\prime}\in\mathscr{D}\) where \(\sigma_{F}\
ot\subset\mathrm{bd}\,\sigma^{\prime}\). Notice that \(p\
ot\in\sigma_{F}\cap\sigma^{\prime}\) since otherwise \(\sigma_{F}\cap\sigma^{\prime}\) is either an element of \(\mathscr{D}\) whose dimension is lower than \(\sigma_{F}\) or \(\sigma_{F}\cap\sigma^{\prime}=\sigma_{F}\) both of which are impossible. It follows that \(p\
ot\in\sigma^{\prime}\). But we already argued above that \(V_{p}\) intersects only elements in that contain \(p\). Case 2: \(F\) is a Voronoi facet \(V_{pq}\). Let \(\sigma_{F}\) be a lowest dimensional element that \(F\) intersects. Assume there is another \(\sigma^{\prime}\) intersecting \(F\) where \(\sigma_{F}\
ot\subset\mathrm{bd}\,\sigma^{\prime}\). We go over different dimensions of \(\sigma^{\prime}\) each time reaching a contradiction. Assume \(\sigma^{\prime}\in\mathcal{D}_{\leqslant 2}\); \(\sigma^{\prime}\) intersects \(F\) and does not contain \(\sigma_{F}\) on its boundary. Two cases can arise. Either (i) \(\sigma_{F}\) and \(\sigma^{\prime}\) are disjoint within \(V_{p}\) or \(V_{q}\), or (ii) \(\sigma_{F}\) and \(\sigma^{\prime}\) have a common boundary in \(V_{p}\) and \(V_{q}\). Case (i) cannot happen due to the claim in Case 1. For (ii) to happen, both \(p\) and \(q\) have to be on the common boundaries of \(\sigma_{F}\) and \(\sigma^{\prime}\), which means that \(p\) and \(q\) have to be on some element in \(\mathcal{D}_{\leqslant 1}\). Observe that \(p\) and \(q\) are non-adjacent since otherwise \(V_{pq}\) has to intersect the common boundary of \(\sigma_{F}\) and \(\sigma^{\prime}\) whose dimension is lower than that of \(\sigma_{F}\). But this would contradict the disk condition that no two non-adjacent vertices in \(\mathcal{D}_{1}\) are connected by a restricted edge. The above argument implies that all elements intersecting \(F\) have \(\sigma_{F}\) as a subset. Case 3: \(F\) is a Voronoi edge. Certainly \(F\) cannot intersect a \(2\)-face \(\sigma_{F}\) more than once due to Lemma 2 (R1). The other possibility is that \(F=V_{t}\), \(t\in\mathrm{Skl}^{2}\,S|_{\sigma_{F}}\), and \(F\) intersects \(\sigma^{\prime}\
eq\sigma_{F}\).