# When alpha-complexes collapse onto codimension-1 submanifolds

Dominique Attali

<figure><img src="image_1.png" /></figure>

<figure><img src="image_2.png" /></figure>

Université Grenoble Alpes, CNRS, Grenoble INP, GIPSA-lab, Grenoble, France

Mattéo Clémot

<figure><img src="image_3.png" /></figure>

<figure><img src="image_4.png" /></figure>

Universite Claude Bernard Lyon 1, CNRS, INSA Lyon, LIRIS, Villeurbanne, France

Bianca B. Dornelas

<figure><img src="image_5.png" /></figure>

<figure><img src="image_6.png" /></figure>

Institute of Geometry, TU Graz, Austria

André Lieutier

<figure><img src="image_7.png" /></figure>

No affiliation, Aix-en-Provence, France

## Abstract

Given a finite set of points $P$ sampling an unknown smooth surface $\mathcal{M} \subseteq \mathbb{R}^3$, our goal is to triangulate $\mathcal{M}$ based solely on $P$. Assuming $\mathcal{M}$ is a smooth orientable submanifold of codimension 1 in $\mathbb{R}^d$, we introduce a simple algorithm, *Naive Squash*, which simplifies the $\alpha$-complex of $P$ by repeatedly applying a new type of collapse called *vertical* relative to $\mathcal{M}$. Naive Squash also has a practical version that does not require knowledge of $\mathcal{M}$. We establish conditions under which both the naive and practical Squash algorithms output a triangulation of $\mathcal{M}$. We provide a bound on the angle formed by triangles in the $\alpha$-complex with $\mathcal{M}$, yielding sampling conditions on $P$ that are competitive with existing literature for smooth surfaces embedded in $\mathbb{R}^3$, while offering a more compartmentalized proof. As a by-product, we obtain that the restricted Delaunay complex of $P$ triangulates $\mathcal{M}$ when $\mathcal{M}$ is a smooth surface in $\mathbb{R}^3$ under weaker conditions than existing ones.

**2012 ACM Subject Classification** Theory of computation → Computational geometry

**Keywords and phrases** Submanifold reconstruction, triangulation, abstract simplicial complexes, collapses, convexity

**Funding** Bianca B. Dornelas: Funded by the Austrian Science Fund (FWF), grant W1230.
# 1 Introduction

Given a finite set of points $P$ that sample an unknown smooth surface $\mathcal{M} \subseteq \mathbb{R}^3$ (example in Figure 1a), we aim to approximate $\mathcal{M}$ based solely on $P$. This problem, known as surface reconstruction, has been widely studied [2,14,18,39–41]. Several algorithms based on computational geometry have been developed, such as Crust [3], PowerCrust [5], Cocone [4], Wrap [29] and variants based on flow complexes [13,26,37,38]. These algorithms rely on the Delaunay complex of $P$ and offer theoretical guarantees, summarized in [24].

The most desirable guarantee is that the reconstruction outputs a triangulation of $\mathcal{M}$, that is, a simplicial complex whose support is homeomorphic to $\mathcal{M}$, in which case we call the algorithm topologically correct. That has been established for many of the aforementioned algorithms, assuming that $P$ is noiseless ($P \subseteq \mathcal{M}$) and sufficiently dense. Specifically, let $\mathcal{R} > 0$ be a lower bound on the reach of $\mathcal{M}$, and $\varepsilon \ge 0$ an upper bound on the distance between any point of $\mathcal{M}$ and its nearest point in $P$. Both Crust and Cocone are topologically correct under the condition $\varepsilon/\mathcal{R} \le 0.06$ [25], which, to our knowledge, is the weakest such constraint guaranteeing topological correctness for surface reconstruction algorithms in $\mathbb{R}^3$.

Surface reconstruction generalizes to approximating an unknown smooth submanifold $\mathcal{M} \subseteq \mathbb{R}^d$ from a finite sample $P$. One approach in that case, similar to the Wrap algorithm in $\mathbb{R}^3$, involves collapses, which are typically applied to complexes like the $\alpha$-complex [12]. The $\alpha$-complex of $P$ [30,31,33] includes simplices whose circumspheres have radius $\le \alpha$ and enclose no other points of $P$ [32]. For well-chosen $\alpha$, the $\alpha$-complex has the same homotopy type as $\mathcal{M}$ [7,19,20,44], provided that $P$ is sufficiently dense and has low noise relative to the reach of $\mathcal{M}$. However, it may still fail to capture the topology of $\mathcal{M}$, as illustrated in Figure 1b: for $\mathcal{M} \subseteq \mathbb{R}^3$, the $\alpha$-complex of $P$ includes slivers, tetrahedra that have one dimension more than $\mathcal{M}$, preventing the existence of a homeomorphism. Slivers complicate reconstructing $k$-dimensional submanifolds in $\mathbb{R}^d$ for $k \ge 2$ for all Delaunay-based reconstruction attempts.

**Contributions.** We introduce a simple algorithm, NaiveVerticalSimplification, which takes as input a simplicial complex $K$ and simplifies it by applying collapses guided by the knowledge of $\mathcal{M}$. We call it naive because this knowledge is non-realistic in practice. We find conditions under which the algorithm is topologically correct for smooth orientable submanifolds $\mathcal{M}$ of $\mathbb{R}^d$ with codimension one. Its variant, PracticalVerticalSimplification, does not rely on $\mathcal{M}$ and remains topologically correct, though it requires stricter conditions. When applying both algorithms to the $\alpha$-complex of $P$ and returning the result, we obtain two reconstruction algorithms which we refer to as NaiveSquash and PracticalSquash, respectively. We determine conditions on the inputs $P$ and $\alpha$ that guarantee the topological correctness of these squash algorithms. Moreover, for $d = 3$, we show that PracticalSquash is correct under the sampling condition $\varepsilon/\mathcal{R} \le 0.178$ (see Figure 1c for an example output), while NaiveSquash is correct for $\varepsilon/\mathcal{R} \le 0.225$, assuming suitable choice of $\alpha$. We also show that the restricted Delaunay complex [16] is generically homeomorphic to $\mathcal{M}$ when $\varepsilon/\mathcal{R} \le 0.225$.

In addition, while proving these results, we derive an upper bound for when triangles with vertices on a smooth submanifold $\mathcal{M} \subseteq \mathbb{R}^d$ form a small angle with $\mathcal{M}$: for a triangle $abc$ with $a, b, c \in \mathcal{M}$, longest edge $bc$, and circumradius $\rho$, we show that the angle between the affine space spanned by $abc$ and the tangent space to $\mathcal{M}$ at $a$ satisfies:

$$ \sin \angle \text{Aff}(abc), \mathbf{T}_a\mathcal{M} \le \frac{\sqrt{3}\rho}{\mathcal{R}}. \qquad (1) $$
<figure><img src="image_8.png" /><figcaption>■ **Figure 1** Points sampling a surface in $\mathbb{R}^3$ (a) with the corresponding $\alpha$-complex, where tetrahedra are highlighted (b). Applying Practical Squash with parameter $\alpha$ outputs (c).</figcaption></figure>

**Techniques.** Our proof of correctness for the squash algorithms is more compartmentalized than the ones present in the literature: we first consider a smooth orientable submanifold $\mathcal{M} \subseteq \mathbb{R}^d$ with codimension one and a general simplicial complex $K$ embedded in $\mathbb{R}^d$ and contained within a small tubular neighborhood of $\mathcal{M}$. We introduce *vertical collapses* (relative to $\mathcal{M}$) in $K$ which remove $d$-simplices of $K$ that either have no $d$-simplices of $K$ above them in directions normal to $\mathcal{M}$ or no $d$-simplices of $K$ below them in directions normal to $\mathcal{M}$. *NaiveVerticalSimplification* iteratively applies vertical collapses relative to $\mathcal{M}$. *PracticalVerticalSimplification* does not depend on knowledge of $\mathcal{M}$ and applies vertical collapses relative to a hyperplane, constructed dynamically based on the simplex currently considered for collapse.

We examine conditions for the correctness of these algorithms. Apart from the requirement that $K$ has no vertical $i$-simplices relative to $\mathcal{M}$ for $0 < i < d$ and that its support projects onto $\mathcal{M}$ and fully covers it, we require the *vertical convexity* of $K$ relative to $\mathcal{M}$. This means that each normal line to $\mathcal{M}$ at a point $m$ (restricted to a small ball around $m$) intersects the support of $K$ in a convex set. For *PracticalVerticalSimplification*, an additional requirement is that the $(d-1)$-simplices of $K$ must form an angle of at most $\frac{\pi}{4}$ with $\mathcal{M}$.

Afterwards, we present *PracticalSquash* and *NaiveSquash*, which initialize the previous algorithms with $K$ as the $\alpha$-complex of a point set $P \subseteq \mathbb{R}^d$ that samples $\mathcal{M}$. We show that correctness is guaranteed when the $i$-simplices in the $\alpha$-complex form small angles with $\mathcal{M}$ for $0 < i < d$. We provide explicit upper bounds for these angles, expressed in terms of $\varepsilon$, $\delta$, and $\alpha$, where $\varepsilon$ and $\delta$ control the sample density and noise in $P$.

We analyze the case $d=3$ and provide numerical bounds on the ratios $\frac{\varepsilon}{\mathcal{R}}$ and $\frac{\alpha}{\mathcal{R}}$ that ensure the correctness of both squash algorithms. Instrumental to this step, we derive (1) which enables us to upper bound the angles of triangles in the $\alpha$-complex relative to the manifold and is of independent interest.

**Related work.** The Squash algorithms (both practical and naive) are similar to Wrap [12,33] in that they compute a subcomplex $K$ of the Delaunay complex of $P$ and then perform a sequence of collapses. However, the selection of $K$ and the nature of the collapses differ between the two methods: in the naive squash, definitions are relative to $\mathcal{M}$, unlike Wrap, which uses flow lines derived from $P$ to guide the collapsing sequence. This distinction allows us to address the general case first and then focus on the specific case of the $\alpha$-complex. Moreover, while we guarantee correctness for a larger interval of the ratio $\frac{\varepsilon}{\mathcal{R}}$ compared to previous literature, most existing work addresses non-uniform sampling cases, whereas our work focuses on uniform sampling.

The vertical convexity assumption, crucial for the correctness of our algorithms, has been employed in various forms to establish collapsibility of certain classes of simplicial complexes
[1,11,21]. Similarly, bounding the angle between the manifold and the simplices used for reconstruction has been essential in prior work [6,10,22–24]. Our bound (1) remains true when replacing $\mathcal{R}$ with the local feature size of $a$, as explained in Appendix A. The thus modified bound improves upon the known bound [24, Lemma 3.5].

At last, for $d = 3$, we show in Appendix G that the restricted Delaunay complex is generically homeomorphic to $\mathcal{M}$ for $\frac{\epsilon}{\mathcal{R}} \le 0.225$. In contrast, it is proven to be homeomorphic to $\mathcal{M}$ only if $\frac{\epsilon}{\mathcal{R}} \le 0.09$ [23, Theorem 13.16], a result based on the Topological Ball Theorem [23, Theorem 13.1]. Our proof bypasses this requirement, relying instead on NaiveSquash.

**Outline.** After the preliminaries in Section 2, Section 3 defines vertically convex simplicial complexes. We introduce the concepts of upper and lower skins for these complexes and prove that both are homeomorphic to their orthogonal projection onto $\mathcal{M}$. Section 4 presents general conditions under which a simplicial complex $K$ can be transformed into a triangulation of $\mathcal{M}$ through either Naive or Practical vertical simplification. Section 5 provides conditions ensuring the topological correctness of both the naive and practical Squash algorithms and the restricted Delaunay complex. Detailed technical proofs are included in the appendices.

# 2 Preliminaries

## Subsets and submanifold.

Given a subset $X \subseteq \mathbb{R}^d$, we define several important geometric concepts. The convex hull of $X$ is denoted as $\text{conv}(X)$ and the affine space spanned by $X$ as $\text{Aff}(X)$. The interior of $X$ is denoted as $X^o$. The relative interior of $X$, denoted as $\text{relint}(X)$, represents the interior of $X$ within $\text{Aff}(X)$. For any point $x$ and radius $r$, we denote the closed ball with center $x$ and radius $r$ as $B(x, r)$. The $r$-offset of $X$, denoted as $X^{\oplus r}$, is the union of closed balls centered at each point in $X$ with radius $r$: $X^{\oplus r} = \bigcup_{x \in X} B(x, r)$. The medial axis of $X$, denoted as $\text{axis}(X)$, is the set of points in $\mathbb{R}^d$ that have at least two nearest points in $X$. The reach of $X$, denoted as $\text{Reach}(X)$, is the infimum of distances between $X$ and $\text{axis}(X)$. Furthermore, we define the projection map $\pi_X : \mathbb{R}^d \setminus \text{axis}(X) \to X$, which associates each point $x$ with its unique closest point in $X$. This projection map is well-defined on every subset of $\mathbb{R}^d$ that does not intersect $\text{axis}(X)$, particularly on every $r$-offset of $X$ with $r < \text{Reach}(X)$.

Throughout the paper, we designate $\mathcal{M}$ as a compact $\mathbb{C}^2$ submanifold of $\mathbb{R}^d$ of codimension one, and, therefore, orientable (see e.g. [45]).

Given $m \in \mathcal{M}$, we denote the affine tangent space to $\mathcal{M}$ at $m$ as $\mathbf{T}_m\mathcal{M}$ and the affine normal space as $\mathbf{N}_m\mathcal{M}$. As $\mathcal{M}$ has codimension one, $\mathbf{T}_m\mathcal{M}$ is a hyperplane and $\mathbf{N}_m\mathcal{M}$ is a line. Additionally, since $\mathcal{M}$ is $\mathbb{C}^2$, it has a positive reach [46]. For all real numbers $r$ such that $0 < r < \text{Reach}(\mathcal{M})$, the $r$-offset of $\mathcal{M}$ can be partitioned into the set of normal segments $\{\mathbf{N}_m\mathcal{M} \cap B(m, r)\}_{m \in \mathcal{M}}$ [27], that is,

$$ \mathcal{M}^{\oplus r} = \dot{\bigcup}_{m \in \mathcal{M}} \mathbf{N}_m \mathcal{M} \cap B(m, r). $$

We define $\mathbf{n}: \mathcal{M} \to \mathbb{R}^d$ as a differentiable field of unit normal vectors of $\mathcal{M}$ [27]. We let $\mathcal{R}$ be a finite arbitrary number such that $0 < \mathcal{R} \le \text{Reach}(\mathcal{M})$, fixed throughout.
Abstract simplicial complexes and collapses.

We recall some classical definitions of algebraic topology [31,43]. An abstract simplicial
complex is a collection $K$ of finite non-empty sets with the property that if $\sigma$ belongs to $K$, so does every non-empty subset of $\sigma$. Each element $\sigma$ of $K$ is called an abstract simplex and its dimension is one less than its cardinality: $\dim \sigma = \text{card} \sigma - 1$. A simplex of dimension $i$ is called an $i$-simplex and the set of $i$-simplices of $K$ is denoted as $K^{[i]}$. If $\tau$ and $\sigma$ are two simplices such that $\tau \subseteq \sigma$, then $\tau$ is called a face of $\sigma$, and $\sigma$ is called a coface of $\tau$. The $(d-1)$-dimensional faces of $\sigma$ are the facets of $\sigma$. The vertex set of $K$ is $\text{Vert } K = \bigcup_{\sigma \in K} \sigma$. A subcomplex $L$ of $K$ is a simplicial complex whose elements belong to $K$. The link of $\sigma$ in $K$, denoted $\text{Lk}(\sigma, K)$, is the set of simplices $\tau$ in $K$ such that $\tau \cup \sigma \in K$ and $\tau \cap \sigma = \emptyset$. It is a subcomplex of $K$. The star of $\sigma$ in $K$, denoted as $\text{St}(\sigma, K)$, is the set of cofaces of $\sigma$. The simplicial complex formed by all the faces of $\sigma$ is the closure of $\sigma$, $\text{Cl} \sigma$.

Consider next an abstract simplex $\sigma \subseteq \mathbb{R}^d$. One can associate it to the geometric simplex $\text{conv}(\sigma) \subseteq \mathbb{R}^d$, called the *support* of $\sigma$. In general, $\dim(\text{Aff}(\sigma)) \le \dim(\sigma)$ and we say that $\sigma$ is *non-degenerate* whenever $\dim(\text{Aff}(\sigma)) = \dim \sigma$. Given a simplicial complex $K$ with vertices in $\mathbb{R}^d$, we say that $K$ is *canonically embedded* if the following two conditions are satisfied:

1. $\dim \sigma = \dim(\text{Aff}(\sigma))$ for all $\sigma \in K$;

2. $\text{conv}(\alpha \cap \beta) = \text{conv}(\alpha) \cap \text{conv}(\beta)$ for all $\alpha, \beta \in K$.

In this paper we consider exclusively abstract simplicial complexes $K$ with vertex sets in $\mathbb{R}^d$ and which are canonically embedded.

Given such a simplicial complex, its *underlying space* (or *support*) is the point set
$|K| = \bigcup_{\sigma \in K} \text{conv}(\sigma)$. If $|K|$ is homeomorphic to $M$, then $K$ is called a *triangulation* of $M$
or is said to triangulate $M$. Since $K$ is canonically embedded, the link of every $i$-simplex
of $K$ falls into one of the following two categories: (1) it is a triangulation of the sphere of
dimension $d-i-1$ or (2) it is a proper<fnref n="1" /> subcomplex of such a triangulation. The *boundary
complex* of a simplicial complex $K$ is the subset of simplices in the second category, denoted
$\partial K$, and it holds that $|\partial K| = \partial |K|$. Simplices in $\partial K$ are referred to as *boundary simplices*
of $K$. Given a set of abstract simplices $\Sigma$, if $\sigma \in \Sigma$ has no coface in $\Sigma$ besides itself, then $\sigma$
is said to be *inclusion-maximal* in $\Sigma$.

Suppose that $\tau \in K$ is a simplex whose star in $K$ has a unique inclusion-maximal element $\sigma \neq \tau$. Then $\tau$ is said to be *free* in $K$. Equivalently, $\tau$ is free in $K$ if and only if the link of $\tau$ in $K$ is the closure of a simplex. Consequently, free simplices of $K$ are always boundary simplices of $K$. However, not all boundary simplices of $K$ are necessary free. There are instances where none of them are free, such as the famous example when $K$ triangulates the 2-dimensional subspace of $\mathbb{R}^3$, known as the “house with two rooms”. A *collapse* in $K$ is the operation that removes from $K$ a free simplex $\tau$ along with all its cofaces. This operation is known to preserve the homotopy-type of $|K|$.

Delaunay complexes, $\alpha$-complexes, and $\alpha$-shapes.

Consider a finite collection of points $P \subseteq \mathbb{R}^d$. The Voronoi region of $q \in P$ is the collection of points $x \in \mathbb{R}^d$ that are closer to $q$ than to any other points of $P$:

$$
V(q, P) = \{ x \in \mathbb{R}^d \mid \|x - q\| \le \|x - p\|, \text{ for all } p \in P \}.
$$

<footnote n="1">¹ A proper subset $A$ of $B$ is such that $A \neq B$.</footnote>
Given a subset $\sigma \subseteq P$, let $V(\sigma, P) = \bigcap_{q \in \sigma} V(q, P)$. The Delaunay complex is defined as
$$ \mathrm{Del}(P) = \{\sigma \subseteq P \mid \sigma \neq \emptyset \text{ and } V(\sigma, P) \neq \emptyset\}. $$

A simplex $\sigma \in \mathrm{Del}(P)$ is called a Delaunay simplex of $P$ and it is dual to its corresponding Voronoi cell $V(\sigma, P)$. Henceforth, we assume that the set of points $P$ is in general position. This means that no $d+2$ points of $P$ lie on the same $d$-dimensional sphere and no $k+2$ points of $P$ lie on the same $k$-dimensional flat for $k < d$. In that case, $\mathrm{Del}(P)$ is canonically embedded [36]. For $\alpha \ge 0$, the $\alpha$-complex of $P$ is the subcomplex of $\mathrm{Del}(P)$ defined by:

$$ \mathrm{Del}(P, \alpha) = \{\sigma \subseteq P \mid \sigma \neq \emptyset \text{ and } V(\sigma, P) \cap P^{\oplus \alpha} \neq \emptyset\}. $$

Its underlying space $|\mathrm{Del}(P, \alpha)| = \bigcup_{\sigma \in \mathrm{Del}(P, \alpha)} \mathrm{conv}(\sigma)$ is called the $\alpha$-shape of $P$. It has the properties: (i) $|\mathrm{Del}(P, \alpha)| \subseteq P^{\oplus \alpha}$ and (ii) $|\mathrm{Del}(P, \alpha)|$ is homotopy equivalent to $P^{\oplus \alpha}$; see [30] for more details.

<figure><img src="image_9.png" /><figcaption>■ Figure 2 Left: $P$ is such that neither $P^{\oplus \alpha}$ nor $\mathrm{Del}(P, \alpha)$ are vertically convex relative to a horizontal line. Right: Decomposition of $P^{\oplus \alpha} \setminus |\mathrm{Del}(P, \alpha)|^{\circ}$ in joins as described in [30].</figcaption></figure>

### 3 Vertically convex simplicial complexes

In this section, we define the concept of vertical convexity relative to $\mathcal{M}$ for both a set and a simplicial complex. We then study the boundary of a vertically convex simplicial complex $K$. Specifically, we divide the boundary of its underlying space into an upper and a lower skins, enabling us to identify two boundary subcomplexes: an upper and a lower ones. Furthermore, we show that each of these subcomplexes triangulates the orthogonal projection of $|K|$ onto $\mathcal{M}$ (Lemma 7). We also extend the definitions for a single $d$-simplex.

► **Definition 1 (Vertical convexity).** A set $X \subseteq \mathbb{R}^d$ is vertically convex relative to $\mathcal{M}$ if $\exists r \in [0, \mathrm{Reach}(\mathcal{M}))$ such that

1. $X \subseteq \mathcal{M}^{\oplus r}$ and

2. $\forall m \in \mathcal{M}, \mathbf{N}_m \mathcal{M} \cap B(m, r) \cap X$ is convex.

In other words, for any $m \in \mathcal{M}$, the set $\mathbf{N}_m \mathcal{M} \cap B(m, r) \cap X$ is either empty or a line segment (possibly of zero-length). A simplicial complex $K$ is vertically convex relative to $\mathcal{M}$ if its underlying space $|K|$ is.

► **Remark 2.** The assumption that there exists $r < \mathrm{Reach}(\mathcal{M})$ such that $X \subseteq \mathcal{M}^{\oplus r}$ can be satisfied in practice by choosing $X$ as the $\alpha$-shape of a point set $P$ that is contained in a $\delta$-offset of $\mathcal{M}$ with $\delta + \alpha < \mathrm{Reach}(\mathcal{M})$. Indeed, setting $r = \delta + \alpha$, we have that $|\mathrm{Del}(P, \alpha)| \subseteq P^{\oplus \alpha} \subseteq \mathcal{M}^{\oplus r}$ with $r < \mathrm{Reach}(\mathcal{M})$.

Examples of a non-vertically convex and a vertically convex simplicial complexes are provided in Figures 2 and 3, respectively.
<figure><img src="image_10.png" /><figcaption>Figure 3 A simplicial complex K vertically convex relative to the curve M. Each segment N_m M ∩ B(m, r) (in dashed orange) intersects |K| in a line segment, as highlighted (blue) for the point m (represented by a black square). Lemma 5 shows that each of the two skins of |K|, depicted in green and pink according to the labeling arrows, is homeomorphic to M.</figcaption></figure>

3.1 Upper and lower skins

Assume that X ⊆ R d is vertically convex relative to M and let m ∈ π_M(X). The endpoints (possibly equal) of the segment N_m M ∩ B(m, r) ∩ X are denoted by low_X(m) and up_X(m), with up_X(m) being above low_X(m) along the direction of the unit normal vector n(m). With this notation, X can be expressed as a union of disjoint normal segments:

$$
X = \bigcup_{m \in \pi_M(X)} [\mathrm{low}_X(m), \mathrm{up}_X(m)].
$$

The *upper skin* and *lower skin* of X are, respectively:

$$
\mathrm{UpperSkin}_{\mathcal{M}}(X) = \{\mathrm{up}_X(m) \mid m \in \pi_{\mathcal{M}}(X)\},
$$

$$
\mathrm{LowerSkin}_{\mathcal{M}}(X) = \{\mathrm{low}_X(m) \mid m \in \pi_{\mathcal{M}}(X)\}.
$$

Figure 3 displays an example. Our goal is to study the skins of |K|, for which we need two extra definitions.

► **Definition 3 (Vertical simplex).** A simplex $\sigma \subseteq \mathbb{R}^d$ such that $\mathrm{conv}(\sigma) \subseteq \mathbb{R}^d \setminus \mathrm{axis}(\mathcal{M})$ is vertical relative to $\mathcal{M}$ if there exists a pair of distinct points in $\mathrm{conv}(\sigma)$ sharing the same projection onto $\mathcal{M}$.

► **Definition 4 (Non-vertical skeleton).** Assume that $|K| \subseteq \mathbb{R}^d \setminus \mathrm{axis}(\mathcal{M})$. We say that $K$ has a non-vertical skeleton relative to $\mathcal{M}$ if $K$ contains no vertical $i$-simplices relative to $\mathcal{M}$ for all integers $0 < i < d$.

The next lemma is a key property of vertically convex simplicial complexes:

► **Lemma 5.** Suppose that $K$ is vertically convex and has a non-vertical skeleton relative to $\mathcal{M}$. Then, the upper and lower skins of $|K|$ are closed sets, each homeomorphic to $\pi_{\mathcal{M}}(|K|)$. The homeomorphism is realized in both cases by $\pi_{\mathcal{M}}$. In addition,

$$
\partial|K| = \mathrm{UpperSkin}_{\mathcal{M}}(|K|) \cup \mathrm{LowerSkin}_{\mathcal{M}}(|K|). \tag{2}
$$
A simple consequence follows:

**Lemma 6.** Let $K$ be vertically convex and with non-vertical skeleton relative to $\mathcal{M}$. If $\text{UpperSkin}_{\mathcal{M}}(|K|) = \text{LowerSkin}_{\mathcal{M}}(|K|)$, then $K = \partial K$.

Aiming for a simplicial version of Equation (2), we define the *upper complex* of $K$ and the *lower complex* of $K$ relative to $\mathcal{M}$ as follows:

$$ \text{UpperComplex}_{\mathcal{M}}(K) = \{\nu \subseteq \partial K \mid \text{conv}(\nu) \subseteq \text{UpperSkin}_{\mathcal{M}}(|K|)\}, $$

$$ \text{LowerComplex}_{\mathcal{M}}(K) = \{\nu \subseteq \partial K \mid \text{conv}(\nu) \subseteq \text{LowerSkin}_{\mathcal{M}}(|K|)\}. $$

By construction, both are subcomplexes of $\partial K$. A combinatorial equivalent of Lemma 5 is:

**Lemma 7.** Let $K$ be vertically convex with non-vertical skeleton relative to $\mathcal{M}$. Then,

$$ |\text{UpperComplex}_{\mathcal{M}}(K)| = \text{UpperSkin}_{\mathcal{M}}(|K|), $$

$$ |\text{LowerComplex}_{\mathcal{M}}(K)| = \text{LowerSkin}_{\mathcal{M}}(|K|) \text{ and} $$

$$ \partial K = \text{UpperComplex}_{\mathcal{M}}(K) \cup \text{LowerComplex}_{\mathcal{M}}(K). $$

Moreover, if $\pi_{\mathcal{M}}(|K|) = \mathcal{M}$, both $\text{UpperComplex}_{\mathcal{M}}(K)$ and $\text{LowerComplex}_{\mathcal{M}}(K)$ are triangulations of $\mathcal{M}$.

## 3.2 Upper and lower facets of a $d$-simplex

Let $\sigma$ be a non-degenerate $d$-simplex of $\mathbb{R}^d$ such that $\text{conv}(\sigma) \subseteq \mathcal{M}^{\oplus r}$ for some $r < \text{Reach}(\mathcal{M})$. In that case, $\text{Cl}\sigma$ is embedded and vertically convex relative to $\mathcal{M}$. The facets of $\sigma$ can be partitioned into *upper facets* and *lower facets* of $\sigma$ relative to $\mathcal{M}$ as follows:

$$ \text{UpperFacets}_{\mathcal{M}}(\sigma) = \{\nu \text{ facet of } \sigma \mid \nu \in \text{UpperComplex}_{\mathcal{M}}(\text{Cl}\sigma)\} $$

$$ \text{LowerFacets}_{\mathcal{M}}(\sigma) = \{\nu \text{ facet of } \sigma \mid \nu \in \text{LowerComplex}_{\mathcal{M}}(\text{Cl}\sigma)\}. $$

An example can be seen in Figure 4, where one can also observe the following property:

<figure><img src="image_11.png" /><figcaption>■ **Figure 4** Upper (smooth green edges) and lower (dotted pink edge) facets of a 2-simplex $\sigma \subseteq \mathbb{R}^2$.</figcaption></figure>

**Lemma 8.** Consider a non-degenerate $d$-simplex $\sigma \subseteq \mathbb{R}^d$ such that $\text{conv}(\sigma) \subseteq \mathcal{M}^{\oplus r}$ for some $r < \text{Reach}(\mathcal{M})$. If $\sigma$ has no vertical facets relative to $\mathcal{M}$, then $\text{UpperFacets}_{\mathcal{M}}(\sigma)$ and $\text{LowerFacets}_{\mathcal{M}}(\sigma)$ are non-empty sets that partition the facets of $\sigma$.
# 4 Vertically collapsing simplicial complexes

In this section, assuming that $|K| \subseteq \mathcal{M}^{\oplus r}$ for some $r < \text{Reach}(\mathcal{M})$, we introduce an algorithm for simplifying $K$ using vertical collapses relative to $\mathcal{M}$ (Section 4.1) and establish conditions for when it outputs a triangulation of $\mathcal{M}$ (Section 4.2). We first present a naive version that requires the knowledge of $\mathcal{M}$ and then present a practical version (Section 4.3).

## 4.1 Naive algorithm

► **Definition 9 (Vertically free simplices).** A simplex $\tau$ is said to be free from above (resp., free from below) in $K$ relative to $\mathcal{M}$ if

■ $\tau$ is a free simplex of $K$;

■ the unique inclusion-maximal simplex $\sigma$ in $\text{St}(\tau, K)$ has dimension $d$;

■ the set of $(d-1)$-simplices in $\text{St}(\tau, K)$ is exactly the set of upper (resp., lower) facets of $\sigma$ relative to $\mathcal{M}$.

We say that $\tau$ is vertically free in $K$ relative to $\mathcal{M}$ if $\tau$ is either free from above or from below in $K$ relative to $\mathcal{M}$.

See Figures 5 and 7 for a depiction. Note that the definition can be naturally extended to non-compact $\mathcal{M}$. In particular, it holds for hyperplanes, a fact that we use in Algorithm 2.

► **Definition 10 (Vertical collapse).** A vertical collapse of $K$ relative to $\mathcal{M}$ is the operation of removing the star of a simplex $\tau \in K$ that is vertically free relative to $\mathcal{M}$.

<figure><img src="image_12.png" /><figcaption>■ **Figure 5** Schematic drawings of $K$ in blue (smooth filled areas). Top row: the edge $\tau$ is free but not vertically free relative to $\mathcal{M}$ and collapsing $\tau$ does not preserve the vertical convexity of $K$. Bottom row: the vertex $\tau$ is free from above relative to $\mathcal{M}$, so that collapsing $\tau$ preserves the vertical convexity of $K$ (Lemma 14). The $(d-1)$-simplices of $K$ that disappear with $\tau$ are precisely the upper facets of $\sigma$ (smooth edges, in green).</figcaption></figure>
A vertical collapse of $K$ can be seen as compressing the underlying space of $K$ by shifting its upper or lower skin along directions normal to $M$; see Figure 5. Our first algorithm, outlined in Algorithm 1, simplifies $K$ by iteratively applying vertical collapses relative to $M$. It is worth noting that the algorithm operates on any simplicial complex $K$ with $|K| \subseteq M^{\oplus r}$ for $r < \text{Reach}(M)$, irrespective of whether $K$ is vertically convex relative to $M$ or not.

**Algorithm 1 NaiveVerticalSimplification(K)**

while there is a simplex $\tau$ vertically free in $K$ relative to $M$ do
  Collapse $\tau$ in $K$;

end while

## 4.2 Correctness

We now establish conditions under which NaiveVerticalSimplification($K$) transforms $K$ into a triangulation of $M$. For that, we introduce a binary relation over $d$-simplices:

► **Definition 11** (Below relation $\prec_M$). Let $\sigma_0, \sigma_1 \subseteq \mathbb{R}^d$ be two $d$-simplices sharing a common facet $\nu = \sigma_0 \cap \sigma_1$ and let $\text{conv}(\sigma_0) \cup \text{conv}(\sigma_1) \subseteq M^{\oplus r}$ for some $r < \text{Reach}(M)$. We say that $\sigma_0$ is below $\sigma_1$ (or that $\sigma_1$ is above $\sigma_0$) relative to $M$, denoted $\sigma_0 \prec_M \sigma_1$, if $\nu$ is an upper facet of $\sigma_0$ and a lower facet of $\sigma_1$ relative to $M$.

Note that the relation $\prec_M$ is not acyclic in general, see Figure 6.

<figure><img src="image_13.png" /><figcaption>**Figure 6** Non-Delaunay triangles that form a cycle in the $\prec_M$ relation and their dual graph.</figcaption></figure>

► **Theorem 12** (Correctness). Consider $K$ such that $|K| \subseteq M^{\oplus r}$ for some $r < \text{Reach}(M)$ and assume the following:

**Injective projection:** $K$ has a non-vertical skeleton relative to $M$.

**Covering projection:** $\pi_M(|K|) = M$.

**Vertical convexity:** $K$ is vertically convex relative to $M$.

**Acyclicity:** $\prec_M$ is acyclic over $d$-simplices of $K$.

Then, NaiveVerticalSimplification($K$) transforms $K$ into a triangulation of $M$.

The remaining of this section aims to prove Theorem 12 and we consider $K$ such that $|K| \subseteq M^{\oplus r}$ for some $r < \text{Reach}(M)$. Using the relation $\prec_M$, associate to $K$ its dual graph
$G_M(K)$ that has one node for each $d$-simplex of $K$ and one arc for each pair of $d$-simplices $\sigma_0, \sigma_1 \in K$ that share a common facet $\sigma_0 \cap \sigma_1$. Direct an arc from $\sigma_0$ to $\sigma_1$ if $\sigma_0 \prec_M \sigma_1$, and from $\sigma_1$ to $\sigma_0$ otherwise. Since either $\sigma_0 \prec_M \sigma_1$ or $\sigma_1 \prec_M \sigma_0$, this yields a well-defined orientation for each arc in the dual graph. Figures 6 and 7 show examples.

<figure><img src="image_14.png" /><figcaption>■ **Figure 7** A vertically convex simplicial complex $K$ relative to $\mathcal{M}$. All free simplices are highlighted by thickness. There are four simplices free from below (represented by three dotted edges and one triangular vertex, in pink) and four simplices free from above (represented by two dashed edges and two square vertices, in green). The dual graph (oriented edges, in blue) has four sources (vertices filled by dots, in pink) and four sinks (vertices with a smooth filling, in green), in one-to-one correspondence with the free simplices from below and above.</figcaption></figure>

In a directed graph, a *source* is a node with only outgoing arcs, while a *sink* is a node with only incoming arcs. The next lemma states that a vertical collapse in $K$ corresponds to the removal of either a sink or a source in $G_M(K)$ and conversely. For that, given a finite set of abstract simplices $\Sigma = \{\sigma_1, \sigma_2, \dots, \sigma_k\}$, let $\bigcap \Sigma = \bigcap_{i=1}^k \sigma_i$ denote the set of vertices that belong to all simplices in $\Sigma$. If $\bigcap \Sigma \neq \emptyset$, it forms an abstract simplex.

**Lemma 13 (Sinks and sources).** Consider $K$ such that $|K| \subseteq \mathcal{M}^{\oplus r}$ for some $r < \text{Reach}(\mathcal{M})$ and assume that $K$ satisfies the injective projection, covering projection and vertical convexity assumptions of Theorem 12. Consider a $d$-simplex $\sigma \in K$ and let $\tau = \bigcap \text{UpperFacets}_\mathcal{M}(\sigma)$ and $\tau' = \bigcap \text{LowerFacets}_\mathcal{M}(\sigma)$. Then,

- $\tau$ is a free simplex of $K$ from above relative to $\mathcal{M} \iff \sigma$ is a sink of $G_M(K)$.

- $\tau'$ is a free simplex of $K$ from below relative to $\mathcal{M} \iff \sigma$ is a source of $G_M(K)$.

The next lemma provides an invariant for the while-loop of Algorithm 1.

**Lemma 14 (Loop invariant).** Consider $K$ such that $|K| \subseteq \mathcal{M}^{\oplus r}$ for some $r < \text{Reach}(\mathcal{M})$. Let $\tau$ be a vertically free simplex in $K$ relative to $\mathcal{M}$. Let $K'$ be obtained from $K$ by collapsing $\tau$ in $K$. If $K$ satisfies the assumptions of Theorem 12, then so does $K'$.

**Proof of Theorem 12.** Since $K$ is vertically convex relative to $\mathcal{M}$ and $\pi_\mathcal{M}(|K|) = \mathcal{M}$, the set $N_m\mathcal{M} \cap B(m, r) \cap |K|$ forms a segment for all $m \in \mathcal{M}$. The endpoints of this segment are denoted $\text{low}_K(m)$ and $\text{up}_K(m)$. First, we show that for all $m \in \mathcal{M}$, if $\text{low}_K(m) \neq \text{up}_K(m)$, then the segment $[\text{low}_K(m), \text{up}_K(m)]$ intersects the support of at least one $d$-simplex of $K$, implying $G_M(K) \neq \emptyset$. Suppose, for a contradiction, that $[\text{low}_K(m), \text{up}_K(m)]$ only intersects
the support of $i$-simplices of $K$ for $i < d$. As $\text{low}_K(m) \neq \text{up}_K(m)$ and $K$ has a finite number of simplices, at least one of these $i$-simplices, say $\nu$, intersects $[\text{low}_K(m), \text{up}_K(m)]$ in a non-zero length segment containing distinct points $x, y \in \text{conv}(\nu) \cap [\text{low}_K(m), \text{up}_K(m)]$. Hence, $x$ and $y$ share the same orthogonal projection $m$ onto $M$, implying that $\nu$ is vertical relative to $M$. This contradicts the injective projection assumption on $K$. Thus,

$$ \exists m \in \mathcal{M}, \text{ low}_K(m) \neq \text{up}_K(m) \implies G_{\mathcal{M}}(K) \neq \emptyset. \qquad (3) $$

We now prove the correctness of NaiveVerticalSimplification($K$). The algorithm starts with $K$ that satisfies the theorem assumptions and by Lemma 14, after each iteration of the while-loop we obtain a new $K$ that continues to satisfy those assumptions. Since each iteration involves a vertical collapse of $K$ relative to $M$, the number of $d$-simplices of $K$ is reduced. Thus, the algorithm must terminate. Upon termination, there are no vertically free simplices in $K$ relative to $M$. By Lemma 13, this implies that $G_{\mathcal{M}}(K)$ has no terminal node (neither a source nor a sink) and is therefore empty. The contrapositive of (3) yields that for all $m \in \mathcal{M}$, $\text{low}_K(m) = \text{up}_K(m)$. In other words, when Algorithm 1 terminates, $\text{LowerSkin}_{\mathcal{M}}(K) = \text{UpperSkin}_{\mathcal{M}}(K)$. By Lemma 6, we have $K = \partial K$ and Lemma 7 implies

$$ K = \partial K = \text{UpperComplex}_{\mathcal{M}}(K) = \text{LowerComplex}_{\mathcal{M}}(K), $$

with $K$ being a triangulation of $M$.

## 4.3 Practical version

Algorithm 1 relies on knowledge of $M$, which renders it impractical for implementation since $M$ is typically unknown. In this section, we introduce Algorithm 2, a feasible variant that is correct if the $(d-1)$-simplices of $K$ form a sufficiently small angle with $M$; see Appendix A for a definition of the angle between affine spaces. In this variant, we assign an affine space $\mathcal{H}_\tau$ to each $\tau \in K$: for a free simplex $\tau$ with a $d$-dimensional coface $\sigma$, $\mathcal{H}_\tau$ is defined as the hyperplane spanned by any facet of $\sigma$. Otherwise, set $\mathcal{H}_\tau = \emptyset$.

**Algorithm 2** PracticalVerticalSimplification($K$)

while there is a simplex $\tau$ vertically free in $K$ relative to $\mathcal{H}_\tau$ do
  Collapse $\tau$ in $K$;

end while

**► Theorem 15 (Correctness).** Suppose that $K$ satisfies the assumptions of Theorem 12 and, in addition, for all $(d-1)$-simplices $\nu$ of $K$

$$ \max_{a \in \nu} \angle (\text{Aff}(\nu), \mathbf{T}_{\pi_{\mathcal{M}}(a)}\mathcal{M}) < \frac{\pi}{4}. \qquad (4) $$

Then, PracticalVerticalSimplification($K$) transforms $K$ into a triangulation of $M$.

# 5 Correct reconstructions from $\alpha$-complexes

In this section, we assume that $M$ is sampled by a finite point set $P$ and consider Algorithms 3 and 4, which apply vertical collapses to $\text{Del}(P, \alpha)$ either straightforwardly or practically. We introduce two parameters, $\varepsilon \ge 0$ and $\delta \ge 0$, to control the sample density and noise of $P$, respectively, and a scale parameter $\alpha \ge 0$. Section 5.1 establishes conditions ensuring the correctness of Algorithms 3 and 4, with the proof outlined in Section 5.2. Section 5.3 shows how these conditions hold for a wide range of $\varepsilon/R$ and $\alpha/R$ when $M$ is a surface in $\mathbb{R}^3$ and $P$ is noiseless. This result is extended to the restricted Delaunay complex of $P$ in Section 5.4.
■ Algorithm 3 NaiveSquash($P, \alpha$)

$K \leftarrow \text{Del}(P, \alpha)$; NaiveVerticalSimplification($K$); return $K$;

■ Algorithm 4 PracticalSquash($P, \alpha$)

$K \leftarrow \text{Del}(P, \alpha)$; PracticalVerticalSimplification($K$); return $K$;

## 5.1 Sampling and angular conditions in $\mathbb{R}^d$

The next definition enables us to express our results in $\mathbb{R}^d$ more concisely.

**Definition 16 (Strict homotopy condition).** We say that $\varepsilon, \delta \ge 0$ satisfy the strict homotopy condition if $(\mathcal{R} - \delta)^2 - \varepsilon^2 > (4\sqrt{2} - 5)\mathcal{R}^2$ for $\delta \le \varepsilon$ and $\varepsilon + \sqrt{2}\delta < (\sqrt{2} - 1)\mathcal{R}$ for $\delta \ge \varepsilon$.

Let $I(\varepsilon, \delta)$ be an interval of $\alpha$ values so that $P^{\oplus\alpha}$ is vertically convex with relation to $\mathcal{M}$. The exact definition can be found in Appendix D.1. The fact that this interval guarantees vertical convexity follows from the specialization of Propositions 5 and 7 in [7] to the case where $\mathcal{M}$ has codimension-one:

**Theorem 17 (Specialization of [7]).** Suppose that $\mathcal{M} \subseteq P^{\oplus\varepsilon}$ and $P \subseteq \mathcal{M}^{\oplus\delta}$ with $\varepsilon, \delta \ge 0$ that satisfy the strict homotopy condition. Then, for all $\alpha \in I(\varepsilon, \delta)$, $\pi_{\mathcal{M}}(P^{\oplus\alpha}) = \mathcal{M}$ and $P^{\oplus\alpha}$ is vertically convex relative to $\mathcal{M}$. Thus, $P^{\oplus\alpha}$ has associated upper and lower skins and deformation-retracts onto $\mathcal{M}$ along $\pi_{\mathcal{M}}$. In addition, the two skins partition $\partial P^{\oplus\alpha}$.

The above concepts can be put together to state our main theorem:

**Theorem 18.** Assume $\mathcal{M} \subseteq P^{\oplus\varepsilon}$ and $P \subseteq \mathcal{M}^{\oplus\delta}$ for $\varepsilon, \delta \ge 0$ that satisfy the strict homotopy condition. Let $\alpha \in [\delta, \frac{2(\mathcal{R}-\delta)}{3}) \cap I(\varepsilon, \delta)$ and $\beta > 0$ such that $\mathcal{M}^{\oplus\beta} \subseteq P^{\oplus\alpha}$. Suppose that for all $i$-simplices $\tau \in \text{Del}(P, \alpha)$, $0 < i < d$ and all $(d-1)$-simplices $\nu \in \text{Del}(P, \alpha)$ it holds:

$$ \max_{x \in \text{conv}(\tau)} \angle(\text{Aff}(\tau), \mathbf{T}_{\pi_{\mathcal{M}}(x)}\mathcal{M}) < \frac{\pi}{2}, \qquad (5) $$

$$ \min_{a \in \tau} \angle(\text{Aff}(\tau), \mathbf{T}_{\pi_{\mathcal{M}}(a)}\mathcal{M}) < \arcsin \left( \frac{(\mathcal{R} + \beta)^2 - (\mathcal{R} + \delta)^2 - \alpha^2}{2(\mathcal{R} + \delta)\alpha} \right) \text{ and} \qquad (6) $$

$$ \min_{x \in \text{conv}(\nu)} \angle(\text{Aff}(\nu), \mathbf{T}_{\pi_{\mathcal{M}}(x)}\mathcal{M}) < \frac{\pi}{2} - 2\arcsin\left(\frac{\alpha}{2(\mathcal{R} - \delta - \alpha)}\right). \qquad (7) $$

Then, $\text{Del}(P, \alpha)$ satisfies the injective projection, covering projection, vertical convexity and acyclicity assumptions of Theorem 12. Furthermore, both the upper and lower complexes of $\text{Del}(P, \alpha)$ relative to $\mathcal{M}$ are triangulations of $\mathcal{M}$ and NaiveSquash($P, \alpha$) returns a triangulation of $\mathcal{M}$.

One can check that Conditions (5), (6) and (7) are well-defined; see Remark E1.

**Corollary 19.** Suppose the assumptions of Theorem 18 are satisfied and furthermore that for all $(d-1)$-simplices $\nu \in \text{Del}(P, \alpha)$,

$$ \max_{a \in \nu} \angle(\text{Aff}(\nu), \mathbf{T}_{\pi_{\mathcal{M}}(a)}\mathcal{M}) < \frac{\pi}{4}. \qquad (8) $$

Then, PracticalSquash($P, \alpha$) returns a triangulation of $\mathcal{M}$.
<figure><img src="image_15.png" /><figcaption>■ **Figure 8** Decomposing $P^{\oplus\alpha} \setminus |\text{Del}(P, \alpha)|^{\circ}$ into upper joins (hashed, in green) and lower joins (dotted, in pink).</figcaption></figure>

## 5.2 Partial proof technique for Theorem 18

In this section, we provide an overview of how to establish the covering projection and vertical convexity of $\text{Del}(P, \alpha)$ as guaranteed by Theorem 18. The complete proof of that theorem, which is unfortunately too lengthy to include here, can be found in Appendix E.

**► Lemma 20.** Assume $\mathcal{M} \subseteq P^{\oplus\epsilon}$ and $P \subseteq \mathcal{M}^{\oplus\delta}$ for $\epsilon, \delta \ge 0$ that satisfy the strict homotopy condition. Let $\alpha \in [\delta, R - \delta) \cap I(\epsilon, \delta)$ and $\beta > 0$ be such that $\mathcal{M}^{\oplus\beta} \subseteq P^{\oplus\alpha}$. Suppose that for all $i$-simplices $\tau \in \text{Del}(P, \alpha)$ with $0 < i < d$, Conditions (5) and (6) hold. Then, $\pi_{\mathcal{M}}(|\text{Del}(P, \alpha)|) = \mathcal{M}$ and $\text{Del}(P, \alpha)$ is vertically convex relative to $\mathcal{M}$.

**Upper and lower joins.** For proving this lemma, we introduce upper and lower joins. Consider $\mathcal{M}$, $P$, $\epsilon$, $\delta$, $\alpha$ and $\beta$ that satisfy the assumptions of Lemma 20 and notice that they also meet the conditions of Theorem 17. Therefore, $P^{\oplus\alpha}$ has associated upper and lower skins and the two skins form a partition of $\partial P^{\oplus\alpha}$. Using that partition, we decompose the set difference $P^{\oplus\alpha} \setminus |\text{Del}(P, \alpha)|^{\circ}$ into upper and lower joins, slightly adapting what is done in [30]; see Figures 2 and 8. For that, notice that $\partial P^{\oplus\alpha}$ can be decomposed into faces, each face being the restriction of $\partial P^{\oplus\alpha}$ to a Voronoi cell of $P$. There is a one-to-one correspondence between simplices of $\partial \text{Del}(P, \alpha)$ and faces of $\partial P^{\oplus\alpha}$: the simplex $\tau \in \partial \text{Del}(P, \alpha)$ corresponds to the face $F_{\tau} = V(\tau, P) \cap \partial P^{\oplus\alpha}$ and conversely. We can further partition each face $F_{\tau}$ of $\partial P^{\oplus\alpha}$ into a portion $F_{\tau}^{+}$ that lies on the upper skin of $\partial P^{\oplus\alpha}$ and a portion $F_{\tau}^{-}$ that lies on the lower skin of $\partial P^{\oplus\alpha}$. Note that $F_{\tau}^{+}$ or $F_{\tau}^{-}$ can be empty. We refer to $F_{\tau}^{+}$ as an upper face and $F_{\tau}^{-}$ as a lower face. The set of upper faces decompose the upper skin, while the set of lower faces decompose the lower skin. A join $X * Y$ is defined as the set of segments $[x, y]$ where $x \in X$ and $y \in Y$ [30]. We call $F_{\tau}^{+} * \text{conv}(\tau)$ an *upper join* and $F_{\tau}^{-} * \text{conv}(\tau)$ a *lower join*. The next lemma, proved in Appendix E.2, identifies points in $\partial|\text{Del}(P, \alpha)|$ that are connected to upper or lower joins.

**► Remark 21.** The collection of upper and lower joins cover the set $P^{\oplus\alpha} \setminus |\text{Del}(P, \alpha)|^{\circ}$.
**Remark 22.** If an upper join and a lower join have a non-empty intersection, the common intersection belongs to $|\text{Del}(P, \alpha)|$.

**Lemma 23.** *Under the assumptions of Lemma 20, let $\gamma \in \text{Del}(P, \alpha)$ and $x \in \text{relint}(\text{conv}(\gamma))$. If for some $\lambda > 0$ (resp. $\lambda < 0$), the segment $(x, x + \lambda \mathbf{n}(\pi_M(x))|$ lies outside $|\text{Del}(P, \alpha)|$, then it intersects an upper (resp. lower join).*

**Proof of Lemma 20.** Consider $\mathcal{M}$, $P$, $\varepsilon$, $\delta$, $\alpha$ and $\beta$ that satisfy the assumptions of Lemma 20. As noted before, they also meet the conditions of Theorem 17. Therefore, $\pi_M(P^{\oplus\alpha}) = \mathcal{M}$ and $P^{\oplus\alpha}$ is vertically convex relative to $\mathcal{M}$. Hence, there exists $r < \text{Reach}(\mathcal{M})$ such that $P^{\oplus\alpha} \subseteq \mathcal{M}^r$ and $P^{\oplus\alpha} \cap \mathbf{N}_m\mathcal{M} \cap B(m, r)$ is a line segment for any $m \in \mathcal{M}$. Fix $m \in \mathcal{M}$ arbitrarily. We show that $|\text{Del}(P, \alpha)| \cap \mathbf{N}_m\mathcal{M} \cap B(m, r)$ is also a line segment.

First, let us establish that it is non empty. Let $u^+$ (resp. $u^-$) be the endpoint of the segment $P^{\oplus\alpha} \cap \mathbf{N}_m\mathcal{M} \cap B(m, r)$ that lies on the upper (resp. lower) skin of $P^{\oplus\alpha}$ and hence is contained in an upper (resp. lower) join. By Remark 21, the entire segment $[u^+, u^-]$ is covered by upper and lower joins. Thus, at some point $c$ of $[u^+, u^-]$, an upper join and a lower join intersect. By Remark 22, such an intersection places $c$ on $|\text{Del}(P, \alpha)|$ as well.

<figure><img src="image_16.png" /><figcaption>**Figure 9** Reaching a contradiction in the proof of Lemma 20. We see the simplices of $\text{Del}(P, \alpha)$ whose support intersects $\mathbf{N}_m\mathcal{M} \cap B(m, r)$ (smooth filling, in pale blue) and one upper (hashed, in green) and one lower (dotted, in pink) joins that intersect $[a, b]$.</figcaption></figure>

Second, we show by contradiction that $|\text{Del}(P, \alpha)| \cap \mathbf{N}_m\mathcal{M} \cap B(m, r)$ is connected. Suppose that $a, b \in |\text{Del}(P, \alpha)| \cap \mathbf{N}_m\mathcal{M} \cap B(m, r)$ are such that $[a, b] \cap |\text{Del}(P, \alpha)| = \{a, b\}$ with $a$ being above $b$ along the direction of $\mathbf{n}(m)$. Since $a, b \in |\text{Del}(P, \alpha)| \subseteq P^{\oplus\alpha}$ and $P^{\oplus\alpha}$ is vertically convex, the segment $[a, b]$ is contained in $P^{\oplus\alpha}$. By Remark 21, the entire segment $[a, b]$ is covered by upper and lower joins. Let $\gamma_a$ and $\gamma_b$ be the simplices of $\text{Del}(P, \alpha)$ that contain $a$ and $b$, respectively, in their relative interior. Letting $\lambda = \frac{|a-b|}{2}$, then both segments $(a, a - \lambda \mathbf{n}(m)]$ and $(b, b + \lambda \mathbf{n}(m)]$ lie outside $|\text{Del}(P, \alpha)|$. It follows, by Lemma 23, that there
are at least one lower and one upper joins among the joins that cover $(a, b)$; see Figure 9. Hence, an upper and a lower joins intersect at a point $c$ of the segment $(a, b)$. By Remark 22, $c$ lies in $|\mathrm{Del}(P, \alpha)|$, a contradiction. Therefore, for all $m \in \mathcal{M}$, $|\mathrm{Del}(P, \alpha)| \cap \mathbf{N}_m \mathcal{M} \cap B(m, r)$ is non-empty and connected, thus forming a line segment. ◀

### 5.3 Sampling conditions for surfaces in $\mathbb{R}^3$.

Theorem 18 requires that the $i$-simplices of $\mathrm{Del}(P, \alpha)$ form a small angle with the manifold $\mathcal{M}$, for $0 < i < d$. Ensuring this can be challenging in practice, especially for $i \ge 3$. However, in the specific case of noiseless edges ($i = 1$) or triangles ($i = 2$), it is possible to upper bound the angle these simplices form with $\mathcal{M}$. For edges, it is known that:

* **Lemma 24** ([15, Lemma 7.8]). If $ab$ is a non-degenerate edge with $a, b \in \mathcal{M}$, then

$$ \sin \angle \mathrm{Aff}(ab), \mathbf{T}_a \mathcal{M} \le \frac{\|b-a\|}{2\mathcal{R}}. $$

For triangles, let $\rho(\tau)$ be the radius of the smallest $(d-1)$-sphere circumscribing $\tau$. We establish a simple bound that is tighter than the previous one (see [24, Lemma 3.5]):

* **Lemma 25.** If $abc$ is a non-degenerate triangle with longest edge $bc$, for $a, b, c \in \mathcal{M}$, then

$$ \sin \angle \mathrm{Aff}(abc), \mathbf{T}_a \mathcal{M} \le \frac{\rho(abc)}{\mathcal{R}} \quad \text{if } abc \text{ is an obtuse triangle and} $$

$$ \sin \angle \mathrm{Aff}(abc), \mathbf{T}_a \mathcal{M} \le \frac{\sqrt{3} \rho(abc)}{\mathcal{R}} \quad \text{if } abc \text{ is an acute triangle.} $$

If $abc$ is obtuse, the bound is tight and happens when $\mathcal{M}$ is a sphere of radius $\mathcal{R}$.

The proof is technical and is therefore provided in Appendix A. For the same reason, Appendix F includes the proof of the following result, where we use the bounds for edges and triangles to establish sampling conditions for surfaces in $\mathbb{R}^3$. Let us define

$$ \beta_{\varepsilon, \alpha} = -\frac{\varepsilon^2}{2\mathcal{R}} + \sqrt{\alpha^2 + \frac{\varepsilon^4}{4\mathcal{R}^2} - \varepsilon^2}, $$

which is one particular value of $\beta$ that guarantees $\mathcal{M}^{\oplus\beta} \subseteq P^{\oplus\alpha}$; see Appendix D.2.

* **Theorem 26.** Let $\mathcal{M}$ be a $\mathbb{C}^2$ surface in $\mathbb{R}^3$ whose reach is at least $\mathcal{R} > 0$. Let $P$ be a finite point set such that $P \subseteq \mathcal{M} \subseteq P^{\oplus\varepsilon}$.

1. For all $\varepsilon, \alpha \ge 0$ that satisfy $\frac{\sqrt{3}\alpha}{\mathcal{R}} < \min\left\{\frac{(\mathcal{R}+\beta_{\varepsilon,\alpha})^2-\mathcal{R}^2-\alpha^2}{2\mathcal{R}\alpha}, \cos(2\arcsin(\frac{\alpha}{\mathcal{R}}))\right\}$,
    - the upper and lower complexes of $\mathrm{Del}(P, \alpha)$ relative to $\mathcal{M}$ are triangulations of $\mathcal{M}$;
    - NaiveSquash$(P, \alpha)$ returns a triangulation of $\mathcal{M}$.

2. For all $\varepsilon, \alpha \ge 0$ that satisfy in addition $\frac{\sqrt{3}\alpha}{\mathcal{R}} < \sin(\frac{\pi}{4} - 2\arcsin(\frac{\alpha}{\mathcal{R}}))$,
    - PracticalSquash$(P, \alpha)$ returns a triangulation of $\mathcal{M}$.

The pairs of $(\frac{\varepsilon}{\mathcal{R}}, \frac{\alpha}{\mathcal{R}})$ that satisfy 1 and 2 are depicted in Figures 10a and 10b, respectively.

* **Remark 27.** In particular, 1 holds for $\frac{\varepsilon}{\mathcal{R}} \le 0.225$ and $\frac{\alpha}{\mathcal{R}} = 0.359$; and 2 for $\frac{\varepsilon}{\mathcal{R}} \le 0.178$ and $\frac{\alpha}{\mathcal{R}} = 0.207$, better bounds than the previous existing ones [23, Theorem 13.16][25].
<figure><img src="image_17.png" /><figcaption>Figure 10 Pairs of $(\frac{\varepsilon}{\mathbb{R}}, \frac{\alpha}{\mathbb{R}})$ for which NaiveSquash$(P, \alpha)$ (a) and PracticalSquash$(P, \alpha)$ (b) are correct, for $P \subseteq \mathcal{M} \subseteq P^{\oplus\varepsilon}$ and $d = 3$.</figcaption></figure>

## 5.4 The restricted Delaunay complex

We recall from [34] that the restricted Delaunay complex is

$$ \mathrm{Del}_{\mathcal{M}}(P) = \{\sigma \subseteq P \mid \sigma \neq \emptyset \text{ and } V(\sigma, P) \cap \mathcal{M} \neq \emptyset\}. $$

**Theorem 28.** Let $\mathcal{M}$ be a $\mathbb{C}^2$ surface in $\mathbb{R}^3$ whose reach is at least $\mathcal{R} > 0$. Let $P$ be a finite set such that $P \subseteq \mathcal{M} \subseteq P^{\oplus\varepsilon}$ for $0 \le \frac{\varepsilon}{\mathcal{R}} \le 0.225$. Under the additional generic assumption that all Voronoi cells of $P$ intersect $\mathcal{M}$ transversally, $\mathrm{Del}_{\mathcal{M}}(P)$ is a triangulation of $\mathcal{M}$.
References

1 Karim Adiprasito and Bruno Benedetti. Barycentric subdivisions of convex complexes are collapsible. *Discrete & Computational Geometry*, 64(3):608–626, 2020.

2 Marc Alexa, Johannes Behr, Daniel Cohen-Or, Shachar Fleishman, David Levin, and Claudio T Silva. Point set surfaces. In *Proceedings Visualization, 2001. VIS'01.*, pages 21–29. IEEE, 2001.

3 N. Amenta and M. Bern. Surface reconstruction by Voronoi filtering. *Discrete and Computational Geometry*, 22(4):481–504, 1999.

4 Nina Amenta, Sunghee Choi, Tamal K. Dey, and Naveen Leekha. A simple algorithm for homeomorphic surface reconstruction. *Int. J. Comput. Geom. Appl.*, 12(1-2):125–141, 2002. doi:10.1142/S0218195902000773.

5 Nina Amenta, Sunghee Choi, and Ravi Krishna Kolluri. The power crust. In David C. Anderson and Kunwoo Lee, editors, *Sixth ACM Symposium on Solid Modeling and Applications, Sheraton Inn, Ann Arbor, Michigan, USA, June 4-8, 2001*, pages 249–266. ACM, 2001. doi:10.1145/376957.376986.

6 D. Attali and A. Lieutier. Flat delaunay complexes for homeomorphic manifold reconstruction, 2022. arXiv:arXiv:2203.05943.

7 Dominique Attali, Hana Dal Poz Kouřimská, Christopher Fillmore, Ishika Ghosh, André Lieutier, Elizabeth Stephenson, and Mathijs Wintraecken. Tight bounds for the learning of homotopy à la Niyogi, Smale, and Weinberger for subsets of Euclidean spaces and of Riemannian manifolds. In *Proc. 26th Ann. Sympos. Comput. Geom.*, Athens, Greece, June 11-14 2024.

8 Dominique Attali, Hana Dal Poz Kouřimská, Christopher Fillmore, Ishika Ghosh, André Lieutier, Elizabeth Stephenson, and Mathijs Wintraecken. Tight bounds for the learning of homotopy à la Niyogi, Smale, and Weinberger for subsets of Euclidean spaces and of Riemannian manifolds, 2024. arXiv:2206.10485.

9 Dominique Attali and André Lieutier. Geometry-driven collapses for converting a čech complex into a triangulation of a nicely triangulable shape. *Discret. Comput. Geom.*, 54(4):798–825, 2015. doi:10.1007/s00454-015-9733-7.

10 Dominique Attali and André Lieutier. Delaunay-like triangulation of smooth orientable submanifolds by $l_1$-norm minimization. In Xavier Goaoc and Michael Kerber, editors, *38th International Symposium on Computational Geometry, SoCG 2022, June 7-10, 2022, Berlin, Germany*, volume 224 of LIPIcs, pages 8:1–8:16. Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2022. doi:10.4230/LIPIcs.SoCG.2022.8.

11 Dominique Attali, André Lieutier, and David Salinas. When convexity helps collapsing complexes. In *SoCG 2019-35th International Symposium on Computational Geometry*, page 15, 2019.

12 Ulrich Bauer and Herbert Edelsbrunner. The morse theory of čech and delaunay complexes. *Transactions of the American Mathematical Society*, 369(5):3741–3762, 2017.

13 Ulrich Bauer and Fabian Roll. Wrapping cycles in delaunay complexes: Bridging persistent homology and discrete morse theory. In Wolfgang Mulzer and Jeff M. Phillips, editors, *40th International Symposium on Computational Geometry (SoCG 2024)*, volume 293 of *Leibniz International Proceedings in Informatics (LIPIcs)*, pages 15:1–15:16, Dagstuhl, Germany, 2024. Schloss Dagstuhl – Leibniz-Zentrum für Informatik.

14 Fausto Bernardini, Joshua Mittleman, Holly Rushmeier, Cláudio Silva, and Gabriel Taubin. The ball-pivoting algorithm for surface reconstruction. *IEEE transactions on visualization and computer graphics*, 5(4):349–359, 1999.

15 Jean-Daniel Boissonnat, Frédéric Chazal, and Mariette Yvinec. *Geometric and topological inference*, volume 57. Cambridge University Press, 2018.

16 Jean-Daniel Boissonnat, Ramsay Dyer, Arijit Ghosh, and Steve Oudot. Equating the witness and restricted Delaunay complexes. Research Report CGL-TR-24, CGL, November 2011. URL: https://inria.hal.science/hal-00772486.
17 Jean-Daniel Boissonnat, André Lieutier, and Mathijs Wintraecken. The reach, metric distortion, geodesic convexity and the variation of tangent spaces. *Journal of applied and computational topology*, 3:29–58, 2019.

18 Jonathan C Carr, Richard K Beatson, Jon B Cherrie, Tim J Mitchell, W Richard Fright, Bruce C McCallum, and Tim R Evans. Reconstruction and representation of 3d objects with radial basis functions. In *Proceedings of the 28th annual conference on Computer graphics and interactive techniques (SIGGRAPH 2001)*, pages 67–76, 2001.

19 F. Chazal, D. Cohen-Steiner, and A. Lieutier. A sampling theory for compact sets in Euclidean space. *Discrete and Computational Geometry*, 41(3):461–479, 2009.

20 F. Chazal and A. Lieutier. Smooth Manifold Reconstruction from Noisy and Non Uniform Approximation with Guarantees. *Computational Geometry: Theory and Applications*, 40:156–170, 2008.

21 Aaron Chen, Florian Frick, and Anne Shiu. Neural codes, decidability, and a new local obstruction to convexity. *SIAM Journal on Applied Algebra and Geometry*, 3(1):44–66, 2019.

22 Siu-Wing Cheng, Tamal K Dey, and Edgar A Ramos. Manifold reconstruction from point samples. In *SODA*, volume 5, pages 1018–1027, 2005.

23 Siu-Wing Cheng, Tamal Krishna Dey, Jonathan Shewchuk, and Sartaj Sahni. *Delaunay mesh generation*. CRC Press Boca Raton, 2013.

24 Tamal K Dey. *Curve and surface reconstruction: algorithms with mathematical analysis*, volume 23. Cambridge University Press, 2006.

25 Tamal K Dey. *Curve and surface reconstruction*. In *Handbook of Discrete and Computational Geometry*, pages 915–936. Chapman and Hall/CRC, 2017.

26 Tamal K Dey, Joachim Giesen, Edgar A Ramos, and Bardia Sadri. Critical Points of the Distance to an $\varepsilon$-Sampling of a Surface and Flow-Ccomplex-Based Surface Reconstruction. *International Journal of Computational Geometry & Applications*, 18, 2008.

27 M. P. do Carmo. *Differential Geometry of Curves and Surfaces*. Prentice Hall, Upper Saddle River, New Jersey, 1976.

28 Herbert Edelsbrunner. *Geometry and topology for mesh generation*. Cambridge University Press, 2001.

29 Herbert Edelsbrunner. Surface reconstruction by wrapping finite sets in space. *Discrete and computational geometry: the Goodman-Pollack Festschrift*, pages 379–404, 2003.

30 Herbert Edelsbrunner. Alpha shapes-a survey. In *Tessellations in the Sciences: Virtues, Techniques and Applications of Geometric Tilings*. 2011.

31 Herbert Edelsbrunner and John L. Harer. *Computational topology*. American Mathematical Society, Providence, RI, 2010. An introduction. doi:10.1090/mbk/069.

32 Herbert Edelsbrunner, David G. Kirkpatrick, and Raimund Seidel. On the shape of a set of points in the plane. *IEEE Trans. Inf. Theory*, 29(4):551–558, 1983. doi:10.1109/TIT.1983.1056714.

33 Herbert Edelsbrunner and Ernst P Mücke. Three-dimensional alpha shapes. *ACM Transactions On Graphics (TOG)*, 13(1):43–72, 1994.

34 Herbert Edelsbrunner and Nimish R Shah. Triangulating topological spaces. *International Journal of Computational Geometry & Applications*, 7(04):365–378, 1997.

35 Herbert Federer. Curvature measures. *Transactions of the American Mathematical Society*, 93(3):418–491, 1959.

36 Steven Fortune. Voronoi diagrams and delaunay triangulations. In Jacob E. Goodman and Joseph O'Rourke, editors, *Handbook of Discrete and Computational Geometry, Second Edition*, pages 513–528. Chapman and Hall/CRC, 2004. doi:10.1201/9781420035315.ch23.

37 Joachim Giesen and Matthias John. Surface reconstruction based on a dynamical system. In *Computer graphics forum*, volume 21, pages 363–371. Wiley Online Library, 2002.

38 Joachim Giesen and Matthias John. The flow complex: a data structure for geometric modeling. In *SODA*, volume 3, pages 285–294, 2003.
39 Simon Giraudot, David Cohen-Steiner, and Pierre Alliez. Noise-adaptive shape reconstruction from raw point sets. In *Computer Graphics Forum*, volume 32, pages 229–238. Wiley Online Library, 2013.

40 Hugues Hoppe, Tony DeRose, Tom Duchamp, John McDonald, and Werner Stuetzle. Surface reconstruction from unorganized points. In *Proceedings of the 19th annual conference on computer graphics and interactive techniques (SIGGRAPH)*, pages 71–78, 1992.

41 Michael Kazhdan, Matthew Bolitho, and Hugues Hoppe. Poisson surface reconstruction. In *Proceedings of the fourth Eurographics symposium on Geometry processing*, volume 7, 2006.

42 Alexander Lytchak. Almost convex subsets. *Geometriae Dedicata*, 115(1):201–218, 2005.

43 J.R. Munkres. *Elements of algebraic topology*. Perseus Books, 1993.

44 P. Niyogi, S. Smale, and S. Weinberger. Finding the Homology of Submanifolds with High Confidence from Random Samples. *Discrete Computational Geometry*, 39(1-3):419–441, 2008.

45 Hans Samelson. Orientability of hypersurfaces in $r^n$. *Proceedings of the American Mathematical Society*, 22(1):301–302, 1969.

46 Sebastian Scholtes. On hypersurfaces of positive reach, alternating Steiner formulae and Hadwiger's problem. *arXiv preprint arXiv:1304.4179*, April 2013.
APPENDIX CONTENTS

<table><tbody><tr><td><b>A</b></td><td><b>Angle between flats</b></td><td><b>22</b></td></tr><tr><td></td><td>A.1 Definitions and basic properties</td><td>22</td></tr><tr><td></td><td>A.2 Angle between a triangle and a tangent space to the manifold</td><td>23</td></tr><tr><td></td><td>A.3 Difference between angular deviations at vertices</td><td>25</td></tr><tr><td><b>B</b></td><td><b>Missing proofs of Section 3</b></td><td><b>26</b></td></tr><tr><td></td><td>B.1 Upper and lower skins</td><td>26</td></tr><tr><td></td><td>B.2 Upper and lower facets of a d-simplex</td><td>30</td></tr><tr><td><b>C</b></td><td><b>Missing proofs of Section 4</b></td><td><b>31</b></td></tr><tr><td></td><td>C.1 Correctness</td><td>31</td></tr><tr><td></td><td>C.2 Practical version</td><td>34</td></tr><tr><td><b>D</b></td><td><b>Additional material for Section 5</b></td><td><b>36</b></td></tr><tr><td></td><td>D.1 Definition of I(ε, δ)</td><td>36</td></tr><tr><td></td><td>D.2 Possible β for Theorem 18</td><td>36</td></tr><tr><td><b>E</b></td><td><b>Proof of Theorem 18 in Section 5</b></td><td><b>37</b></td></tr><tr><td></td><td>E.1 Injective projection</td><td>38</td></tr><tr><td></td><td>E.2 Vertical convexity</td><td>38</td></tr><tr><td></td><td>E.3 Acyclicity</td><td>44</td></tr><tr><td><b>F</b></td><td><b>Sampling conditions for surfaces in R<sup>3</sup></b></td><td><b>47</b></td></tr><tr><td><b>G</b></td><td><b>The restricted Delaunay complex</b></td><td><b>49</b></td></tr><tr><td></td><td>G.1 The core Delaunay complex</td><td>49</td></tr><tr><td></td><td>G.2 A pure 2-dimensional simplicial complex when d = 3</td><td>51</td></tr></tbody></table>
### A Angle between flats

#### A.1 Definitions and basic properties

Consider two affine spaces $X, Y \subseteq \mathbb{R}^d$. Let $U$ and $V$ be the vector spaces associated to $X$ and $Y$, respectively. We recall that the angle between two affine spaces $X$ and $Y$ is the same as the angle between the two vector spaces $U$ and $V$ and is defined as

$$ \angle(X, Y) = \angle(U, V) = \max_{u \in U} \min_{v \in V} \angle(u, v). \\ \|u\| = 1 \qquad \|v\| = 1 $$

The definition is not symmetric in $X$ and $Y$, unless the two affine spaces $X$ and $Y$ (or equivalently, the two vector spaces $U$ and $V$) have same dimension. Given a vector space $V$, denote by $V^\perp$ its orthogonal complement. The following properties will be useful:

* **Property A1.** Let $U$ and $V$ be two vector spaces. Then,

$$ \angle(U, V) = \angle(V^\perp, U^\perp). $$

* **Property A2.** Let $U$ and $V$ be two vector spaces, with $\dim U = 1$. Then,

$$ \angle(U, V) + \angle(U, V^\perp) = \frac{\pi}{2}. $$

The angle between two vector spaces can also be written in terms of all hyperplanes that contain the second vector space:

* **Lemma A3.** Let $U, V$ be two vector spaces and $u \in U$. Then,

$$ \min_{\substack{v \in V \\ \|v\|=1}} \angle(u, v) = \max_{\substack{H \supset V \\ \mathrm{codim}(H)=1 \quad \|h\|=1}} \min_{h \in H} \angle(u, h) \qquad (9) $$

and

$$ \angle(U, V) = \max_{\substack{H \supset V \\ \mathrm{codim}(H)=1}} \angle(U, H), \qquad (10) $$

where $H$ designates a vector space and $\mathrm{codim}(H) = \dim(H^\perp)$.

**Proof.** For any codimension one vector space $H \supset V$, it holds that

$$ \min_{\substack{v \in V \\ \|v\|=1}} \angle(u, v) \ge \min_{\substack{h \in H \\ \|h\|=1}} \angle(u, h). $$

Thus, we have one direction of (9):

$$ \min_{\substack{v \in V \\ \|v\|=1}} \angle(u, v) \ge \max_{\substack{H \supset V \\ \mathrm{codim}(H)=1}} \min_{h \in H} \angle(u, h). $$

Note that if $u \in V$, (9) is trivially satisfied as both sides are 0. Hence, for the other direction of (9), we consider $u \notin V$. Denote the vector in $V$ closest to $u$ by $\pi_V(u) = \arg \min_{v \in V} (v-u)^2$. From the definition of the angle, it holds that

$$ \min_{\substack{v \in V \\ \|v\|=1}} \angle(u, v) = \angle(u, \pi_V(u)) = \arcsin \frac{\|\pi_V(u) - u\|}{\|u\|}. $$
Next, define

$$w = u - \pi_V(u) \in V^{\perp}$$

and let $W$ be the vector space spanned by $w$. Since $\omega \in V^{\perp}$, one has $V \subseteq W^{\perp}$. Moreover, $\pi_{W^{\perp}}(u) = \pi_V(u)$ because $u - \pi_V(u) = \omega \in W$. Hence,

$$ \begin{aligned} \min_{\substack{v \in V \\ \|v\|=1}} \angle(u, v) &= \angle(u, \pi_V(u)) = \angle(u, \pi_{W^{\perp}}(u)) = \min_{\substack{h \in W^{\perp} \\ \|h\|=1}} \angle(u, h) \\ &\le \max_{\substack{H \supseteq V \\ \mathrm{codim}(H)=1}} \min_{\substack{h \in H \\ \|h\|=1}} \angle(u, h). \end{aligned} $$

Finally, (10) holds because

$$ \begin{aligned} \angle(U, V) &= \max_{\substack{u \in U \\ \|u\|=1}} \min_{\substack{v \in V \\ \|v\|=1}} \angle(u, v) \\ &= \max_{\substack{u \in U \\ \|u\|=1}} \max_{\substack{H \supseteq V \\ \mathrm{codim}(H)=1}} \min_{\substack{h \in H \\ \|h\|=1}} \angle(u, h) \\ &= \max_{\substack{H \supseteq V \\ \mathrm{codim}(H)=1}} \max_{\substack{u \in U \\ \|u\|=1}} \min_{\substack{h \in H \\ \|h\|=1}} \angle(u, h) \\ &= \max_{\substack{H \supseteq V \\ \mathrm{codim}(H)=1}} \angle(U, H). \end{aligned} $$

## A.2 Angle between a triangle and a tangent space to the manifold

In this section, we establish a generalized version of Lemmas 24 and 25, using the local feature size instead of the reach and relaxing the requirement that $\mathcal{M}$ has codimension one. We assume $\mathcal{M}$ is a compact submanifold of $\mathbb{R}^d$ with positive reach, from which it follows that $\mathcal{M}$ is $C^{1,1}$ [42, Proposition 1.4]. Recall from [3] that the local feature size at a point $x$ on $\mathcal{M}$ is $\text{lfs}(x) = d(x, \text{axis}(\mathcal{M}))$ and that $\text{Reach}(\mathcal{M}) \le \text{lfs}(x)$ for all $x \in \mathcal{M}$.

**Lemma A4.** Let $\mathcal{M}$ be a compact submanifold of $\mathbb{R}^d$ with positive reach. If $ab$ is a non-degenerate edge with $a, b \in \mathcal{M}$, then

$$ \sin \angle \text{Aff}(ab), \mathbf{T}_a \mathcal{M} \le \frac{\|b-a\|}{2 \text{lfs}(a)}. $$

**Proof.** Point $b$ lies on or outside the set of spheres of radius $\text{lfs}(a)$ that are tangent to $\mathcal{M}$ at $a$. In the worst case, where $b$ lies on one of these spheres, $ab$ is a chord of that sphere. $\quad \blacksquare$

Let $\rho(\tau)$ designate the radius of the smallest $(d-1)$-sphere circumscribing a simplex $\tau$.

**Lemma A5.** Let $\mathcal{M}$ be a compact submanifold of $\mathbb{R}^d$ with positive reach. If $abc$ is a non-degenerate triangle with longest edge $bc$, for $a, b, c \in \mathcal{M}$, then

$$ \sin \angle \text{Aff}(abc), \mathbf{T}_a \mathcal{M} \le \frac{\rho(abc)}{\text{lfs}(a)} \quad \text{if } abc \text{ is an obtuse triangle and} $$

$$ \sin \angle \text{Aff}(abc), \mathbf{T}_a \mathcal{M} \le \frac{\sqrt{3} \rho(abc)}{\text{lfs}(a)} \quad \text{if } abc \text{ is an acute triangle.} $$

If $abc$ is obtuse, the bound is tight and happens when $\mathcal{M}$ is a $k$-sphere of radius $R$ with $2 \le k \le d-1$.
**Proof.** Let $A = \angle cab, \vec{u} = \frac{b-a}{\|b-a\|}$, and $\vec{v} = \frac{c-a}{\|c-a\|}$. Let $H$ be any hyperplane that contains $T_a M$ and let $\vec{n}$ be a unit vector orthogonal to $H$. By construction, $\vec{n}$ is orthogonal to $M$ at $a$. Introduce the two angles

$$ \theta_u = \arccos(\vec{u} \cdot \vec{n}), $$

$$ \theta_v = \arccos(\vec{v} \cdot \vec{n}). $$

Thanks to Lemma A4, we have that

$$ |\cos \theta_u| = |\vec{u} \cdot \vec{n}| = \sin \angle \operatorname{Aff}(ab), H \le \frac{\|b-a\|}{2 \operatorname{lhs}(a)}, \qquad (11) $$

$$ |\cos \theta_v| = |\vec{v} \cdot \vec{n}| = \sin \angle \operatorname{Aff}(ac), H \le \frac{\|c-a\|}{2 \operatorname{lhs}(a)}. \qquad (12) $$

Consider the vector

$$ \vec{w} = \frac{\vec{v} - (\vec{u} \cdot \vec{v}) \vec{u}}{\|\vec{v} - (\vec{u} \cdot \vec{v}) \vec{u}\|} = \frac{1}{\sin A} (\vec{v} - \cos A \vec{u}). $$

By construction, $\vec{w}$ is a unit vector parallel to the affine plane spanned by triangle $abc$ and orthogonal to $\vec{v}$. It follows that $(\vec{u}, \vec{w})$ is an orthonormal basis of the vector plane supporting the triangle $abc$ and we can write

$$ \begin{aligned} \sin \angle \operatorname{Aff}(abc), H &= \max_{t \in [0, 2\pi]} (\cos t \vec{u} + \sin t \vec{w}) \cdot \vec{n} \\ &= \max_{t \in [0, 2\pi]} (\vec{u} \cdot \vec{n}) \cos t + (\vec{w} \cdot \vec{n}) \sin t. \end{aligned} $$

The maximum over $[0, 2\pi]$ of the map $t \mapsto x \cos t + y \sin t$ is $\sqrt{x^2 + y^2}$. Thus,

$$ \begin{aligned} (\sin \angle \operatorname{Aff}(abc), H)^2 &= (\vec{u} \cdot \vec{n})^2 + (\vec{w} \cdot \vec{n})^2 \\ &= \cos^2 \theta_u + \frac{1}{\sin^2 A} (\cos \theta_v - \cos A \cos \theta_u)^2 \\ &= \frac{1}{\sin^2 A} (\cos^2 \theta_u + \cos^2 \theta_v - 2 \cos A \cos \theta_u \cos \theta_v). \end{aligned} $$

For fixed $A$, the last expression is a homogeneous degree 2 polynomial in $\cos \theta_u$ and $\cos \theta_v$. Under the constraints (11) and (12), its maximum is reached at one of the four corners of the constraint rectangle, i.e. when $\cos \theta_u = \pm \frac{\|b-a\|}{2 \operatorname{lhs}(a)}$ and $\cos \theta_v = \pm \frac{\|c-a\|}{2 \operatorname{lhs}(a)}$. We distinguish two cases, depending on whether the triangle $abc$ is obtuse or acute.

If $abc$ is acute, then $A \le \frac{\pi}{2}$ and $\cos A \ge 0$. It follows that the maximum of the polynomial is reached either when $\cos \theta_u = \frac{\|b-a\|}{2 \operatorname{lhs}(a)}$ and $\cos \theta_v = -\frac{\|c-a\|}{2 \operatorname{lhs}(a)}$ or when $\cos \theta_u = -\frac{\|b-a\|}{2 \operatorname{lhs}(a)}$ and $\cos \theta_v = \frac{\|c-a\|}{2 \operatorname{lhs}(a)}$. Letting $b' = 2a - b$ be the symmetric point of $b$ with respect to $a$, we obtain

$$ \begin{aligned} (\sin \angle \operatorname{Aff}(abc), H)^2 &\le \frac{1}{4 \operatorname{lhs}(a)^2} \frac{1}{\sin^2 A} (\|b-a\|^2 + \|c-a\|^2 + 2 \cos A \|b-a\| \|c-a\|) \\ &= \frac{1}{4 \operatorname{lhs}(a)^2} \frac{1}{\sin^2 A} \|b' - c\|^2 \\ &= \frac{\rho(ab'c)^2}{\operatorname{lhs}(a)^2}. \end{aligned} $$

Since the last equation holds for any hyperplane $H$ that contains $T_a M$, it follows from (10) in Lemma A3 that

$$ (\sin \angle \operatorname{Aff}(abc), T_a M)^2 \le \frac{\rho(ab'c)^2}{\operatorname{lhs}(a)^2}. $$
Under the constraint that the longest edge in the triangle abc is bc, the ratio $\frac{\rho(ab'c)}{\rho(abc)}$ is maximized when abc is an equilateral triangle, in which case the ratio is equal to $\sqrt{3}$. The bound for acute triangles follows.

If abc is obtuse, then $A \ge \frac{\pi}{2}$ since bc is the longest edge. Therefore, $\cos A \le 0$ and the maximum of the polynomial is reached either when $\cos \theta_u = \frac{\|b-a\|}{2\text{lfs}(a)}$ and $\cos \theta_v = \frac{\|c-a\|}{2\text{lfs}(a)}$ or when $\cos \theta_u = -\frac{\|b-a\|}{2\text{lfs}(a)}$ and $\cos \theta_v = -\frac{\|c-a\|}{2\text{lfs}(a)}$. We obtain that

$$ (\sin \angle \mathrm{Aff}(abc), H)^2 \le \frac{1}{4\mathrm{lfs}(a)^2} \frac{1}{\sin^2 A} (\|b-a\|^2 + \|c-a\|^2 - 2 \cos A \|b-a\| \|c-a\|) \\ = \frac{1}{4\mathrm{lfs}(a)^2} \frac{1}{\sin^2 A} \|b-c\|^2 \\ = \frac{\rho(abc)^2}{\mathrm{lfs}(a)^2}, $$

where we used the formula $\rho(abc) = \frac{\|b-c\|}{2\sin A}$ to obtain the last equality. As for the acute case, we get that:

$$ (\sin \angle \mathrm{Aff}(abc), \mathbf{T}_a \mathcal{M})^2 \le \frac{\rho(abc)^2}{\mathrm{lfs}(a)^2}, $$

To see that the bound is tight in the obtuse case, consider a k-sphere of radius $R$ and center $o$ with $2 \le k \le d-1$ as $\mathcal{M}$. Let $o'$ be the center of the smallest 2-sphere circumscribing abc. Then, the angle $\theta$ between the lines oa (or ob or oc) and oo' is

$$ \theta = \angle \mathrm{Aff}(abc), \mathbf{T}_a \mathcal{M} = \angle \mathrm{Aff}(abc), \mathbf{T}_b \mathcal{M} = \angle \mathrm{Aff}(abc), \mathbf{T}_c \mathcal{M} $$

and $\sin \theta$ is precisely the bound $\frac{\rho(abc)}{R} = \frac{\rho(abc)}{\mathrm{lfs}(a)}$.

### A.3 Difference between angular deviations at vertices

Consider a simplex $\tau$ with vertices on $\mathcal{M}$. In this section, we bound the variation of the angle $\angle(\mathrm{Aff}(\tau), \mathbf{T}_a \mathcal{M})$ as $a$ varies over the vertices of $\tau$. Recall that $\rho(\tau)$ denotes the radius of the smallest $(d-1)$-sphere circumscribing the simplex $\tau$.

**Lemma A6.** Let $0 < i < d$. For any $i$-simplex $\tau$ whose vertices lie on $\mathcal{M}$ with $\rho(\tau) < R$,

$$ \max_{a \in \tau} \angle(\mathrm{Aff}(\tau), \mathbf{T}_a \mathcal{M}) - \min_{a \in \tau} \angle(\mathrm{Aff}(\tau), \mathbf{T}_a \mathcal{M}) \le 2 \arcsin \left( \frac{\rho(\tau)}{R} \right). \quad (13) $$

**Proof.** By [17, Corollary 3], for all $m, m' \in \mathcal{M}$, we have $\angle(\mathbf{T}_m \mathcal{M}, \mathbf{T}_{m'} \mathcal{M}) \le 2 \arcsin \left( \frac{\|m'-m\|}{2R} \right)$. Consider two vertices $a, b \in \tau$. Since $\|a-b\| \le 2\rho(\tau)$, it holds that

$$ \angle(\mathbf{T}_b \mathcal{M}, \mathbf{T}_a \mathcal{M}) \le 2 \arcsin \left( \frac{\rho(\tau)}{R} \right). $$

The result follows by combining the above inequality and the triangular inequality:

$$ \angle(\mathrm{Aff}(\tau), \mathbf{T}_b \mathcal{M}) - \angle(\mathrm{Aff}(\tau), \mathbf{T}_a \mathcal{M}) \le \angle(\mathbf{T}_b \mathcal{M}, \mathbf{T}_a \mathcal{M}) \le 2 \arcsin \left( \frac{\rho(\tau)}{R} \right). \quad \blacksquare $$
## B Missing proofs of Section 3

In this section, we write $K$ instead of $|K|$ inside notations, so that $\text{UpperSkin}_M(|K|) = \text{UpperSkin}_M(K)$, $\text{LowerSkin}_M(|K|) = \text{LowerSkin}_M(K)$, $\text{up}_{|K|}(m) = \text{up}_K(m)$, and $\text{low}_{|K|}(m) = \text{low}_K(m)$.

### B.1 Upper and lower skins

**Lemma 5.** Suppose that $K$ is vertically convex and has a non-vertical skeleton relative to $M$. Then, the upper and lower skins of $|K|$ are closed sets, each homeomorphic to $\pi_M(|K|)$. The homeomorphism is realized in both cases by $\pi_M$. In addition,

$$ \partial|K| = \text{UpperSkin}_M(|K|) \cup \text{LowerSkin}_M(|K|). \qquad (2) $$

**Proof.** It suffices to show that $\text{UpperSkin}_M(K)$ is a closed set and that the mapping $\pi_M: \text{UpperSkin}_M(K) \to \pi_M(|K|)$ is a homeomorphism. This result will automatically extend to $\text{LowerSkin}_M(K)$ because the lower skin of $K$ becomes the upper skin of $K$ when the orientation of $K$ is reversed.

We begin by proving that $\text{UpperSkin}_M(K)$ is a closed set. To do this, we define a set $A$, which is closed by construction, and show that $A = \text{UpperSkin}_M(K)$. Let the set of points lying above $K$ in the offset region $M^{\oplus r}$ be

$$ \text{Above}(K) = \bigcup_{m \in \pi_M(|K|)} [\text{up}_K(m), m + r\mathbf{n}(m)] $$

and set

$$ A = \text{closure}(\text{Above}(K)) \cap |K|. $$

$A$ is the intersection of two closed sets and hence it is closed. Recalling that

$$ |K| = \bigcup_{m \in \pi_M(|K|)} [\text{low}_K(m), \text{up}_K(m)], $$

we observe that the sets $\text{Above}(K)$ and $|K|$ intersect at a single point, $\text{up}_K(m)$, along each normal segment $[m - r\mathbf{n}(m), m + r\mathbf{n}(m)]$. Thus, by construction, $\text{UpperSkin}_M(K) = \text{Above}(K) \cap |K|$ and hence $\text{UpperSkin}_M(K) \subseteq A$.

To prove the reverse inclusion, we first show that each normal segment $N_m M \cap B(m, r)$ intersects $A$ at exactly one point. We proceed in three stages.

**Stage one.** We establish the following implication:

$$ x \in \text{closure}(\text{Above}(K)) \implies [x, m + r\mathbf{n}(m)] \subseteq \text{closure}(\text{Above}(K)). $$

Consider a point $x \in \text{closure}(\text{Above}(K))$, implying the existence of a sequence of points $(x_i)_{i \in \mathbb{N}}$ in $\text{Above}(K)$ that converges to $x$ as $i \to +\infty$. Let $m = \pi_M(x)$ and $m_i = \pi_M(x_i)$, and consider the sequence of segments $([x_i, m_i + r\mathbf{n}(m_i)])_{i \in \mathbb{N}}$ (see Figure 11 for a depiction). Each segment $[x_i, m_i + r\mathbf{n}(m_i)]$ in the sequence belongs to $\text{Above}(K)$ since, given $x_i \in \text{Above}(K)$, it holds that

$$ [x_i, m_i + r\mathbf{n}(m_i)] \subseteq [\text{up}_K(m_i), m_i + r\mathbf{n}(m_i)] \subseteq \text{Above}(K). $$

Furthermore, we show that the sequence of segments $([x_i, m_i + r\mathbf{n}(m_i)])_{i \in \mathbb{N}}$ converges in Hausdorff distance to $[x, m + r\mathbf{n}(m)]$, completing the proof. It is enough to show the
<figure><img src="image_18.png" /><figcaption>Figure 11 Schematics of the construction in Stage one.</figcaption></figure>

convergence of the endpoints of segments and since $\lim_{i \to +\infty} x_i = x$, we only need to show that $\lim_{i \to +\infty} (m_i + r\mathbf{n}(m_i)) = m + r\mathbf{n}(m)$. Let $f: \text{Above}(K) \to \text{Above}(K)$ be defined by $f(z) = \pi_M(z) + r\mathbf{n}(\pi_M(z))$. Both $\pi_M: \text{Above}(K) \to \mathcal{M}$ and $\mathbf{n}: \mathcal{M} \to \mathbf{n}(m)$ are continuous maps, hence $f$ is continuous and $\lim_{i \to +\infty} f(x_i) = f(x)$. Thus, $\lim_{i \to +\infty} (m_i + r\mathbf{n}(m_i)) = m + r\mathbf{n}(m)$.

**Stage two.** We show that for all $m \in \pi_M(|K|)$, the set $A \cap \mathbf{N}_m\mathcal{M} \cap B(m, r)$ is connected. Consider two points $x, y \in A \cap \mathbf{N}_m\mathcal{M} \cap B(m, r)$. Since $x, y \in |K| \cap \mathbf{N}_m\mathcal{M} \cap B(m, r)$, the vertical convexity assumption guarantees that $[x, y] \in |K| \cap \mathbf{N}_m\mathcal{M} \cap B(m, r)$. Since $x, y \in \text{closure}(\text{Above}(K)) \cap \mathbf{N}_m\mathcal{M} \cap B(m, r)$, the previous stage guarantees that $[x, y] \in \text{closure}(\text{Above}(K)) \cap \mathbf{N}_m\mathcal{M} \cap B(m, r)$. Therefore, $[x, y]$ belongs to $A \cap \mathbf{N}_m\mathcal{M} \cap B(m, r)$.

**Stage three.** We show that $A \cap \mathbf{N}_m\mathcal{M} \cap B(m, r)$ is reduced to a single point for all $m \in \pi_M(|K|)$. In the previous stage, we established that $A \cap \mathbf{N}_m\mathcal{M} \cap B(m, r)$ is connected, thus forming a segment. Assume, for a contradiction, that the endpoints $x$ and $y$ of this segment are distinct. For each $z \in [x, y]$, let $\sigma_z$ denote the unique simplex of $K$ containing $z$ in its relative interior. Since $A \subseteq \partial|K| = |\partial K|$, $\sigma_z$ belongs to the boundary complex $\partial K$ of $K$ and has $\dim \sigma_z < d$ for all $z \in [x, y]$. Given that $x \neq y$, there exists $z \in [x, y]$ with $\dim \sigma_z > 0$. Since $\sigma_z$ is a boundary simplex of $K$ containing $[x, y]$ locally around $z$, it must be vertical with $0 < \dim \sigma_z < d$, contradicting our assumption that $K$ contains no vertical $i$-simplices for $0 < i < d$.

From stage three, $A$ intersects $[m - r\mathbf{n}(m), m + r\mathbf{n}(m)]$ at a single point for all $m \in \pi_M(|K|)$. By construction, so does $\text{UpperSkin}_M(K)$. Since $\text{UpperSkin}_M(K) \subseteq A$, it follows that $\text{UpperSkin}_M(K) = A$ along the normal segment $[m - r\mathbf{n}(m), m + r\mathbf{n}(m)]$ for all $m \in \pi_M(|K|)$. Hence, the upper skin of $K$ coincides with $A$ and is therefore closed.

We are now ready to conclude. The upper skin of $K$ is a closed set and, therefore, compact. The map $\pi_M: \text{UpperSkin}_M(K) \to \pi_M(|K|)$ is a continuous bijection from one compact set to another, and is thus a homeomorphism. Let us prove Equation (2), that is,

$$ \partial|K| = \text{UpperSkin}_M(K) \cup \text{LowerSkin}_M(K). $$

By definition, the boundary of $|K|$ is the set $\partial|K| = |K| \cap \text{closure}(\mathbb{R}^d \setminus |K|)$.
Introducing the following sets (see Figure 12)

$$ \text{Below}(K) = \bigcup_{m \in \pi_M(|K|)} [m - r\mathbf{n}(m), \text{low}_K(m)] \text{ and} $$

$$ \text{Side}(K) = \{x \in \mathcal{M}^{\oplus r} | \pi_{\mathcal{M}}(x) \notin \pi_{\mathcal{M}}(|K|)\}, $$

we can write

$$ \mathbb{R}^d \setminus |K| = \text{Above}(K) \cup \text{Below}(K) \cup (\mathbb{R}^d \setminus \mathcal{M}^{\oplus r}) \cup \text{Side}(K). $$

<figure><img src="image_19.png" /><figcaption>Figure 12 The different regions in $\mathcal{M}^{\oplus r}$.</figcaption></figure>

Taking the closure on both sides, it follows that

$$ \text{closure}(\mathbb{R}^d \setminus |K|) = \text{closure}(\text{Above}(K)) \cup \text{closure}(\text{Below}(K)) \cup \text{closure}(\mathbb{R}^d \setminus \mathcal{M}^{\oplus r}) \cup \text{closure}(\text{Side}(K)). $$

Intersecting both sides of the equality with $|K|$ and noting that the third term in the union has an empty intersection with $|K|$, we obtain that

$$ \begin{aligned} \partial|K| &= |K| \cap \text{closure}(\mathbb{R}^d \setminus |K|) \\ &= |K| \cap (\text{closure}(\text{Above}(K)) \cup \text{closure}(\text{Below}(K)) \cup \text{closure}(\text{Side}(K))) \\ &= (|K| \cap \text{closure}(\text{Above}(K))) \cup (|K| \cap \text{closure}(\text{Below}(K))) \\ &= \text{UpperSkin}_M(K) \cup \text{LowerSkin}_M(K), \end{aligned} $$

which concludes the proof.

**Lemma 6.** Let $K$ be vertically convex and with non-vertical skeleton relative to $\mathcal{M}$. If $\text{UpperSkin}_M(|K|) = \text{LowerSkin}_M(|K|)$, then $K = \partial K$.

**Proof.** Since $\text{UpperSkin}_M(|K|) = \text{LowerSkin}_M(|K|)$, it follows that $\text{low}_{|K|}(m) = \text{up}_{|K|}(m)$ for all $m \in \pi_M(|K|)$ and $|K| \subseteq \text{UpperSkin}_M(|K|) = \text{LowerSkin}_M(|K|)$. By Lemma 5,

$$ |K| \subseteq \text{UpperSkin}_M(|K|) \cup \text{LowerSkin}_M(|K|) = \partial|K| = |\partial K|. $$

Thus, $|K| \subseteq |\partial K|$ and therefore $K = \partial K$.
By Lemma 5, we already know that the union of the upper and lower skins is a simplicial complex. However, since their intersection is non-empty, it is unclear whether each one of them separately is a simplicial complex as well. Lemma 7 establishes exactly that, replacing each set in Equation (2) by a simplicial counterpart. Its proof relies on the next lemma.

**Lemma B1.** Suppose that $K$ has a non-vertical skeleton and is vertically convex relative to $M$. Then, for all simplices $\nu \in K$, the following two implications hold:

1. $\text{relint}(\text{conv}(\nu)) \cap \text{UpperSkin}_M(K) \neq \emptyset \Rightarrow \text{conv}(\nu) \subseteq \text{UpperSkin}_M(K)$;

2. $\text{relint}(\text{conv}(\nu)) \cap \text{LowerSkin}_M(K) \neq \emptyset \Rightarrow \text{conv}(\nu) \subseteq \text{LowerSkin}_M(K)$.

**Proof.** Let $\nu$ be a simplex of $K$ and $x \in \text{relint}(\text{conv}(\nu))$. Consider $t > 0$ such that the only simplices of $K$ whose convex hull intersects $B(x, t)$ are in the star of $\nu$. We define the geometric star of $x$ in $K$, also known as the tangent cone [35], as

$$ \tilde{\text{St}}_K(x) = \{ \lambda u \mid x + u \in |K| \cap B(x, t), \lambda \ge 0 \}. $$

Similarly, for any $\tau \in \text{St}(\nu, K)$, we introduce the cone

$$ \tilde{\text{St}}_{\tau}(x) = \{ \lambda u \mid x + u \in \text{relint}(\text{conv}(\tau)) \cap B(x, t), \lambda \ge 0 \}. $$

Since $K$ is embedded, the family $\{\tilde{\text{St}}_{\tau}(x) \mid \tau \in \text{St}(\nu, K)\}$ is a partition of $\tilde{\text{St}}_K(x)$. Note that $x \mapsto \tilde{\text{St}}_K(x)$ remains constant on $\text{relint}(\text{conv}(\nu))$ for each $\nu \in K$, thus depending only on the simplex of $K$ whose support contains $x$ in its relative interior. Additionally, we have:

$$ x \in \text{UpperSkin}_M(K) \iff \mathbf{n}(\pi_M(x)) \notin \tilde{\text{St}}_K(x). $$

We next establish that:

$$ \text{relint}(\text{conv}(\nu)) \cap \text{UpperSkin}_M(K) \neq \emptyset \Rightarrow \text{relint}(\text{conv}(\nu)) \subseteq \text{UpperSkin}_M(K). $$

If $\dim \nu = 0$, the result is clear. For $\dim \nu > 0$, assume for contradiction that $x_0, x_1 \in \text{relint}(\text{conv}(\nu))$ with $x_0 \in \text{UpperSkin}_M(K)$ but $x_1 \notin \text{UpperSkin}_M(K)$. The segment $[x_0, x_1]$ lies entirely within $\text{relint}(\text{conv}(\nu))$. Since $K$ is vertically convex relative to $M$, there exists $0 < r < \text{Reach}(M)$ such that $|K| \subseteq M^{\oplus r}$. Therefore, the projection map $\pi_M$ is well-defined and continuous on $|K|$, as is the map $x \mapsto \mathbf{n}(\pi_M(x))$. Consequently, at some point $x \in [x_0, x_1]$, we must have $\mathbf{n}(\pi_M(x)) \in \partial \tilde{\text{St}}_K(x_0)$, or equivalently:

$$ \mathbf{n}(\pi_M(x)) \in \partial \tilde{\text{St}}_K(x). $$

Observe that $\partial \tilde{\text{St}}_K(x)$ is contained in $\bigcup_{\tau} \tilde{\text{St}}_{\tau}(x)$, where $\tau \in \text{St}(\nu, K)$ has dimension at most $d-1$. Hence, $\mathbf{n}(\pi_M(x))$ belongs to $\tilde{\text{St}}_{\tau}(x)$ for some $\tau \in \text{St}(\nu, K)$ with $0 < \dim \tau < d$. This implies $\tau$ is vertical with $0 < \dim \tau < d$, contradicting the assumption that $K$ has a non-vertical skeleton. It follows that the relative interior of $\nu$ is contained in the upper skin. Moreover, the upper skin is closed, by Lemma 5. Hence,

$$ \text{relint}(\text{conv}(\nu)) \subseteq \text{UpperSkin}_M(K) \Rightarrow \text{conv}(\nu) \subseteq \text{UpperSkin}_M(K). $$

The first result, for the upper skin, follows. The proof for the lower skin is analogous. ◀

**Lemma 7.** Let $K$ be vertically convex with non-vertical skeleton relative to $M$. Then,

$$ |\text{UpperComplex}_M(K)| = \text{UpperSkin}_M(|K|), $$

$$ |\text{LowerComplex}_M(K)| = \text{LowerSkin}_M(|K|) \text{ and} $$

$$ \partial K = \text{UpperComplex}_M(K) \cup \text{LowerComplex}_M(K). $$

Moreover, if $\pi_M(|K|) = M$, both $\text{UpperComplex}_M(K)$ and $\text{LowerComplex}_M(K)$ are triangulations of $M$.
**Proof.** By construction, $|UpperComplex_M(K)| \subseteq UpperSkin_M(|K|)$. For the reverse inclusion, consider $x \in UpperSkin_M(|K|)$ and let $\nu \in K$ be the simplex whose support contains $x$ in its relative interior. By Lemma B1, $conv(\nu) \subseteq UpperSkin_M(|K|)$, showing that $\nu \in UpperComplex_M(K)$ and $x \in |UpperComplex_M(K)|$. We have just established the first equality. The second one is obtained similarly. For the third one, applying Lemma 5, we obtain that

$$ 
\begin{aligned}
|\partial K| &= UpperSkin_M(|K|) \cup LowerSkin_M(|K|) \\
&= |UpperComplex_M(K)| \cup |LowerComplex_M(K)| \\
&= |UpperComplex_M(K)| \cup |LowerComplex_M(K)|.
\end{aligned}
$$

Since $UpperComplex_M(K) \cup LowerComplex_M(K) \subseteq \partial K$, the third equality follows. Finally, by Lemma 5, when $\pi_M(|K|) = M$, both the upper complex and lower complex of $K$ are triangulations of $M$. ◀

## B.2 Upper and lower facets of a d-simplex

**Lemma 8.** Consider a non-degenerate d-simplex $\sigma \subseteq \mathbb{R}^d$ such that $conv(\sigma) \subseteq M^{\oplus r}$ for some $r < \text{Reach}(M)$. If $\sigma$ has no vertical facets relative to $M$, then $UpperFacets_M(\sigma)$ and $LowerFacets_M(\sigma)$ are non-empty sets that partition the facets of $\sigma$.

**Proof.** By Lemma 7 applied with $K = Cl\sigma$,

$$(Cl\sigma)^{[d-1]} = UpperFacets_M(\sigma) \cup LowerFacets_M(\sigma).$$

Let us show that $UpperFacets_M(\sigma) \cap LowerFacets_M(\sigma) = \emptyset$. Suppose for a contradiction that there is a facet $\nu$ of $\sigma$ such that $conv(\nu) \subseteq UpperSkin_M(K)$ and $conv(\nu) \subseteq LowerSkin_M(K)$. This would imply that $conv(\sigma) \subseteq Aff(\nu)$ and $\sigma$ would be degenerate which is impossible. Let us show that $UpperFacets_M(\sigma) \neq \emptyset$ by contradiction. If $UpperFacets_M(\sigma) = \emptyset$, then $LowerFacets_M(\sigma)$ would contain all the facets of $\sigma$, contradicting the fact that the two skins of $Cl\sigma$ relative to $M$ are homeomorphic by Lemma 5. Similarly, $LowerFacets_M(\sigma) \neq \emptyset$. ◀
# C Missing proofs of Section 4

## C.1 Correctness

**▶ Lemma 13 (Sinks and sources).** Consider $K$ such that $|K| \subseteq \mathcal{M}^{\oplus r}$ for some $r < \text{Reach}(\mathcal{M})$ and assume that $K$ satisfies the injective projection, covering projection and vertical convexity assumptions of Theorem 12. Consider a $d$-simplex $\sigma \in K$ and let $\tau = \bigcap \text{UpperFacets}_{\mathcal{M}}(\sigma)$ and $\tau' = \bigcap \text{LowerFacets}_{\mathcal{M}}(\sigma)$. Then,

- $\tau$ is a free simplex of $K$ from above relative to $\mathcal{M} \iff \sigma$ is a sink of $G_{\mathcal{M}}(K)$.

- $\tau'$ is a free simplex of $K$ from below relative to $\mathcal{M} \iff \sigma$ is a source of $G_{\mathcal{M}}(K)$.

**Proof.** Since the second item of the lemma can be obtained from the first one by reversing the orientation of $\mathcal{M}$, we only need to prove the first item. We start with the forward direction $\implies$. Suppose that $\tau \in K$ is a free simplex of $K$ from above relative to $\mathcal{M}$. This implies that

$$ \text{St}(\tau, K)^{[d-1]} = \text{UpperFacets}_{\mathcal{M}}(\sigma), $$

where $\Sigma^{[i]}$ stands for the set of $i$-simplices of $\Sigma$. Observe that $\text{St}(\tau, K) \setminus \{\sigma\} \subseteq \partial K$ and therefore $\text{UpperFacets}_{\mathcal{M}}(\sigma) \subseteq \partial K$. Hence, $\sigma$ has no $d$-simplex in $K$ above it. In other words, $\sigma$ is a sink of the dual graph $G_{\mathcal{M}}(K)$.

Let us prove the backward direction $\iff$. Suppose that $\sigma$ is a sink of $G_{\mathcal{M}}(K)$. Equivalently, $\sigma$ is a $d$-simplex of $K$ such that $\text{UpperFacets}_{\mathcal{M}}(\sigma) \subseteq \partial K$. By Lemma 8, $\text{UpperFacets}_{\mathcal{M}}(\sigma) \neq \emptyset$ and it follows that $\tau \neq \emptyset$ and $\tau \in \partial K$. Let us prove that $\tau$ is a free simplex of $K$. By definition, this boils down to proving that $\text{Lk}(\tau, K)$ is the closure of a simplex. We do this by showing that

$$ \text{Lk}(\tau, K) = \text{Lk}(\tau, \text{Cl}\,\sigma). \qquad (14) $$

We first claim that the above equation is implied by the following one

$$ \text{Lk}(\tau, \partial K) = \text{Lk}(\tau, \partial \text{Cl}\,\sigma). \qquad (15) $$

Indeed, suppose that we have (15). Since $\text{Cl}\,\sigma \subseteq K$, we get that $\text{Lk}(\tau, \text{Cl}\,\sigma) \subseteq \text{Lk}(\tau, K)$ and we only need to establish the reverse inclusion to get (14). For this, we use the fact that for any simplicial complex $X$ embedded in $\mathbb{R}^d$ and any $\tau \in X$, we have that $\partial \text{Lk}(\tau, X) = \text{Lk}(\tau, \partial X)$. We thus deduce from (15) that

$$ \partial \text{Lk}(\tau, K) = \partial \text{Lk}(\tau, \text{Cl}\,\sigma). $$

Because $\tau \in \partial K$, it follows that $|\text{Lk}(\tau, K)|$ is topologically equivalent to a proper subset of the $(d-k-1)$-sphere, where $k = \text{dim}\,\tau$. Because $\tau \in \partial \text{Cl}\,\sigma$, we have similarly that $|\text{Lk}(\tau, \text{Cl}\,\sigma)|$ is also topologically equivalent to a proper subset of the $(d-k-1)$-sphere. Since the latter link is a subset of the former link and the two links share the same boundary complex, the only possibility is that they are equal and we get (14). We have just established our claim that (15) $\implies$ (14). Hence, to prove that $\tau$ is a free simplex of $K$, it suffices to establish (15). Let

$$ \mathbf{A} = \text{Lk}(\tau, \partial K) $$

$$ \mathbf{B} = \text{Lk}(\tau, \text{UpperComplex}_{\mathcal{M}}(K)) $$

$$ \mathbf{C} = \text{Lk}(\tau, \text{UpperComplex}_{\mathcal{M}}(\text{Cl}\,\sigma)) $$

$$ \mathbf{D} = \text{Lk}(\tau, \partial \text{Cl}\,\sigma). $$
We prove (15) by showing that $A = B = C = D$ in three steps. Before we start, we write two useful equalities due to the fact $\partial \mathrm{Cl} \sigma$ is a pure simplicial ($d-1$)-complex:

$$ \mathrm{Cl}(\mathrm{UpperFacets}_{\mathcal{M}}(\sigma)) = \mathrm{UpperComplex}_{\mathcal{M}}(\mathrm{Cl}\sigma), \qquad (16) $$

$$ \mathrm{Cl}(\mathrm{LowerFacets}_{\mathcal{M}}(\sigma)) = \mathrm{LowerComplex}_{\mathcal{M}}(\mathrm{Cl}\sigma). \qquad (17) $$

We refer the reader to Figure 13 for a pictorial representation of the objects in the proof.

<figure><img src="image_20.png" /><figcaption>Figure 13 Notation for the proof of Lemma 13. The upper skin of $K$ is in green and its lower skin in pink. We have schematically represented $\sigma$ using curved edges. Its upper skin (in pale green) is a subset of the upper skin of $K$. The $k$-simplex $\tau$ is represented as a black dot. Its link in $\partial K$ is represented by the two white dots and is proved to triangulate the $(d-k-2)$-sphere.</figcaption></figure>

**Step 1:** $A = B$. By Lemma 8, $\mathrm{UpperFacets}_{\mathcal{M}}(\sigma)$ and $\mathrm{LowerFacets}_{\mathcal{M}}(\sigma)$ partition the facets of $\sigma$. Let us make a general observation. Suppose that $\Sigma$ and $\Sigma'$ partition the set of facets of $\sigma$. Let $\tau = \bigcap \Sigma$ and consider a point $x$ in the relative interior of $\mathrm{conv}(\Sigma)$. Since $\mathrm{Cl}\sigma$ is embedded, $x$ does not lie on $|\mathrm{Cl}(\Sigma')|$. Applying this with $\Sigma = \mathrm{UpperFacets}_{\mathcal{M}}(\sigma)$ and $\Sigma' = \mathrm{LowerFacets}_{\mathcal{M}}(\sigma)$, we get that for any point $x$ in the relative interior of $\mathrm{conv}(\sigma)$, we have that

$$ x \notin |\mathrm{Cl}(\mathrm{LowerFacets}_{\mathcal{M}}(\sigma))| = |\mathrm{LowerComplex}_{\mathcal{M}}(\mathrm{Cl}\sigma)| = \mathrm{LowerSkin}_{\mathcal{M}}(\mathrm{Cl}\sigma), $$

where the first equality comes from (17) and the second equality comes from Lemma 7. Let $m = \pi_{\mathcal{M}}(x)$. By construction, the normal segment $N_m \mathcal{M} \cap B(m, r)$ passes through $x$. It intersects $\mathrm{LowerSkin}_{\mathcal{M}}(\mathrm{Cl}\sigma)$ in a point $y$ and $\mathrm{LowerSkin}_{\mathcal{M}}(K)$ in a point $z$ in such a way that along direction $n(m)$, $x$ is strictly above $y$ and $z$ cannot be above $y$. This shows that $x \neq z$ and consequently $x \notin \mathrm{LowerSkin}_{\mathcal{M}}(K)$. Since $\mathrm{LowerSkin}_{\mathcal{M}}(K)$ is a closed set by Lemma 5, $x$ is at distance greater than some $\epsilon > 0$ of $\mathrm{LowerSkin}_{\mathcal{M}}(K)$. It follows that

$$ B(x, \epsilon) \cap |\partial K| = B(x, \epsilon) \cap |\mathrm{UpperComplex}_{\mathcal{M}}(K)|. $$

Since $K$ is canonically embedded, the star (and therefore the link) of $\tau$ in any subcomplex of $K$ depends only upon simplices whose support intersects some neighborhood of $x$. It follows that:

$$ \mathrm{Lk}(\tau, \partial K) = \mathrm{Lk}(\tau, \mathrm{UpperComplex}_{\mathcal{M}}(K)). $$
**Step 2: C = D.** Consider again two sets $\Sigma$ and $\Sigma'$ that partition the set of facets of $\sigma$. Setting $\tau = \bigcap \Sigma$, one can observe that $Lk(\tau, \mathrm{Cl}(\Sigma)) = Lk(\tau, \partial \mathrm{Cl} \sigma)$. Applying this with $\Sigma = \mathrm{UpperFacets}_M(\sigma)$ and $\Sigma' = \mathrm{LowerFacets}_M(\sigma)$ and using (16), we get that

$$Lk(\tau, \mathrm{UpperComplex}_M(\mathrm{Cl} \sigma)) = Lk(\tau, \partial \mathrm{Cl} \sigma).$$

We see in particular that $|Lk(\tau, \mathrm{UpperComplex}_M(\mathrm{Cl} \sigma))|$ is a topological $(d-k-2)$-sphere.

**Step 3: B = C.** Recall that $\mathrm{UpperFacets}_M(\sigma) \subseteq \partial K$. By Lemma 7, $\partial K$ is the union of the two subcomplexes $\mathrm{UpperComplex}_M(K)$ and $\mathrm{LowerComplex}_M(K)$ whose underlying spaces are the upper and lower skins of $K$ relative to $M$, respectively. Each upper facet of $\sigma$ is contained in one of those two skins but not both. The only possibility is thus that $\mathrm{UpperFacets}_M(\sigma) \subseteq \mathrm{UpperComplex}_M(K)$ and therefore using (16)

$$\mathrm{UpperComplex}_M(\mathrm{Cl} \sigma) \subseteq \mathrm{UpperComplex}_M(K).$$

Taking the link of $\tau$ in each of those two subcomplexes of $K$, we get that

$$Lk(\tau, \mathrm{UpperComplex}_M(\mathrm{Cl} \sigma)) \subseteq Lk(\tau, \mathrm{UpperComplex}_M(K)).$$

On the left side, we know from the previous step that the link is a triangulation of the $(d-k-2)$-sphere. We now study the link on the right side. By Lemma 5, $|\mathrm{UpperComplex}_M(K)|$ is homeomorphic to $M$. Since $M$ is a $(d-1)$-manifold without boundary, we deduce that so is $|\mathrm{UpperComplex}_M(K)|$. This implies that the link of any simplex in $\mathrm{UpperComplex}_M(K)$ is a triangulation of the $(d-k-2)$-sphere. In summary, writing $X \approx Y$ if $X$ is homeomorphic to $Y$ and $S^i$ for the $i$-sphere, we obtain that

$$S^{d-k-2} \approx |Lk(\tau, \mathrm{UpperComplex}_M(\mathrm{Cl} \sigma))| \subseteq |Lk(\tau, \mathrm{UpperComplex}_M(K))| \approx S^{d-k-2}.$$

The only subset of $S^{d-k-2}$ homeomorphic to $S^{d-k-2}$ being $S^{d-k-2}$ itself, we get that:

$$Lk(\tau, \mathrm{UpperComplex}_M(\mathrm{Cl} \sigma)) = Lk(\tau, \mathrm{UpperComplex}_M(K))$$

We have just proved that $\tau$ is a free simplex of $K$. Clearly, $\tau$ is then also free from above with respect to $M$ since its coface $\sigma$ has dimension $d$ and its $(d-1)$-cofaces are the upper facets of $\sigma$ by construction. This concludes the proof. ▼

**Lemma 14 (Loop invariant).** Consider $K$ such that $|K| \subseteq M^{\oplus r}$ for some $r < \mathrm{Reach}(M)$. Let $\tau$ be a vertically free simplex in $K$ relative to $M$. Let $K'$ be obtained from $K$ by collapsing $\tau$ in $K$. If $K$ satisfies the assumptions of Theorem 12, then so does $K'$.

**Proof.** Because $K' \subseteq K$, clearly $|K'| \subseteq M^{\oplus r}$ and $K'$ has a non-vertical skeleton with respect to $M$. Let us establish vertical convexity and covering projection for $K'$. Because $\tau$ is a vertically free simplex in $K$ relative to $M$, the star $\mathrm{St}(\tau, K)$ has a unique inclusion-maximal simplex $\sigma$ whose dimension is $d$. Furthermore, one of the following two situations occurs:

$$(1) \mathrm{St}(\tau, K)^{[d-1]} = \mathrm{UpperFacets}_M(\sigma) \quad \text{or} \quad (2) \mathrm{St}(\tau, K)^{[d-1]} = \mathrm{LowerFacets}_M(\sigma),$$

where $\Sigma^{[i]}$ stands for the set of $i$-simplices of $\Sigma$. Suppose that situation (1) occurs. In other words, $\tau$ is a free simplex of $K$ from above relative to $M$. This implies that the upper skin of $|\sigma|$ is contained in the upper skin of $|K|$ and $\mathrm{up}_{\mathrm{Cl} \sigma}(m) = \mathrm{up}_K(m)$ for all $m \in \pi_M(\mathrm{conv}(\sigma))$. We deduce that:

$$|K'| \cap \mathbf{N}_m M \cap B(m, r) = \begin{cases} [\mathrm{low}_K(m), \mathrm{low}_{\mathrm{Cl} \sigma}(m)] & \text{if } m \in \pi_M(\mathrm{conv}(\sigma)), \\ |K| \cap \mathbf{N}_m M \cap B(m, r) & \text{otherwise.} \end{cases}$$
We conclude that $K'$ is both vertically convex relative to $\mathcal{M}$ and has a covering projection. Similarly, we obtain the same conclusion when situation (2) occurs. It remains to check that the acyclicity condition holds for $K'$ as well. Note that acyclicity of the relation $\prec_M$ over $d$-simplices of $K$ is equivalent to acyclicity of the graph $G_M(K)$. By Lemma 13, a vertical collapse in $K$ corresponds to the removal of a terminal node of $G_M(K)$. We thus obtain acyclicity of the graph $G_M(K')$ or, equivalently, acyclicity of the relation $\prec_M$ over $d$-simplices of $K'$. ◀

## C.2 Practical version

**▶ Theorem 15 (Correctness).** Suppose that $K$ satisfies the assumptions of Theorem 12 and, in addition, for all $(d-1)$-simplices $\nu$ of $K$

$$ \max_{a \in \nu} \angle(\mathrm{Aff}(\nu), \mathbf{T}_{\pi_{\mathcal{M}}(a)}\mathcal{M}) < \frac{\pi}{4}. \qquad (4) $$

Then, **PracticalVerticalSimplification(K)** transforms $K$ into a triangulation of $\mathcal{M}$.

**Proof.** Let $\tau$ be a free simplex of $K$ whose inclusion-maximal coface $\sigma$ has dimension $d$. We prove the theorem by establishing the following equivalence: $\tau$ is vertically free in $K$ relative to $\mathcal{M}$ if and only if $\tau$ is vertically free in $K$ relative to $\mathcal{H}_\tau$.

For any facet $\nu$ of $\sigma$, let $N_\nu$ denote the unit normal to $\mathrm{conv}(\nu)$ pointing outwards $\mathrm{conv}(\sigma)$, as illustrated in Figure 14. We have assumed that for any facet $\nu$ of $\sigma$ and any vertex $a$ of $\nu$:

$$ \angle(\mathrm{Aff}(\nu), \mathbf{T}_{\pi_{\mathcal{M}}(a)}\mathcal{M}) < \frac{\pi}{4}. $$

It follows that for any facet $\nu$ of $\sigma$ and any vertex $a \in \nu$,

$$ \angle(\mathbf{n}(\pi_{\mathcal{M}}(a)), N_{\nu}) < \frac{\pi}{4}, \qquad \text{if } \nu \in \mathrm{UpperFacets}_{\mathcal{M}}(\sigma), $$

$$ \angle(\mathbf{n}(\pi_{\mathcal{M}}(a)), N_{\nu}) > \frac{3\pi}{4}, \qquad \text{if } \nu \in \mathrm{LowerFacets}_{\mathcal{M}}(\sigma). $$

<figure><img src="image_21.png" /><figcaption>■ **Figure 14** Outward-pointing normal vectors to a triangle in $\mathbb{R}^2$ can be partitioned in two groups, depending on the angle they make. One of the group consists of normal vectors to upper facets of $\sigma$, the other group consists of normal vectors to lower facets of $\sigma$.</figcaption></figure>

Given any pair of facets $\nu_0, \nu_1$ of $\sigma$, we note that we can always find a common vertex $a \in \nu_0 \cap \nu_1$. It follows that $\angle(N_{\nu_0}, N_{\nu_1}) < \frac{\pi}{2}$ if $\nu_0$ and $\nu_1$ are both upper facets of $\sigma$ relative to $\mathcal{M}$ or both lower facets of $\sigma$ relative to $\mathcal{M}$ and $\angle(N_{\nu_0}, N_{\nu_1}) > \frac{\pi}{2}$ otherwise. We can thus partition the facets of $\sigma$ in two groups, depicted in two different colors in Figure 14. In each group, any two facets have their outward-pointing normal vectors that make an angle
smaller than $\frac{\pi}{2}$. Two facets not in the same group have their outward-pointing normal vectors making an angle greater than $\frac{\pi}{2}$. Let $\nu$ be any facet of $\sigma$. Let $N$ be one of the two unit normal vectors to $\text{Aff}(\nu)$ and use it to orient $\text{Aff}(\nu)$. If $N = N_{\nu}$ (resp. $N = -N_{\nu}$), facets in the group of $\nu$ are precisely those that are upper (resp. lower) facets of $\sigma$ relative to $\text{Aff}(\nu)$. We thus deduce that either

$$ \left\{ \begin{array}{l} \text{UpperFacets}_{\mathcal{M}}(\sigma) = \text{UpperFacets}_{\text{Aff}(\nu)}(\sigma), \\ \text{LowerFacets}_{\mathcal{M}}(\sigma) = \text{LowerFacets}_{\text{Aff}(\nu)}(\sigma), \end{array} \right. $$

or

$$ \left\{ \begin{array}{l} \text{UpperFacets}_{\mathcal{M}}(\sigma) = \text{LowerFacets}_{\text{Aff}(\nu)}(\sigma), \\ \text{LowerFacets}_{\mathcal{M}}(\sigma) = \text{UpperFacets}_{\text{Aff}(\nu)}(\sigma), \end{array} \right. $$

depending upon the choice of $N$ to orient $\text{Aff}(\nu)$. The result follows immediately by noting that for $\mathcal{X} \in \{\mathcal{M}, \text{Aff}(\nu)\}$, the simplex $\tau$ is vertically free in $K$ relative to $\mathcal{X}$ if and only if

$$ \text{St}(\tau, K)^{[d-1]} = \text{UpperFacets}_{\mathcal{X}}(\sigma) \quad \text{or} \quad \text{St}(\tau, K)^{[d-1]} = \text{LowerFacets}_{\mathcal{X}}(\sigma), $$

where $\Sigma^{[i]}$ stands for the set of $i$-simplices of $\Sigma$. Thus, $\tau$ is vertically free in $K$ relative to $\mathcal{M}$ if and only if $\tau$ is vertically free in $K$ relative to $\text{Aff}(\nu)$. We get the desired equivalence. $\quad$
### D Additional material for Section 5

This appendix contains missing material for Section 5.

#### D.1 Definition of $I(\varepsilon, \delta)$

We define $I(\varepsilon, \delta)$ as the range of values of $\alpha$ used in [8] for Theorem 17. Following [8], we define $I(\varepsilon, \delta)$ by distinguishing two cases. If $\delta \ge \varepsilon$, then the authors in [8] establish that the following interval of values for $\alpha$ is valid:

$$I(\varepsilon, \delta) = \left[ \frac{1}{2} (\mathcal{R} + \varepsilon - \sqrt{\Delta_0}), \frac{1}{2} (\mathcal{R} + \varepsilon + \sqrt{\Delta_0}) \right],$$

where $\Delta_0 = 2(\mathcal{R} - \delta)^2 - (\mathcal{R} + \varepsilon)^2$. The definition of $I(\varepsilon, \delta)$ is more involved when $\delta \le \varepsilon$. Let

$$\Delta_1 = \frac{1}{\mathcal{R}^2} (\varepsilon^2 - (\mathcal{R} - \delta)^2)^2 - 10 (\varepsilon^2 - (\mathcal{R} - \delta)^2) - 7\mathcal{R}^2.$$

Assuming that $\varepsilon < \mathcal{R}$ and $\delta < \mathcal{R}$ satisfy the strict homotopy condition:

$$(\mathcal{R} - \delta)^2 - \varepsilon^2 \ge (4\sqrt{2} - 5)\mathcal{R}^2,$$

it has been shown in [8] that $\Delta_1$ is non-negative and thus, it makes sense to define

$$\beta_{\min} = \frac{1}{4} \left( \frac{(\mathcal{R} - \delta)^2 + \mathcal{R}^2 - \varepsilon^2}{\mathcal{R}} - \sqrt{\Delta_1} \right) \quad \text{and} \quad \beta_{\max} = \frac{1}{4} \left( \frac{(\mathcal{R} - \delta)^2 + \mathcal{R}^2 - \varepsilon^2}{\mathcal{R}} + \sqrt{\Delta_1} \right).$$

$\Delta_1$ in [8] has been chosen precisely to be the discriminant of the quadratic polynomial:

$$\varepsilon^2 - (\mathcal{R} - \delta)^2 + \mathcal{R}^2 + \beta \frac{1}{\mathcal{R}} (\varepsilon^2 - \mathcal{R}^2 - (\mathcal{R} - \delta)^2) + 2\beta^2$$

and $[\beta_{\min}, \beta_{\max}]$ represents the interval of values of $\beta$ for which the polynomial is non-negative. The non-negativity can be rewritten as:

$$(1 + \frac{\beta}{\mathcal{R}}) \varepsilon^2 + \beta^2 + \frac{\beta}{\mathcal{R}} (\mathcal{R}^2 - (\mathcal{R} - \delta)^2) \le (\mathcal{R} - \delta)^2 - (\mathcal{R} - \beta)^2. \quad (18)$$

Let

$$\alpha_{\min} = \sqrt{\left(1 + \frac{\beta_{\min}}{\mathcal{R}}\right) \varepsilon^2 + \beta_{\min}^2 + \frac{\beta_{\min}}{\mathcal{R}} (\mathcal{R}^2 - (\mathcal{R} - \delta)^2)},$$

$$\alpha_{\max} = \sqrt{(\mathcal{R} - \delta)^2 - (\mathcal{R} - \beta_{\max})^2},$$

Equation (18) shows that $\alpha_{\min} \le \alpha_{\max}$. It is then proven in [8] that when $\delta \le \varepsilon$ the non-empty interval $I(\varepsilon, \delta) = [\alpha_{\min}, \alpha_{\max}]$ can be used for Theorem 17.

#### D.2 Possible $\beta$ for Theorem 18

The next lemma enunciates a result of [8] that provides a “large” value of $\beta$ for which $M^{\oplus\beta} \subseteq P^{\oplus\alpha}$ and which can be plugged in Theorem 18.

**► Lemma D1 ([8]).** Let $M$ be a smooth submanifold whose reach is larger than or equal to $\mathcal{R}$ and let $P$ be a point set such that $M \subseteq P^{\oplus\varepsilon}$ for some $\varepsilon \ge 0$. Then, $M^{\oplus\beta} \subseteq P^{\oplus\alpha}$ whenever

$$\beta = -\frac{\varepsilon^2}{2\mathcal{R}} + \sqrt{\alpha^2 + \frac{\varepsilon^4}{4\mathcal{R}^2} - \varepsilon^2}.$$
E Proof of Theorem 18 in Section 5

The goal of this appendix is to establish Theorem 18:

**▶ Theorem 18.** Assume $\mathcal{M} \subseteq P^{\oplus\varepsilon}$ and $P \subseteq \mathcal{M}^{\oplus\delta}$ for $\varepsilon, \delta \ge 0$ that satisfy the strict homotopy condition. Let $\alpha \in [\delta, \frac{2(\mathcal{R}-\delta)}{3}) \cap I(\varepsilon, \delta)$ and $\beta > 0$ such that $\mathcal{M}^{\oplus\beta} \subseteq P^{\oplus\alpha}$. Suppose that for all $i$-simplices $\tau \in \text{Del}(P, \alpha)$, $0 < i < d$ and all $(d-1)$-simplices $\nu \in \text{Del}(P, \alpha)$ it holds:

$$ \max_{x \in \text{conv}(\tau)} \angle(\text{Aff}(\tau), \mathbf{T}_{\pi_{\mathcal{M}}(x)}\mathcal{M}) < \frac{\pi}{2}, \qquad (5) $$

$$ \min_{a \in \tau} \angle(\text{Aff}(\tau), \mathbf{T}_{\pi_{\mathcal{M}}(a)}\mathcal{M}) < \arcsin\left(\frac{(\mathcal{R} + \beta)^2 - (\mathcal{R} + \delta)^2 - \alpha^2}{2(\mathcal{R} + \delta)\alpha}\right) \text{ and} \qquad (6) $$

$$ \min_{x \in \text{conv}(\nu)} \angle(\text{Aff}(\nu), \mathbf{T}_{\pi_{\mathcal{M}}(x)}\mathcal{M}) < \frac{\pi}{2} - 2\arcsin\left(\frac{\alpha}{2(\mathcal{R} - \delta - \alpha)}\right). \qquad (7) $$

Then, $\text{Del}(P, \alpha)$ satisfies the injective projection, covering projection, vertical convexity and acyclicity assumptions of Theorem 12. Furthermore, both the upper and lower complexes of $\text{Del}(P, \alpha)$ relative to $\mathcal{M}$ are triangulations of $\mathcal{M}$ and NaiveSquash$(P, \alpha)$ returns a triangulation of $\mathcal{M}$.

**▶ Remark E1.** It is easy to check that Conditions (5), (6) and (7) in Theorem 18 are well-defined. Because $P \subseteq \mathcal{M}^{\oplus\delta}$, we obtain that $|\text{Del}(P, \alpha)| \subseteq P^{\oplus\alpha} \subseteq \mathcal{M}^{\oplus(\delta+\alpha)}$. Since $\delta + \alpha < \mathcal{R} \le \text{Reach}(\mathcal{M})$,

$$ |\text{Del}(P, \alpha)| \subseteq \mathbb{R}^d \setminus \text{axis}(\mathcal{M}) $$

and the projection map $\pi_{\mathcal{M}}$ is thus well-defined on the support of any simplex in $\text{Del}(P, \alpha)$. It follows that the left sides of Conditions (5), (6) and (7) are well-defined. We claim that

$$ -1 \le \frac{(\mathcal{R} + \beta)^2 - (\mathcal{R} + \delta)^2 - \alpha^2}{2(\mathcal{R} + \delta)\alpha} \le 1. $$

The left inequality is equivalent to $\beta + \alpha \ge \delta$ which holds since we have assumed that $\alpha \ge \delta$. The right inequality is equivalent to $\beta \le \delta + \alpha$ which holds because we have assumed that $P \subseteq \mathcal{M}^{\oplus\delta}$ and $\mathcal{M}^{\oplus\beta} \subseteq P^{\oplus\alpha}$, implying that $\mathcal{M}^{\oplus\beta} \subseteq \mathcal{M}^{\oplus(\delta+\alpha)}$. Hence, the right side of Condition (6) is well-defined. Similarly, using the assumption $\alpha \le \frac{2}{3}(\mathcal{R} - \delta)$, we easily get that

$$ 0 \le \frac{\alpha}{2(\mathcal{R} - \delta - \alpha)} \le 1, $$

showing that the right side of Condition (7) is also well-defined.

**Proof of Theorem 18.** Injective projection for $\text{Del}(P, \alpha)$ is shown in Section E.1 (Lemma E2). Covering projection and vertical convexity for $\text{Del}(P, \alpha)$ are established in Section 5.2 (Lemma 20). Acyclicity is established in Section E.3 (Lemma E7). Hence, all the assumptions of Lemma 7 and Theorem 12 are satisfied. By Lemma 7, the upper and lower complexes of $\text{Del}(P, \alpha)$ relative to $\mathcal{M}$ are each a triangulation of $\mathcal{M}$. By Theorem 12, NaiveSquash$(P, \alpha)$ returns a triangulation of $\mathcal{M}$.

<figure><img src="image_22.png" /></figure>
## E.1 Injective projection

In this section, we characterize non-verticality of an $i$-simplex $\tau \in \mathrm{Del}(P, \alpha)$ relative to $\mathcal{M}$.

**Lemma E2.** Let $P$ be a finite point set in $\mathbb{R}^d$ such that $P \subseteq \mathcal{M}^{\oplus\delta}$ for some $\delta \ge 0$. Let $\alpha \in [0, \mathbb{R} - \delta)$. Then, for all $i$-simplices $\tau \in \mathrm{Del}(P, \alpha)$ with $0 < i < d$,

$$ (5) \iff \tau \text{ is non-vertical relative to } \mathcal{M} $$

*Proof.* It is easy to see that $\tau$ is non-vertical relative to $\mathcal{M}$ if and only if for all $x \in \mathrm{conv}(\tau)$

$$ \angle(\mathbf{N}_{\pi_M(x)}\mathcal{M}, \mathrm{Aff}(\tau)) > 0. $$

Using Property A2, $\angle(\mathbf{N}_{\pi_M(x)}\mathcal{M}, \mathrm{Aff}(\tau)) = \frac{\pi}{2} - \angle(\mathrm{Aff}(\tau), \mathbf{T}_{\pi_M(x)}\mathcal{M})$ and the above inequality is equivalent to $\angle(\mathrm{Aff}(\tau), \mathbf{T}_{\pi_M(x)}\mathcal{M}) < \frac{\pi}{2}$. Hence, $\tau$ is non-vertical relative to $\mathcal{M}$ if and only if

$$ \max_{x \in \mathrm{conv}(\tau)} \angle(\mathrm{Aff}(\tau), \mathbf{T}_{\pi_M(x)}\mathcal{M}) < \frac{\pi}{2}, $$

which is equivalent to (5).

<figure><img src="image_23.png" /></figure>

## E.2 Vertical convexity

In this section, we establish Lemma 23, which we need for the proof of Lemma 20.

**Lemma 23.** Under the assumptions of Lemma 20, let $\gamma \in \mathrm{Del}(P, \alpha)$ and $x \in \mathrm{relint}(\mathrm{conv}(\gamma))$. If for some $\lambda > 0$ (resp. $\lambda < 0$), the segment $(x, x + \lambda \mathbf{n}(\pi_M(x))]$ lies outside $|\mathrm{Del}(P, \alpha)|$, then it intersects an upper (resp. lower join).

Plugging the assumptions of Lemma 20 inside Lemma 23 and using Lemma E2 to replace Condition (5) with the assumption that $\tau$ is non-vertical relative to $\mathcal{M}$, we can rewrite Lemma 23 as follows:

**Lemma E3.** Let $\mathcal{M} \subseteq P^{\oplus\epsilon}$ and $P \subseteq \mathcal{M}^{\oplus\delta}$ for some $\epsilon, \delta \ge 0$ that satisfy the strict homotopy condition. Let $\alpha \in [\delta, \mathbb{R} - \delta) \cap I(\epsilon, \delta)$ and $\beta > 0$ be such that $\mathcal{M}^{\oplus\beta} \subseteq P^{\oplus\alpha}$. Suppose that for all $i$-simplices $\tau \in \mathrm{Del}(P, \alpha)$ with $0 < i < d$, $\tau$ is non-vertical relative to $\mathcal{M}$ and Condition (6) hold. Let $\gamma \in \mathrm{Del}(P, \alpha)$ and $x \in \mathrm{relint}(\mathrm{conv}(\gamma))$. If for some $\lambda > 0$ (resp. $\lambda < 0$), the segment $(x, x + \lambda \mathbf{n}(\pi_M(x))]$ lies outside $|\mathrm{Del}(P, \alpha)|$, then it intersects an upper (resp. lower join).

Hence, proving Lemma 23 is equivalent to proving Lemma E3. Before giving the proof at the end of the section, consider a finite point set $P \subseteq \mathbb{R}^d$ and recall that, as explained in Section 5.2, the boundary of $P^{\oplus\alpha}$ can be decomposed into faces. Those faces are in one-to-one correspondence with the boundary simplices of $\mathrm{Del}(P, \alpha)$. Associate to each boundary $i$-simplex $\gamma \in \partial \mathrm{Del}(P, \alpha)$ the $(d - i - 1)$-sphere

$$ S(\gamma, \alpha) = \bigcap_{p \in \gamma} \partial B(p, \alpha). $$

Equivalently, $S(\gamma, \alpha)$ can be defined as the locus of the centers of the $(d-1)$-spheres with radius $\alpha$ that circumscribe $\gamma$. The center $c_\gamma$ of $S(\gamma, \alpha)$ coincides with the center of the smallest $(d-1)$-sphere circumscribing $\gamma$; see Figure 15. The face of $\partial P^{\oplus\alpha}$ dual to $\gamma \in \partial \mathrm{Del}(P, \alpha)$ can then be described as

$$ F_{\gamma} = S(\gamma, \alpha) \cap \partial P^{\oplus\alpha}. $$
<figure><img src="image_24.png" /><figcaption>Figure 15 For $d=2$ and $\gamma = \{a, b\}$, the set $S(\gamma, \alpha)$ is a 0-sphere that consists of the two white dots. Only one of them lies on $\partial P^{\oplus\alpha}$ and therefore belongs to $F_{\gamma}$. In this particular case, $F_{\gamma}^{+} = F_{\gamma}$.</figcaption></figure>

<figure><img src="image_25.png" /></figure>

<figure><img src="image_26.png" /></figure>

<figure><img src="image_27.png" /><figcaption>Figure 16 Highest point $s_{\gamma}(x)$ of $S(\gamma, \alpha)$ in direction $\mathbf{n}(x^*)$ when $\mathcal{M}$ is a surface in $\mathbb{R}^3$ and $\dim \gamma = 0$ (left), $\dim \gamma = 1$ (middle), and $\dim \gamma = 2$ (right).</figcaption></figure>

We also recall that the upper face $F_{\gamma}^{+}$ (resp. lower face $F_{\gamma}^{-}$) designates the restriction of $F_{\gamma}$ to the upper skin (resp. lower skin) of $P^{\oplus\alpha}$. The set $F_{\gamma}^{+} * \text{conv}(\gamma)$ (resp. $F_{\gamma}^{-} * \text{conv}(\gamma)$) designates the upper (resp. lower) join of $\gamma$.

More generally, given any simplex $\gamma \subseteq \mathbb{R}^d$ (not necessarily in $\text{Del}(P, \alpha)$), we define $S(\gamma, \alpha) = \bigcap_{p \in \gamma} \partial B(p, \alpha)$. Assuming that $\text{conv}(\gamma) \subseteq \mathbb{R}^d \setminus \text{axis}(\mathcal{M})$ and $S(\gamma, \alpha) \neq \emptyset$, we associate to $\gamma$ and any $x \in \text{conv}(\gamma)$ the highest point of $S(\gamma, \alpha)$ in direction $\mathbf{n}(\pi_{\mathcal{M}}(x))$ which we denote as $s_{\gamma}(x)$; see Figure 16. Let $\text{Bis}(\gamma)$ be the bisector of $\gamma$. By construction, $s_{\gamma}(x) \in S(\gamma, \alpha) \subseteq \text{Bis}(\gamma)$. Writing $x^* = \pi_{\mathcal{M}}(x)$ for short, we make the following remark:

► **Remark E4.** For any simplex $\gamma \subseteq \mathbb{R}^d$ and $\alpha \ge 0$ such that $\text{conv}(\gamma) \subseteq \mathbb{R}^d \setminus \text{axis}(\mathcal{M})$ and $S(\gamma, \alpha) \neq \emptyset$ and for any $x \in \text{conv}(\gamma)$,

$$ \angle(\mathbf{n}(x^*), s_{\gamma}(x) - c_{\gamma}) = \angle(\mathbf{N}_{x^*} \mathcal{M}, \text{Bis}(\gamma)) = \angle(\text{Aff}(\gamma), \mathbf{T}_{x^*} \mathcal{M}). $$

We start with a lemma.
**► Lemma E5.** Assume that $\mathcal{M} \subseteq P^{\oplus\varepsilon}$ and $P \subseteq \mathcal{M}^{\oplus\delta}$ for some $\varepsilon, \delta \ge 0$ and let $\alpha \in [\delta, \mathcal{R}-\delta)$. Let $\beta > 0$ such that $\mathcal{M}^{\oplus\beta} \subseteq P^{\oplus\alpha}$. Consider a simplex $\tau$ with $0 < \dim \tau < d$ that satisfies (6). Suppose that $\tau$ is a boundary simplex of $\mathrm{Del}(P, \alpha)$. Then, we can always find $a \in \tau$ at which the following implication holds:

$$s_{\tau}(a) \text{ lies on } \partial P^{\oplus\alpha} \implies s_{\tau}(a) \text{ lies on the upper skin of } P^{\oplus\alpha}. \qquad (19)$$

<figure><img src="image_28.png" /><figcaption>■ **Figure 17** We reach a contradiction in the proof of Lemma E5 by assuming that $s_{\tau}(a)$ lies on the lower skin of $\partial P^{\oplus\alpha}$.</figcaption></figure>

**Proof.** Because $\tau$ is a boundary simplex of $\mathrm{Del}(P, \alpha)$, we have that $S(\tau, \alpha) \neq \emptyset$ and for any $x \in \mathrm{conv}(\tau)$, the point $s_{\tau}(x)$ exists. Consider $a \in \tau$ and write $a^* = \pi_{\mathcal{M}}(a)$ for short. Suppose that $a \in \tau$ is such that

$$s_{\tau}(a) \text{ lies on } \partial P^{\oplus\alpha} \quad \text{and} \quad s_{\tau}(a) \text{ does not lie on the upper skin of } P^{\oplus\alpha}. \qquad (20)$$

The only possibility is thus that $s_{\tau}(a)$ lies on the lower skin of $P$, as illustrated in Figure 17. Let $z = a^* + \mathcal{R}\mathbf{n}(a^*)$ and note that the ball $B(z, \mathcal{R})$ is tangent to $\mathcal{M}$ at $a^*$ and does not contain any point of $\mathcal{M}$ in its interior. Since $\mathcal{M}^{\oplus\beta} \subseteq P^{\oplus\alpha}$, we deduce that the lower skins of both $\mathcal{M}^{\oplus\beta}$ and $P^{\oplus\alpha}$ do not intersect the interior of $B(z, \beta + \mathcal{R})$. Hence, $\|z - s_{\tau}(a)\| \ge \mathcal{R} + \beta$. By construction, $\|a - s_{\tau}(a)\| = \alpha$ and $\|a - z\| \le \|a - a^*\| + \|a^* - z\| = \delta + \mathcal{R}$. Consider the triangle with vertices $a, s_{\tau}(a)$ and $z$. Using the formula that gives the angle at vertex $a$ in triangle $azs_{\tau}(a)$ with respect to the length of the sides of the triangle, we obtain

$$\begin{align*}
\cos(\angle(\mathbf{n}(a^*), s_{\tau}(a) - a)) &= \frac{\|a - z\|^2 + \|a - s_{\tau}(a)\|^2 - \|z - s_{\tau}(a)\|^2}{2\|a - z\|\|a - s_{\tau}(a)\|} \\
&\le \frac{\|a - z\|^2 + \alpha^2 - (\mathcal{R} + \beta)^2}{2\|a - z\|\alpha} \\
&\le \frac{(\delta + \mathcal{R})^2 + \alpha^2 - (\mathcal{R} + \beta)^2}{2(\delta + \mathcal{R})\alpha}, \tag{21}
\end{align*}$$

where the first inequality comes from the fact that $\|a - s_{\tau}(a)\| = \alpha$ and $\|z - s_{\tau}(a)\| \ge \mathcal{R} + \beta$ and the second inequality comes from the fact that $\lambda \mapsto \frac{\lambda^2 - A}{\lambda}$ is increasing for $A > 0$ and
$\lambda > 0$, applied with $\lambda = \|a - z\|$ and $A = -\alpha^2 + (\mathcal{R} + \beta)^2$. We are going to exhibit a point $a \in \tau$ for which (21) does not hold, showing that for that $a$, statement (20) is false and its negation, statement (19), is true. By Remark E1

$$-1 \le \frac{(\mathcal{R} + \beta)^2 - (\mathcal{R} + \delta)^2 - \alpha^2}{2(\mathcal{R} + \delta)\alpha} \le 1.$$

and it makes sense to introduce the angle

$$\theta = \arcsin \left( \frac{(\mathcal{R} + \beta)^2 - (\mathcal{R} + \delta)^2 - \alpha^2}{2(\mathcal{R} + \delta)\alpha} \right) \in [-\frac{\pi}{2}, \frac{\pi}{2}].$$

Assumption (6) can then be rewritten as $\min_{a \in \tau} \angle(\mathrm{Aff}(\tau), \mathbf{T}_{\pi_M(a)}\mathcal{M}) < \theta$ and we let $a \in \tau$ be any vertex such that

$$\angle(\mathrm{Aff}(\tau), \mathbf{T}_{a^*}\mathcal{M}) < \theta. \qquad (22)$$

Let us show that:

$$\angle(\mathbf{n}(a^*), s_{\tau}(a) - a) < \frac{\pi}{2} + \theta. \qquad (23)$$

<figure><img src="image_29.png" /><figcaption>Figure 18 Notation for the proof of Lemma E5.</figcaption></figure>

If $\angle(\mathbf{n}(a^*), s_{\tau}(a) - a) < \frac{\pi}{2}$, clearly (23) holds. If $\angle(\mathbf{n}(a^*), s_{\tau}(a) - a) \ge \frac{\pi}{2}$ (see Figure 18), then using (22) and Remark E4, we get that

$$\theta > \angle(\mathrm{Aff}(\tau), \mathbf{T}_{a^*}\mathcal{M}) = \angle(\mathbf{n}(a^*), s_{\tau}(a) - c_{\tau}) = \angle(\mathbf{n}(a^*), c_{\tau} - a) - \frac{\pi}{2} \\ \ge \angle(\mathbf{n}(a^*), s_{\tau}(a) - a) - \frac{\pi}{2}.$$

Hence, we obtain (23) as desired. Taking the cosine on both sides of (23), we obtain that

$$\cos(\angle(\mathbf{n}(a^*), s_{\tau}(a) - a)) > -\sin \theta = \frac{(\mathcal{R} + \delta)^2 + \alpha^2 - (\mathcal{R} + \beta)^2}{2(\mathcal{R} + \delta)\alpha}.$$

But, this contradicts (21) which was a consequence of (20). Hence, for that particular $a$, (20) is false. We thus deduce that there exists $a \in \tau$ such that if $s_{\tau}(a)$ lies on $\partial P^{\oplus\alpha}$, then $s_{\tau}(a)$ lies on the upper skin of $P^{\oplus\alpha}$. This concludes the proof. ▼
Before proving Lemma E3, we make a useful remark:

► **Remark E6.** Consider a $(d-1)$-simplex $\nu \subseteq \mathbb{R}^d$ that is non-vertical relative to $\mathcal{M}$ and whose support is contained in $\mathbb{R}^d \setminus \text{axis}(\mathcal{M})$ and let $N$ be a unit vector orthogonal to $\text{Aff}(\nu)$. If $N \cdot \mathbf{n}(\pi_{\mathcal{M}}(x)) > 0$ for some $x \in \text{conv}(\nu)$, then $N \cdot \mathbf{n}(\pi_{\mathcal{M}}(x)) > 0$ for all $x \in \text{conv}(\nu)$.

**Proof of Lemma E3.** The proof is by descending induction over the dimension of $\gamma$.

**Induction basis:** Suppose that $\gamma$ has dimension $d-1$. Then, $\text{Aff}(\gamma)$ is a hyperplane and $S(\gamma, \alpha)$ is a 0-sphere that consists of two points (possibly equal). Consider $x \in \text{relint}(\text{conv}(\gamma))$ and $\lambda > 0$ such that the segment $(x, x + \lambda \mathbf{n}(\pi_{\mathcal{M}}(x))]$ lies outside $|\text{Del}(P, \alpha)|$. Let $N$ be the unit vector orthogonal to $\text{Aff}(\gamma)$ that satisfies

$$ \mathbf{n}(\pi_{\mathcal{M}}(x)) \cdot N > 0 $$

and observe that, for $\mu > 0$ small enough, the segment $(x, x + \mu N]$ lies outside $|\text{Del}(P, \alpha)|$. Let $s$ be the highest point of $S(\gamma, \alpha)$ along direction $N$. By duality between the boundary simplices of $\text{Del}(P, \alpha)$ and the faces of $\partial P^{\oplus\alpha}$, we deduce that $s$ lies on $\partial P^{\oplus\alpha}$. Let $a \in \gamma$. Since $\gamma$ is non-vertical, Remark E6 tells us that

$$ \mathbf{n}(\pi_{\mathcal{M}}(a)) \cdot N > 0. $$

Note that $s$ is also the point of $S(\gamma, \alpha)$ highest along direction $\mathbf{n}(\pi_{\mathcal{M}}(a))$, namely $s = s_{\gamma}(a)$. Thus, $s_{\gamma}(a)$ lies on $\partial P^{\oplus\alpha}$. Applying Lemma E5 with $\tau = \gamma$, we get that $s_{\gamma}(a)$ lies on the upper skin of $P^{\oplus\alpha}$. Hence, the set $\{s_{\gamma}(a)\} * \text{conv}(\gamma)$ is contained in the upper join of $\gamma$ and the segment $(x, x + \lambda \mathbf{n}(\pi_{\mathcal{M}}(x))]$ has a non-empty intersection with the upper join of $\gamma$. This concludes the induction basis.

**Induction step:** Let $k \in \{0, \dots, d-1\}$ and assume that the lemma holds for all $\gamma$ with dimension $i \ge k+1$. Let us prove that the lemma also holds when $\gamma$ has dimension $k$. We distinguish two cases:

(a) $\gamma$ has no proper coface in $\text{Del}(P, \alpha)$. In that case, the whole sphere $S(\gamma, \alpha)$ lies on $\partial P^{\oplus\alpha}$ and so does $s_{\gamma}(a)$ for any $a \in \gamma$. Pick $a \in \gamma$. By Lemma E5 applied with $\tau = \gamma$, $s_{\gamma}(a)$ lies on the upper skin of $P^{\oplus\alpha}$. Since for $0 \le k < d-1$, the $(d-k-1)$-sphere $S(\gamma, \alpha)$ is connected, the whole sphere $S(\gamma, \alpha)$ has to lie on the upper skin. Hence, $S(\gamma, \alpha) * \text{conv}(\gamma)$ is the upper join of $\gamma$. It follows that for any point $x \in \text{relint}(\text{conv}(\gamma))$ and any $\lambda > 0$, the upper join $S(\gamma, \alpha) * \text{conv}(\gamma)$ has a non-empty intersection with the segment $(x, x + \lambda \mathbf{n}(\pi_{\mathcal{M}}(x))]$. This concludes case (a).

(b) $\gamma$ has at least one proper coface in $\text{Del}(P, \alpha)$; see Figure 19. Consider $z \in \text{relint}(\text{conv}(\gamma))$ and $\lambda > 0$ such that the segment $(z, z + \lambda \mathbf{n}(\pi_{\mathcal{M}}(z))]$ lies outside $|\text{Del}(P, \alpha)|$ and let us prove that the segment intersects an upper join. Write $z^* = \pi_{\mathcal{M}}(z)$ for short. Let $\Sigma = \text{St}(\gamma, \text{Del}(P, \alpha))$ denote the set of cofaces of $\gamma$ in $\text{Del}(P, \alpha)$. Denote the tangent vector space to $|\Sigma|$ at $z$ as $\text{Tan}(z, |\Sigma|)$ and define the angle

$$ \varphi = \min_{0 \neq v \in \text{Tan}(z, |\Sigma|)} \angle(\mathbf{n}(z^*), v). $$

Because of our assumption that $(z, z + \lambda \mathbf{n}(\pi_{\mathcal{M}}(z))]$ lies outside $|\text{Del}(P, \alpha)|$, we have that $\varphi > 0$. Consider a ball $B$ centered at $z$ whose radius is small enough so that $B \subseteq P^{\oplus\alpha}$ and $B$ does not intersect the support of any simplex in $\text{Del}(P, \alpha) \setminus \Sigma$. Note that $|\Sigma| \cap B$ is star-shaped at $z$, that is,

$$ x \in |\Sigma| \cap B \implies [x, z] \subseteq |\Sigma| \cap B. $$
<figure><img src="image_30.png" /><figcaption>Figure 19 Construction of a path Γ connecting z ∈ relint(conv(γ)) to z' ∈ relint(conv(σ)) when d = 2 and γ is a vertex. As we move any point x ∈ [z, z'] in direction n(x*), x enters the gray cone formed of all points p such that ∠(n(z*), p - x) < ϕ and therefore goes outside |Del(P, α)|.</figcaption></figure>

By considering B small enough, we may assume furthermore that for all $x \in |\Sigma| \cap B$ with $x \neq z$, the half-line with origin at z and passing through x intersects $|\Sigma| \cap B$ in a radius of B, that is, a segment connecting the center of B to its bounding sphere $\partial B$. We also assume that B is small enough so that for all $x \in B$

$$ \angle(\mathbf{n}(z^*), \mathbf{n}(x^*)) < \varphi, $$

where, as usual, we write $x^* = \pi_M(x)$. Consider the $(d-k)$-dimensional affine space $H$ passing through z and orthogonal to $\text{Aff}(\gamma)$. Associate to each proper coface $\sigma \in \Sigma \setminus \{\gamma\}$ the angle:

$$ \psi_{\sigma} = \min_{s \in \text{conv}(\sigma) \cap \partial B \cap H} \angle(\mathbf{n}(z^*), s - z). $$

Note that $\psi_{\sigma} \ge \varphi$ because $\varphi$ can be expressed as

$$ \varphi = \min_{s \in |\Sigma| \cap \partial B} \angle(\mathbf{n}(z^*), s - z). $$

Let $\sigma \in \Sigma \setminus \{\gamma\}$ that achieves the smallest $\psi_{\sigma}$. One can always find $z' \in \text{relint}(\text{conv}(\sigma)) \cap B$ and $\mu > 0$ such that the $\mu$-offset of the segment $[z, z']$ is contained in B; see Figure 19. Let

$$ f(x) = x + \mu \mathbf{n}(x^*). $$

By construction, for all $x \in [z, z']$, we have $(x, f(x)] \subseteq B \subseteq P^{\oplus \alpha}$. Moreover,

$$ (x, f(x)] \subseteq P^{\oplus \alpha} \setminus |\text{Del}(P, \alpha)|. $$
Indeed, $\sigma$ has been chosen so that any point $x \in \text{conv}(\sigma) \cap B$ is the highest point of $|\Sigma| \cap B$ along direction $\mathbf{n}(z^*)$ and therefore

$$ (x, x + \mu \mathbf{n}(z^*)) \subseteq P^{\oplus \alpha} \setminus |\text{Del}(P, \alpha)| $$

Because $\angle(\mathbf{n}(z^*), \mathbf{n}(x^*)) < \varphi \le \psi_\sigma$, the same remains true when replacing $\mathbf{n}(z^*)$ with $\mathbf{n}(x^*)$ in the above inclusion; see Figure 19. Consider now the path

$$ \Gamma = (z, f(z)] \cup f([z, z')] \cup [f(z'), z'). $$

By construction,

$$ \Gamma \subseteq P^{\oplus \alpha} \setminus |\text{Del}(P, \alpha)| $$

and, by Remark 22, $\Gamma$ is covered either by upper joins or by lower joins but cannot be covered by both. Applying the induction hypothesis to $\sigma$, we obtain that sufficiently close to $z' \in \text{conv}(\sigma)$, the path $\Gamma$ is covered by an upper join. Hence, the entire path $\Gamma$ is covered by upper joins and the segment $(z, z + \lambda \mathbf{n}(z^*))$ intersects an upper join. This concludes case (b) and the proof of the lemma. ◀

### E.3 Acyclicity

The relation $\prec_M$ over the $d$-simplices of a simplicial complex $K$ is not acyclic in general; see Figure 6. However, when $K$ is the $\alpha$-complex of a finite point set $P$ within distance $\delta$ of $M$, we state conditions under which $\prec_M$ becomes acyclic. The result is akin to an acyclicity result on Delaunay complexes in [28].

**Lemma E7 (Acyclicity).** Let $P$ be a finite point set in $\mathbb{R}^d$ such that $P \subseteq M^{\oplus \delta}$ for some $\delta \ge 0$. Let $\alpha \in [0, \frac{2(\mathcal{R}-\delta)}{3})$. Assume that all $(d-1)$-simplices $\nu \in \text{Del}(P, \alpha)$ are non-vertical relative to $M$ and satisfy

$$ \min_{x \in \text{conv}(\nu)} \angle(\text{Aff}(\nu), \mathbf{T}_{\pi_M(x)}M) < \frac{\pi}{2} - 2 \arcsin \left( \frac{\alpha}{2(\mathcal{R} - \delta - \alpha)} \right). $$

Then, the relation $\prec_M$ defined over the Delaunay $d$-simplices is acyclic.

Any $(d-1)$-simplex $\nu$ that satisfies the conditions of the above lemma is non-vertical relative to $M$ and has a support contained in $\mathbb{R}^d \setminus \text{axis}(M)$.

**Definition 8.** Consider a $(d-1)$-simplex $\nu$ that is non-vertical relative to $M$ and whose support is contained in $\mathbb{R}^d \setminus \text{axis}(M)$. We say that the unit vector $N$ normal to $\text{Aff}(\nu)$ is consistently oriented with $M$ if there exists $x \in \text{conv}(\nu)$ such that $N \cdot \mathbf{n}(\pi_M(x)) > 0$.

By Remark E6, $\nu$ has exactly one of its two unit normal vectors that is consistently oriented with $M$ and for that unit vector $N$, we have that $N \cdot \mathbf{n}(\pi_M(x)) > 0$ for all $x \in \text{conv}(\nu)$. Let $Z(\sigma)$ designates the center of the $(d-1)$-sphere that circumscribes a $d$-simplex $\sigma$ and associate to each point $z \in \mathbb{R}^d \setminus \text{axis}(M)$ the real number:

$$ \text{alt}_M(z) = (z - \pi_M(z)) \cdot \mathbf{n}(\pi_M(z)). $$

The proof of Lemma E7 relies on the following lemma:
**► Lemma E9.** Let P be a finite point set in $\mathbb{R}^d$ such that $P \subseteq \mathcal{M}^{\oplus\delta}$ for some $\delta \ge 0$. Let $\alpha \in [0, \frac{2(\mathcal{R}-\delta)}{3})$ and consider a $(d-1)$-simplex $\nu \in \text{Del}(P, \alpha)$ that is non-vertical relative to $\mathcal{M}$. Assume that

$$ \min_{x \in \text{conv}(\nu)} \angle(\text{Aff}(\nu), \mathbf{T}_{\pi_{\mathcal{M}}(x)}\mathcal{M}) < \frac{\pi}{2} - 2 \arcsin \left( \frac{\alpha}{2(\mathcal{R} - \delta - \alpha)} \right). $$

1. Let N be the unit normal vector to $\text{Aff}(\nu)$ that is consistently oriented with $\mathcal{M}$. As we move a point $z$ on the segment $V(\nu, P) \cap P^{\oplus\alpha}$ along direction $N$, $\text{alt}_{\mathcal{M}}(z)$ is increasing.

2. Suppose that $\nu$ is the common facet of two d-simplices $\sigma_0, \sigma_1 \in \text{Del}(P, \alpha)$ such that $\sigma_0 \prec_{\mathcal{M}} \sigma_1$. As we move a point $z$ on the Voronoi edge dual to $\nu$ in direction $Z(\sigma_1) - Z(\sigma_0)$, $\text{alt}_{\mathcal{M}}(z)$ is increasing and therefore:

$$ \sigma_0 \prec_{\mathcal{M}} \sigma_1 \implies \text{alt}_{\mathcal{M}}(Z(\sigma_0)) < \text{alt}_{\mathcal{M}}(Z(\sigma_1)). $$

**Proof.** We first note that $V(\nu, P) \cap P^{\oplus\alpha}$ is indeed a segment because

$$ V(\nu, P) \cap P^{\oplus\alpha} = V(\nu, P) \cap \bigcap_{p \in \nu} B(p, \alpha) $$

and this segment is parallel to $N$. Let $z_0$ and $z_1$ be the two endpoints of that segment and name them so that $(z_1 - z_0) \cdot N \ge 0$. For all $t \in [0, 1]$, let $z(t) = (1-t)z_0 + tz_1$ and $\varphi(t) = \text{alt}_{\mathcal{M}}(z(t))$. We show the first item of the lemma by establishing that $\varphi'(t) > 0$ for all $t \in (0, 1)$. Since $\nabla \text{alt}_{\mathcal{M}}(z) = \mathbf{n}(\pi_{\mathcal{M}}(z))$ and $z'(t) = z_1 - z_0$, we obtain that

$$ \begin{aligned} \varphi'(t) &= \nabla \text{alt}_{\mathcal{M}}(z(t)) \cdot z'(t) \\ &= \mathbf{n}(\pi_{\mathcal{M}}(z(t))) \cdot (z_1 - z_0). \end{aligned} $$

To show that $\varphi'(t) > 0$, it suffices to show that $\angle(\mathbf{n}(z(t)), z_1 - z_0) < \frac{\pi}{2}$ for all $t \in (0, 1)$; see Figure 20, left. Consider $t \in (0, 1)$ and $x \in \text{conv}(\nu)$. Write $z = z(t)$, $z^* = \pi_{\mathcal{M}}(z(t))$, and $x^* = \pi_{\mathcal{M}}(x)$ for short. We have

$$ \angle(\mathbf{n}(z^*), z_1 - z_0) \le \angle(\mathbf{n}(z^*), \mathbf{n}(x^*)) + \angle(\mathbf{n}(x^*), z_1 - z_0). $$

Let us first upper bound $\angle(\mathbf{n}(z^*), \mathbf{n}(x^*))$. Set $r = \delta + \alpha < \text{Reach}(\mathcal{M})$. Since $P \subseteq \mathcal{M}^{\oplus\delta}$, we get that $x, z \in P^{\oplus\alpha} \subseteq \mathcal{M}^{\oplus(\delta+\alpha)} = \mathcal{M}^{\oplus r}$. We know from [35, page 435] that for $r < \text{Reach}(\mathcal{M})$, the projection map $\pi_{\mathcal{M}}$ onto $\mathcal{M}$ is $(\frac{\mathcal{R}}{\mathcal{R}-r})$-Lipschitz for points in $\mathcal{M}^{\oplus r}$. Hence, $\|z^* - x^*\| \le \frac{\mathcal{R}}{\mathcal{R}-\alpha-\delta} \|z - x\|$. Then, using a result in [15] which says that for all $m, m' \in \mathcal{M}$, we have $\angle(\mathbf{n}(m), \mathbf{n}(m')) \le 2 \arcsin \left( \frac{\|m' - m\|}{2\mathcal{R}} \right)$, we obtain that

$$ \angle(\mathbf{n}(z^*), \mathbf{n}(x^*)) \le 2 \arcsin \left( \frac{\|z^* - x^*\|}{2\mathcal{R}} \right) \le 2 \arcsin \left( \frac{\|z - x\|}{2(\mathcal{R} - \alpha - \delta)} \right). $$

Because $z \in V(\nu, P) \cap \bigcap_{p \in \nu} B(p, \alpha)$ and $x \in \text{conv}(\nu)$, we deduce that $\|z - x\| \le \alpha$ and

$$ \angle(\mathbf{n}(z^*), \mathbf{n}(x^*)) \le 2 \arcsin \left( \frac{\alpha}{2(\mathcal{R} - \alpha - \delta)} \right). \qquad (24) $$

Because $N$ is consistently oriented with $\mathcal{M}$, we have that $N \cdot \mathbf{n}(x^*) > 0$ and

$$ \angle(\mathbf{n}(x^*), z_1 - z_0) = \angle(\mathbf{n}(x^*), N) = \angle(\mathbf{T}_{x^*} \mathcal{M}, \text{Aff}(\nu)) \qquad (25) $$
<figure><img src="image_31.png" /><figcaption>Figure 20 Notation for the proof of Lemma E9. The angle $\angle(\mathbf{n}(x^*), z_1 - z_0)$ is in purple.</figcaption></figure>

Using (24) and (25), we obtain that

$$ \angle(\mathbf{n}(z^*), z_1 - z_0) \le \angle(\mathbf{n}(z^*), \mathbf{n}(x^*)) + \angle(\mathbf{n}(x^*), z_1 - z_0) \\ \le 2 \arcsin \left( \frac{\alpha}{2(\mathcal{R} - \alpha - \delta)} \right) + \angle(\mathbf{T}_{x^*} \mathcal{M}, \mathrm{Aff}(\nu)). $$

Since the above inequality is true for all $x$, we get that

$$ \angle(\mathbf{n}(z^*), z_1 - z_0) \le 2 \arcsin \left( \frac{\alpha}{2(\mathcal{R} - \alpha - \delta)} \right) + \min_{x \in \mathrm{conv}(\nu)} \angle(\mathbf{T}_{x^*} \mathcal{M}, \mathrm{Aff}(\nu)) $$

and using our angular hypothesis, we deduce that $\angle(\mathbf{n}(z^*), z_1 - z_0) < \frac{\pi}{2}$ and $\varphi'(t) > 0$ for all $t \in (0, 1)$ as desired.

For the proof of the second item of the lemma, define $z_0$ and $z_1$ as in the proof of the first item and note that the hypothesis $\sigma_0 \prec_M \sigma_1$ implies $z_1 = Z(\sigma_1)$, $z_0 = Z(\sigma_0)$, and $N = \frac{z_1 - z_0}{\|z_1 - z_0\|}$; see Figure 20, right. The first item then implies that

$$ \mathrm{alt}_M(Z(\sigma_0)) < \mathrm{alt}_M(Z(\sigma_1)), $$

which yields the second item.

**Proof of Lemma E7.** Let $\sigma_0, \sigma_1 \in \mathrm{Del}(P, \alpha)$ be two $d$-simplices with a common $(d-1)$-face. If $\sigma_0 \prec_M \sigma_1$, then Lemma E9 implies that $\mathrm{alt}_M(Z(\sigma_0)) < \mathrm{alt}_M(Z(\sigma_1))$. The acyclicity of the relation $\prec_M$ follows, because no function can increase along a cycle.
F Sampling conditions for surfaces in $\mathbb{R}^3$

This appendix contains the proof of Theorem 26 in Section 5. Recall that

$$ \beta_{\varepsilon, \alpha} = -\frac{\varepsilon^2}{2\mathcal{R}} + \sqrt{\alpha^2 + \frac{\varepsilon^4}{4\mathcal{R}^2} - \varepsilon^2}. $$

**Theorem 26.** Let $\mathcal{M}$ be a $\mathbb{C}^2$ surface in $\mathbb{R}^3$ whose reach is at least $\mathcal{R} > 0$. Let $P$ be a finite point set such that $P \subseteq \mathcal{M} \subseteq P^{\oplus\varepsilon}$.

1. For all $\varepsilon, \alpha \ge 0$ that satisfy $\frac{\sqrt{3}\alpha}{\mathcal{R}} < \min\left\{\frac{(\mathcal{R}+\beta_{\varepsilon,\alpha})^2-\mathcal{R}^2-\alpha^2}{2\mathcal{R}\alpha}, \cos(2\arcsin(\frac{\alpha}{\mathcal{R}}))\right\}$,
- the upper and lower complexes of $\mathrm{Del}(P, \alpha)$ relative to $\mathcal{M}$ are triangulations of $\mathcal{M}$;
- NaiveSquash$(P, \alpha)$ returns a triangulation of $\mathcal{M}$.

2. For all $\varepsilon, \alpha \ge 0$ that satisfy in addition $\frac{\sqrt{3}\alpha}{\mathcal{R}} < \sin(\frac{\pi}{4} - 2\arcsin(\frac{\alpha}{\mathcal{R}}))$,
- PracticalSquash$(P, \alpha)$ returns a triangulation of $\mathcal{M}$.

As an intermediate step, we establish Lemma F1.

**Lemma F1.** Let $\mathcal{M}$ be a surface in $\mathbb{R}^3$ and $P \subseteq \mathcal{M}$ a finite point set such that $\mathcal{M} \subseteq P^{\oplus\varepsilon}$. Let $\delta = 0$ and $\beta = \beta_{\varepsilon,\alpha}$. Consider $\varepsilon \ge 0$ and $\alpha \ge 0$ that satisfy the following condition:

$$ \frac{\sqrt{3}\alpha}{\mathcal{R}} < \min \left\{ \frac{(\mathcal{R} + \beta_{\varepsilon,\alpha})^2 - \mathcal{R}^2 - \alpha^2}{2\mathcal{R}\alpha}, \cos\left(2\arcsin\left(\frac{\alpha}{\mathcal{R}}\right)\right) \right\}. \quad (26) $$

Then, the assumptions of Theorem 18 are satisfied. If furthermore

$$ \frac{\sqrt{3}\alpha}{\mathcal{R}} < \sin\left(\frac{\pi}{4} - 2\arcsin\left(\frac{\alpha}{\mathcal{R}}\right)\right), \quad (27) $$

then the assumptions of Corollary 19 are also satisfied.

**Proof.** For short, set $I(\varepsilon) = I(\varepsilon, 0)$. We are going to establish the lemma, adding to Condition (26) the following one:

$$ \varepsilon \le \sqrt{6 - 4\sqrt{2}\mathcal{R}} \quad \text{and} \quad \alpha \in I(\varepsilon) \cap \left[0, \frac{\mathcal{R}}{\sqrt{3}}\right]. \quad (28) $$

Indeed, one can check numerically that the domain of $\varepsilon \ge 0$ and $\alpha \ge 0$ defined by (26) and (28) is exactly the same as the one defined by (26) alone; see Figure 21. Hence, adding (28) to (26) does not change the statement of the lemma, except that under that form, the lemma becomes easier to establish.

Let us first check that the assumptions of Theorem 18 are satisfied. In Theorem 18, we require that $\varepsilon, \delta \ge 0$ satisfy the strict homotopy condition. Since $\delta = 0$, this condition can be rewritten as $\mathcal{R}^2 - \varepsilon^2 \ge (4\sqrt{2} - 5)\mathcal{R}^2$ or equivalently

$$ \varepsilon \le \sqrt{6 - 4\sqrt{2}\mathcal{R}}. $$

We also require that $\alpha \in I(\varepsilon, \delta) \cap \left[\delta, \frac{2(\mathcal{R}-\delta)}{3}\right)$ which can be rewritten as $\alpha \in I(\varepsilon) \cap \left[0, \frac{\mathcal{R}}{\sqrt{3}}\right]$ since $\delta = 0$. Lemma D1 ensures that for $\beta = \beta_{\varepsilon,\alpha}$, we have $\mathcal{M}^{\oplus\beta} \subseteq P^{\oplus\alpha}$, as required in Theorem 18. Suppose that $\tau$ is either an edge or a triangle of $\mathrm{Del}(P, \alpha)$. Then, $\rho(\tau) \le \alpha$ and applying Lemmas 24 and 25, we obtain that for $\alpha \le \frac{\mathcal{R}}{\sqrt{3}}$

$$ \min_{x \in \mathrm{conv}(\tau)} \angle(\mathrm{Aff}(\tau), \mathbf{T}_{\pi_{\mathcal{M}}(x)}\mathcal{M}) \le \min_{a \in \tau} \angle(\mathrm{Aff}(\tau), \mathbf{T}_{\pi_{\mathcal{M}}(a)}\mathcal{M}) \le \arcsin\left(\frac{\sqrt{3}\alpha}{\mathcal{R}}\right). \quad (29) $$
<figure><img src="image_32.png" /><figcaption>■ **Figure 21** Pairs of $(\frac{\epsilon}{R}, \frac{\alpha}{R})$ for which Condition (28) is satisfied (in orange) and for which both Conditions (26) and (28) are satisfied (in blue), for $P \subseteq \mathcal{M} \subseteq P^{\oplus\epsilon}$ and $d = 3$.</figcaption></figure>

Applying Lemma A6, we deduce that for any edge and triangle $\tau \in \mathrm{Del}(P, \alpha)$

$$ \max_{a \in \tau} \angle(\mathrm{Aff}(\tau), \mathbf{T}_{\pi_{\mathcal{M}}(a)}\mathcal{M}) \le \arcsin\left(\frac{\sqrt{3}\alpha}{R}\right) + 2\arcsin\left(\frac{\alpha}{R}\right). \quad (30) $$

Replacing the left side of Condition (5) with the right side of the above inequality, we obtain the stronger condition:

$$ \arcsin\left(\frac{\sqrt{3}\alpha}{R}\right) < \frac{\pi}{2} - 2\arcsin\left(\frac{\alpha}{R}\right). \quad (31) $$

Similarly, when replacing the left side of Conditions (6) and (7) with the right side of (29) and after plugging $\beta = \beta_{\varepsilon,\alpha}$ and $\delta = 0$ on the right side, we get the respectively stronger conditions:

$$ \arcsin\left(\frac{\sqrt{3}\alpha}{R}\right) < \arcsin\left(\frac{(R + \beta_{\varepsilon,\alpha})^2 - R^2 - \alpha^2}{2R\alpha}\right), \quad (32) $$

$$ \arcsin\left(\frac{\sqrt{3}\alpha}{R}\right) < \frac{\pi}{2} - 2\arcsin\left(\frac{\alpha}{2(R - \alpha)}\right). \quad (33) $$

Hence, for $\beta = \beta_{\varepsilon,\alpha}$ and $\delta = 0$, Conditions (5), (6), and (7) are implied by (31), (32), and (33) which can be rewritten as (26) since (33) is redundant with (31).

Second, let us check that if furthermore Condition (27) is satisfied, the assumptions of Corollary 19 are also satisfied. When replacing the left side of Condition (8) with the right side of (30), we get a stronger condition, namely (27). ◀

Thanks to the above lemma, the proof of Theorem 26 is now straightforward.

**Proof of Theorem 26.** Let $\delta = 0$ and $\beta = \beta_{\varepsilon,\alpha}$. By Lemma F1, if 1 holds, then the assumptions of Theorem 18 are met. It can thus be applied to obtain the first part of the theorem. In addition, if 2 holds, the assumptions of Corollary 19 are met. It can thus be applied to obtain the second part of the theorem. ◀
## G The restricted Delaunay complex

Given $\mathcal{M} \subseteq \mathbb{R}^d$ and a finite $P \subseteq \mathbb{R}^d$, we recall that the restricted Delaunay complex is

$$ \mathrm{Del}_{\mathcal{M}}(P) = \{\sigma \subseteq P \mid \sigma \neq \emptyset \text{ and } V(\sigma, P) \cap \mathcal{M} \neq \emptyset\}. $$

The goal of this section is to establish the following theorem.

**Theorem 28.** Let $\mathcal{M}$ be a $\mathbb{C}^2$ surface in $\mathbb{R}^3$ whose reach is at least $\mathcal{R} > 0$. Let $P$ be a finite set such that $P \subseteq \mathcal{M} \subseteq P^{\oplus \epsilon}$ for $0 \le \frac{\epsilon}{\mathcal{R}} \le 0.225$. Under the additional generic assumption that all Voronoi cells of $P$ intersect $\mathcal{M}$ transversally, $\mathrm{Del}_{\mathcal{M}}(P)$ is a triangulation of $\mathcal{M}$.

Instrumental to the proof, we introduce the core Delaunay complex. Given $\mathcal{M} \subseteq \mathbb{R}^d$ and a finite point set $P \subseteq \mathbb{R}^d$, the core Delaunay complex is the collection of $d-1$ simplices in the restricted Delaunay complex together with all their faces:

$$ \mathrm{CoreDel}_{\mathcal{M}}(P) = \mathrm{Cl} \left( \mathrm{Del}_{\mathcal{M}}(P)^{[d-1]} \right). $$

**Proof of Theorem 28.** By Lemma G2, $\mathrm{CoreDel}_{\mathcal{M}}(P)$ triangulates $\mathcal{M}$. By Lemma G3, the restricted Delaunay complex is a pure 2-dimensional simplicial complex. In other words,

$$ \mathrm{Del}_{\mathcal{M}}(P) = \mathrm{CoreDel}_{\mathcal{M}}(P), $$

yielding the result.

In the rest of the section, we establish the two lemmas needed for the proof of Theorem 28.

### G.1 The core Delaunay complex

In this section, we provide conditions under which the core Delaunay complex triangulates $\mathcal{M}$. The first lemma is true for all dimensions $d$ and the second one is true for $d = 3$ and is the one used in the proof of Theorem 28.

**Lemma G1.** Under the assumptions of Theorem 18 and the additional generic assumption that none of the Voronoi vertices of $P$ lie on $\mathcal{M}$, there exists an execution of NaiveSquash($P, \alpha$) that outputs $\mathrm{CoreDel}_{\mathcal{M}}(P)$. Consequently, $\mathrm{CoreDel}_{\mathcal{M}}(P)$ is a triangulation of $\mathcal{M}$.

**Algorithm 5 NonCrossingVertSimp($K$)**

while $G_{\mathcal{M}}(K) \neq \emptyset$ do

if $G_{\mathcal{M}}(K)$ has a sink $\sigma$ whose circumcenter lies above $\mathcal{M}$ then

Collapse $\cap$ UpperFacets$_{\mathcal{M}}(\sigma)$ in $K$;

else if $G_{\mathcal{M}}(K)$ has a source $\sigma$ whose circumcenter lies below $\mathcal{M}$ then

Collapse $\cap$ LowerFacets$_{\mathcal{M}}(\sigma)$ in $K$;

end if

end while

**Algorithm 6 NonCrossingSquash($P, \alpha$)**

$K \leftarrow \mathrm{Del}(P, \alpha)$; NonCrossingVertSimp($K$); return $K$;
**Proof.** Before we start, recall that given a point $x \in \mathbb{R}^d \setminus \text{axis}(\mathcal{M})$,

$$ \text{alt}_{\mathcal{M}}(x) = (x - \pi_{\mathcal{M}}(x)) \cdot \mathbf{n}(\pi_{\mathcal{M}}(x)) $$

is the signed distance of $x$ from $\mathcal{M}$. We shall say that a point $x \in \mathbb{R}^d \setminus \text{axis}(X)$ lies above $\mathcal{M}$ iff $\text{alt}_{\mathcal{M}}(x) \ge 0$, $x$ lies below $\mathcal{M}$ iff $\text{alt}_{\mathcal{M}}(x) \le 0$, and $x$ lies on $\mathcal{M}$ iff $\text{alt}_{\mathcal{M}}(x) = 0$. We also note that the core Delaunay complex can equivalently be defined as

$$ \text{CoreDel}_{\mathcal{M}}(P) = \text{Cl} \left( \{ \nu \in \text{Del}(P)^{[d-1]} \mid V(\nu, P) \cap \mathcal{M} \neq \emptyset \} \right). $$

The proof is done in four steps:

**Step 1:** We show that NonCrossingSquash($P$, $\alpha$) corresponds to one particular execution of NaiveSquash($P$, $\alpha$). For this, we show that when running NonCrossingVertSimp($K$) on $K = \text{Del}(P, \alpha)$, each execution of the while-loop results in one vertical collapse relative to $\mathcal{M}$. This boils down to proving that at least one of the two conditional expressions in NonCrossingVertSimp($K$) evaluates to true whenever $G_{\mathcal{M}}(K) \neq \emptyset$. Suppose that $G_{\mathcal{M}}(K) \neq \emptyset$ and contains a node $\sigma_0$, which, by definition, is a $d$-simplex of $K$. Let $Z(\sigma_0)$ denote the circumcenter of $\sigma_0$. We consider two cases:

(a) Suppose that $Z(\sigma_0)$ lies above $\mathcal{M}$. Because $G_{\mathcal{M}}(K)$ is a directed acyclic graph, we can find a directed path that connects $\sigma_0$ to a sink $\sigma$. By Lemma E9, the map that associates to each node $v$ the quantity $\text{alt}_{\mathcal{M}}(Z(v))$ is increasing along the directed path. Since $Z(\sigma_0)$ lies above $\mathcal{M}$, so does $Z(\sigma)$. Thus, we find a sink whose circumcenter lies above $\mathcal{M}$.

(b) Suppose that $Z(\sigma_0)$ lies below $\mathcal{M}$. Similarly, we find a source $\sigma$ whose circumcenter lies below $\mathcal{M}$.

This shows that at least one of the two conditional expressions in NonCrossingVertSimp($K$) evaluates to true whenever $G_{\mathcal{M}}(K) \neq \emptyset$.

**Step 2:** We show that $\text{CoreDel}_{\mathcal{M}}(P) \subseteq \text{Del}(P, \alpha)$. Indeed, consider a $(d-1)$-simplex $\gamma \in \text{CoreDel}_{\mathcal{M}}(P)$. By definition, there exists a sphere that circumscribes $\gamma$ and whose center lies on $\mathcal{M}$. Because $\mathcal{M} \subseteq P^{\oplus\varepsilon}$, we deduce that the radius of that sphere is $\varepsilon$ at most and $\gamma \in \text{Del}(P, \varepsilon)$. Because $\alpha \in I(\varepsilon, \delta) = [\alpha_{\min}, \alpha_{\max}]$, one can easily check from the definition of $\alpha_{\min}$ in Appendix D.1 that $\varepsilon \le \alpha$ and therefore $\gamma \in \text{Del}(P, \alpha) = K$.

**Step 3:** We show that when running NonCrossingVertSimp($K$) on $K = \text{Del}(P, \alpha)$, we have the loop invariant:

$$ \text{CoreDel}_{\mathcal{M}}(P) \subseteq K \subseteq \text{Del}(P, \alpha). $$

This is true before beginning the while-loop thanks to the previous step. We only need to prove that during an execution of the while-loop, one cannot remove $(d-1)$-simplices of $\text{CoreDel}_{\mathcal{M}}(P)$. We examine in turn each of the two possibilities that may occur:

(a) $G_{\mathcal{M}}(K)$ has a sink $\sigma$ whose circumcenter $Z(\sigma)$ lies above $\mathcal{M}$ and $\bigcap \text{UpperFacets}_{\mathcal{M}}(\sigma)$ is collapsed in $K$. In that case, the set of $(d-1)$-simplices of $K$ that disappear are exactly the upper facets of $\sigma$. Each upper facet $\gamma$ of $\sigma$ is dual to some Voronoi edge $V(\gamma, P)$. Let

$$ \gamma^* = V(\gamma, P) \cap P^{\oplus\alpha} = V(\gamma, P) \cap \bigcap_{p \in \gamma} B(p, \alpha). \qquad (34) $$

$\gamma^*$ is a segment with one endpoint at $Z(\sigma)$. By Lemma E9, the map $x \mapsto \text{alt}_{\mathcal{M}}(x)$ is increasing along the segment $\gamma^*$ as we move $x$ on $\gamma^*$ from $Z(\sigma)$ to the other endpoint. Since
$\text{alt}_M(x) > 0$ for all $x \in \gamma^*$, we deduce that $\gamma^*$ does not intersect $M$. Since $V(\gamma, P) \setminus \gamma^*$ lies outside $P^{\oplus\alpha}$ and $M \subseteq P^{\oplus\alpha}$, we deduce that $V(\gamma, P) \cap M = \emptyset$ and $\gamma \notin \text{CoreDel}_M(P)$.

(b) $G_M(K)$ has a source $\sigma$ whose circumcenter $Z(\sigma)$ lies below $M$ and $\cap$ LowerFacets$_M(\sigma)$ is collapsed in $K$. Similarly, we can show that none of the $(d-1)$-simplices that disappear from $K$ during the collapse of $\tau$ in $K$ belong to $\text{CoreDel}_M(P)$.

**Step 4:** We show that as we run NonCrossingVertSimp(K) on $K = \text{Del}(P, \alpha)$, when the algorithm terminates, then $K = \text{CoreDel}_M(P)$. For this, we are going to prove that during the course of the algorithm, all $(d-1)$-simplices $\gamma \in \text{Del}(P, \alpha) \setminus \text{CoreDel}_M(P)$ disappear at some point. Consider a $(d-1)$-simplex $\gamma \in \text{Del}(P, \alpha) \setminus \text{CoreDel}_M(P)$ and define again $\gamma^*$ as in (34):

$$ \gamma^* = V(\gamma, P) \cap P^{\oplus\alpha} = V(\gamma, P) \cap \bigcap_{p \in \gamma} B(p, \alpha). $$

Note that $\gamma^*$ is connected. Since $\gamma^*$ does not intersect $M$ and is connected, either $\gamma^*$ lies above $M$ or $\gamma^*$ lies below $M$. We are going to charge any $(d-1)$-simplex $\gamma \in \text{Del}(P, \alpha) \setminus \text{CoreDel}_M(P)$ to a $d$-simplex $\sigma \in \text{Del}(P, \alpha)$, considering two cases:

(a) Suppose that $\gamma^*$ lies above $M$. We claim that, in that case, there is a $d$-simplex $\sigma \in \text{Del}(P, \alpha)$ such that $\sigma \subsetneq_M \gamma$ with $Z(\sigma)$ above $M$. Suppose for a contradiction that this is not true and $\gamma$ has no $d$-simplex of $\text{Del}(P, \alpha)$ below it relative to $M$. Then, Lemma E3 implies that $\gamma$ belongs to a lower join of the form $c * \text{conv}(\gamma)$ with $c \in \gamma^*$ lying on the lower skin of $P^{\oplus\alpha}$. Since the lower skin of $P^{\oplus\alpha}$ lies below $M$, we thus get that $c \in \gamma^*$ lies below $M$, yielding a contradiction. In that case, we charge $\gamma$ to $\sigma$.

(b) Suppose that $\gamma^*$ lies below $M$. Similarly, one can show that there is a $d$-simplex $\sigma \in \text{Del}(P, \alpha)$ such that $\gamma \supsetneq_M \sigma$ with $Z(\sigma)$ lying below $M$. In that case, we charge $\gamma$ to $\sigma$.

At the end of Algorithm 5, every $d$-simplex $\sigma$ of $\text{Del}(P, \alpha)$ has been removed at some point. The charging is done in such a way that, when the $d$-simplex $\sigma$ is removed from $K$, so are all $(d-1)$-simplices charged to it. Hence, when Algorithm 5 terminates, $K$ does not contain any $(d-1)$-simplices of $\text{Del}(P, \alpha) \setminus \text{CoreDel}_M(P)$ and therefore $K = \text{CoreDel}_M(P)$.

To summarize, Step 1 guarantees that NonCrossingSquash(P, α) corresponds to one particular execution of NaiveSquash(P, α). Applying Theorem 18, we obtain that it returns a triangulation of $M$, which, by Step 4, is $\text{CoreDel}_M(P)$. ◀

**Lemma G2.** Let $M$ be a $C^2$ surface in $\mathbb{R}^3$ whose reach is at least $R > 0$. Let $P$ be a finite point set such that $P \subseteq M \subseteq P^{\oplus\epsilon}$ for $\frac{\epsilon}{R} \le 0.225$. Assuming no Voronoi vertices of $P$ lie on $M$, $\text{CoreDel}_M(P)$ is a triangulation of $M$.

**Proof.** Let $\epsilon \in [0, 0.225R]$ and note that it is always possible to choose $\alpha \ge 0$ such that the pair $(\frac{\epsilon}{R}, \frac{\alpha}{R})$ belongs to the region depicted in Figure 10a or equivalently such that $\epsilon, \alpha \ge 0$ satisfy 1 in Lemma 26. Let $\delta = 0$ and $\beta = \beta_{\epsilon, \alpha}$. By Lemma F1, the assumptions of Theorem 18 are satisfied. It is thus possible to apply Lemma G1 and deduce that $\text{CoreDel}_M(P)$ is a triangulation of $M$. ◀

## G.2 A pure 2-dimensional simplicial complex when $d = 3$

In this section, we establish conditions under which the restricted Delaunay complex is a pure 2-dimensional complex, when $M$ is a smooth surface in $\mathbb{R}^3$.
**Lemma G3.** Let $\mathcal{M}$ be a $\mathbb{C}^2$ surface in $\mathbb{R}^3$ whose reach is at least $\mathcal{R} > 0$. Let $P$ be a finite point set such that $P \subseteq \mathcal{M} \subseteq P^{\oplus\epsilon}$ for $\epsilon \ge 0$. Let us make the generic assumption that all Voronoi cells of $P$ intersect $\mathcal{M}$ transversally<fnref n="2" />. For all $\epsilon < \mathcal{R}$ that satisfy

$$2 \arcsin \frac{\epsilon}{2\mathcal{R}} + \arcsin \frac{\epsilon}{\mathcal{R}} < \frac{\pi}{2}$$

or, equivalently, for all $\frac{\epsilon}{\mathcal{R}} \le 0.732...$, $\mathrm{Del}_{\mathcal{M}}(P)$ is a pure 2-dimensional simplicial complex.

Before giving the proof, we start with some remarks. Define the restricted Voronoi region of $q \in P$ as the intersection of the Voronoi region of $q$ with $\mathcal{M}$:

$$V_{\mathcal{M}}(q, P) = V(q, P) \cap \mathcal{M} = \{x \in \mathcal{M} \mid \|x - q\| \le \|x - p\|, \text{ for all } p \in P\}.$$

**Remark G4.** $\mathrm{Del}_{\mathcal{M}}(P)$ is the nerve of the collection of restricted Voronoi regions,

$$\mathrm{Del}_{\mathcal{M}}(P) = \mathrm{Nerve}(\{V_{\mathcal{M}}(q, P)\}_{q \in P}).$$

**Remark G5.** If $\mathcal{M} \subseteq P^{\oplus\epsilon}$, then $V_{\mathcal{M}}(p, P) \subseteq B(p, \epsilon)$ for all $p \in P$.

**Proof of Lemma G3.** Our generic assumption implies that no Voronoi vertices of $P$ lie on $\mathcal{M}$ and therefore $\mathrm{Del}_{\mathcal{M}}(P)$ has dimension 2 or less.

<figure><img src="image_33.png" /><figcaption>■ **Figure 22** If the restricted Delaunay complex $\mathrm{Del}_{\mathcal{M}}(P)$ has one vertex $p$ with no coface (left), then the connected component $M_p$ of $\mathcal{M}$ passing through $p$ is contained in the (yellow) Voronoi region $V(p, P)$ (right).</figcaption></figure>

Let us show that any vertex in $\mathrm{Del}_{\mathcal{M}}(P)$ has at least one edge as a coface. Suppose for a contradiction that $\mathrm{Del}_{\mathcal{M}}(P)$ contains a vertex $p \in P$ with no proper coface. Consider the connected component of $\mathcal{M}$ that passes through $p$ and denote it as $M_p$. Because $M_p$ passes through $p \in V(p, P)$ and does not intersect the boundary of $V(p, P)$, we obtain that $M_p \subseteq V(p, P)$; see Figure 22. By Remark G5, $V_{\mathcal{M}}(p, P) \subseteq B(p, \epsilon)$ and therefore

$$M_p \subseteq \mathcal{M} \cap B(p, \epsilon).$$

$M_p$ being a surface without boundary, it cannot be contractible and neither can be $\mathcal{M} \cap B(p, \epsilon)$ which is a surface (possibly with boundary) that contains $M_p$. But, this contradicts Lemma 6 in [9] which states that $\mathcal{M} \cap B(p, \epsilon)$ is contractible, being the non-empty intersection of a set $\mathcal{M}$ with a ball whose radius $\epsilon$ is smaller than the reach of $\mathcal{M}$.

<footnote n="2">² We recall that two smooth submanifolds of $\mathbb{R}^d$ intersect transversally if at every intersection point, the tangent spaces of the two submanifolds span $\mathbb{R}^d$.</footnote>
We now focus on the non-trivial part of the proof, showing that any edge in Del<sub>M</sub>(P) has at least one triangle as a coface. Suppose for a contradiction that Del<sub>M</sub>(P) contains an edge pq with no proper coface. Consider the restricted Voronoi cell of pq:

$$V_M(pq, P) = V_M(p, P) \cap V_M(q, P) = V(pq, P) \cap \mathcal{M}.$$

Recall that the Voronoi cell $V(pq, P)$ is contained in the bisector $\Pi_{pq}$ of p and q and that its relative boundary is defined as its boundary within the hyperplane $\Pi_{pq}$. We note that $pq$ is an edge of Del<sub>M</sub>(P) with no proper coface if and only if M intersects $V(pq, P)$ and does not intersect the relative boundary of $V(pq, P)$.

Our generic assumption implies that M intersects $V(pq, P)$ in a smooth curve (precisely, a 1-dimensional $C^1$ submanifold). Thanks to Remark G5, the curve is contained in $B(p, \varepsilon) \cap B(q, \varepsilon)$ and therefore is bounded. On the other hand, the curve does not intersect the relative boundary of $V(pq, P)$. Thus, the curve consists of one or several loops, i.e. topological circles. Let us choose one of these loops which, by Jordan Theorem, is the boundary of some closed topological disk D within $\Pi_{pq}$; see Figure 23. Note that

$$D \subseteq B(p, \varepsilon) \cap B(q, \varepsilon) \cap \Pi_{pq}. \qquad (35)$$

<figure><img src="image_34.png" /><figcaption>■ Figure 23 If $pq$ is an edge of Del<sub>M</sub>(P) with no proper coface, then M intersects the (yellow) Voronoi cell $V(pq, M)$ in one or several loops (in bold). A key step in the proof of Lemma G3 consists in showing that $y$ belongs to the dome (in dashed green) of $B(p, \varepsilon)$ above $\Pi_{pq}$.</figcaption></figure>

By compactness, there exist a point $x \in D$ that maximizes $d(x, M)$ and a point $y \in M$ such that $\|x - y\| = d(x, M)$. Furthermore, we have

$$\angle(\mathbf{T}_y M, \Pi_{pq}) = 0, \qquad (36)$$

as illustrated in Figure 23. Without loss of generality, we may rename $p$ and $q$ so that $p$ and $y$ both lie on the same side of $\Pi_{pq}$; see Figure 23.

We claim that $y \in B(p, \varepsilon)$. If $y = x$, the claim is trivial since $x \in D \subseteq B(p, \varepsilon) \cap \Pi_{pq}$. If $y \neq x$, consider the half-line with origin at $y$ and passing through $x$. Let $z$ be the point on this half-line whose distance to $y$ is $R$; see Figure 24. By construction, the sphere centered at $z$ with radius $R$ is tangent to $M$ at $y$. Since the reach of $M$ is at least $R$, the open ball $B^\circ(z, R)$ does not intersect $M$. In particular, it does not intersect the relative boundary of D which, by construction, is contained in $M$. Hence, on one hand, $x$ belongs to both
the open disk $B^\circ(z, \mathcal{R}) \cap \Pi_{pq}$ and the topological disk $D$. On the other hand, the open disk $B^\circ(z, \mathcal{R}) \cap \Pi_{pq}$ does not meet the relative boundary of $D$. The only possibility is that $B^\circ(z, \mathcal{R}) \cap \Pi_{pq} \subseteq D$. Combining this inclusion with the inclusion in (35), we get that

$$B^\circ(z, \mathcal{R}) \cap \Pi_{pq} \subseteq B(p, \varepsilon) \cap \Pi_{pq}.$$

Denote by $\Pi_{pq}^+$ the half-space whose boundary is $\Pi_{pq}$ and which contains $p$ (and therefore $y$). Next, we show that the above inclusion still holds when replacing $\Pi_{pq}$ with $\Pi_{pq}^+$. In the context of the proof of the claim, for any ball $B$ (either closed or open), let us call the restriction of $B$ to $\Pi_{pq}^+$ the *dome* of $B$ above $\Pi_{pq}$. Because $\|x - y\| = d(x, \mathcal{M}) \le \|x - p\| \le \varepsilon < \mathcal{R}$, the dome of $B^\circ(z, \mathcal{R})$ above $\Pi_{pq}$ is less than half the ball $B^\circ(z, \mathcal{R})$. Because $\varepsilon < \mathcal{R}$, the dome of $B(p, \varepsilon)$ above $\Pi_{pq}$ must contain the dome of $B^\circ(z, \mathcal{R})$ above $\Pi_{pq}$:

$$B^\circ(z, \mathcal{R}) \cap \Pi_{pq}^+ \subseteq B(p, \varepsilon) \cap \Pi_{pq}^+.$$

Since $y$ lies on the boundary of the dome on the left side, it also belongs to the dome on the right side. This establishes our claim that $y \in B(p, \varepsilon)$.

<figure><img src="image_35.png" /><figcaption>■ **Figure 24** Notation for the proof of the claim in Lemma G3. Note that, although the proof assumes $\varepsilon < \mathcal{R}$, the ball $B(p, \varepsilon)$ is depicted as significantly larger than $B(z, \mathcal{R})$, which might be misleading. This is because the assumptions made within the proof are designed to lead to a contradiction, making the situation impossible to depict while satisfying all of those assumptions.</figcaption></figure>

We are now ready to reach a contradiction. By [17, Corollary 3]:

$$\angle(\mathbf{T}_y\mathcal{M}, \mathbf{T}_p\mathcal{M}) \le 2\arcsin \frac{\varepsilon}{2\mathcal{R}}. \qquad (37)$$

Since $x \in B(p, \varepsilon) \cap B(q, \varepsilon) \ne \emptyset$, we get that $\|p - q\| \le 2\varepsilon$ and by Lemma 24,

$$\angle(q - p, \mathbf{T}_p\mathcal{M}) \le \arcsin \frac{\varepsilon}{\mathcal{R}}. \qquad (38)$$
Since $q-p$ is orthogonal to $\Pi_{pq}$, we get that (36) is equivalent to $\angle(q-p, T_y M) = \frac{\pi}{2}$. This with (37) and (38) gives:

$$2 \arcsin \frac{\varepsilon}{2R} + \arcsin \frac{\varepsilon}{R} \geq \frac{\pi}{2}.$$

But, this contradicts our assumption that

$$2 \arcsin \frac{\varepsilon}{2R} + \arcsin \frac{\varepsilon}{R} < \frac{\pi}{2}.$$

Hence, the assumed situation cannot occur. In other words, if an edge belongs to $\mathrm{Del}_M(P)$, it must have at least one triangle as a coface. ◀