# Delaunay-like Triangulation of Smooth Orientable Submanifolds by L1-Norm Minimization

Dominique Attali, André Lieutier

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

To cite this version:

Dominique Attali, André Lieutier. Delaunay-like Triangulation of Smooth Orientable Submanifolds by L1-Norm Minimization. 2022. hal-03613561

HAL Id: hal-03613561

https://hal.science/hal-03613561

Preprint submitted on 18 Mar 2022

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

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

Distributed under a Creative Commons Attribution 4.0 International License
# Delaunay-like Triangulation of Smooth Orientable Submanifolds by $\ell_1$-Norm Minimization

Dominique Attali*

André Lieutier†

Monday 14th March, 2022

## Abstract

In this paper, we focus on one particular instance of the shape reconstruction problem, in which the shape we wish to reconstruct is an orientable smooth submanifold of the Euclidean space. Assuming we have as input a simplicial complex $K$ that approximates the submanifold (such as the Čech complex or the Rips complex), we recast the reconstruction problem as a $\ell_1$-norm minimization problem in which the optimization variable is a chain of $K$. Providing that $K$ satisfies certain reasonable conditions, we prove that the considered minimization problem has a unique solution which triangulates the submanifold and coincides with the flat Delaunay complex introduced and studied in a companion paper [4]. Since the objective is a weighted $\ell_1$-norm and the contraints are linear, the triangulation process can thus be implemented by linear programming.

## 1 Introduction

In many practical situations, the shape of interest is only known through a finite set of data points. Given these data points as input, it is then natural to try to construct a triangulation of the shape, that is, a set of simplices whose union is homeomorphic to the shape. This paper focuses on one particular instance of this problem, in which the shape we wish to reconstruct is a smooth $d$-dimensional submanifold of the Euclidean space. We show that, when the submanifold is orientable and under appropriate conditions, a triangulation of that submanifold can be expressed as the solution of a weighted $\ell_1$-norm minimization problem under linear constraints. This formulation gives rise to new algorithms for the triangulation of manifolds, in particular when the manifolds have large codimensions.

**Variational formulation of Delaunay triangulation and generalizations.** Our work is based on the observation that when we consider a point cloud $P$ in $\mathbb{R}^d$, its Delaunay complex can be expressed as the solution of a particular $\ell_p$-norm minimization problem. This fact is best explained by lifting the point set $P$ vertically onto the paraboloid $\mathcal{P} \subseteq \mathbb{R}^{d+1}$ whose equation is $x_{d+1} = \sum_{i=1}^d x_i^2$. It is well-known that the Delaunay complex of $P$ is isomorphic to the boundary complex of the lower convex hull of the lifted points $\hat{P}$.

Starting from this equivalence, Chen has observed in [20] that the Delaunay complex of $P$ minimizes the $\ell_p$-norm of the difference between two functions over all triangulations $T$ of $P$. The graph of the first function is the lifted triangulation $\hat{T}$ and the graph of the second one is the paraboloid $\mathcal{P}$. This variational formulation has been successfully exploited in [2, 18, 21] for

<footnote>*Univ. Grenoble Alpes, CNRS, GIPSA-lab, Grenoble, France. Dominique.Attali@grenoble-inp.fr</footnote>

<footnote>†Dassault systèmes, Aix-en-Provence, France. andre.lieutier@3ds.com</footnote>
the generation of *Optimal Delaunay Triangulations*. When $p = 1$, the $\ell_p$-norm associated to $T$ is what we call in this paper the *Delaunay energy of $T$* and, can be interpreted as the volume enclosed between the lifted triangulation $\hat{T}$ and the paraboloid $\mathcal{P}$.

**Our contribution.** While it seems difficult to extend the lifting construction when points of $P$ sample a $d$-dimensional submanifold of $\mathbb{R}^N$, our main result is to show that nonetheless, the induced variational formulation can still be transposed.

Consider a set of points $P$ that sample a $d$-dimensional submanifold $\mathcal{M}$. When searching for a triangulation of $\mathcal{M}$ from $P$, it seems reasonable to restrict the search within a simplicial complex $K$ built from $P$. A first crucial ingredient in our work is to embed the triangulations that one can build using simplices of $K$ inside the vector space formed by simplicial $d$-cycles<fnref n="1" /> of $K$ over the field $\mathbb{R}$. In spirit, this is similar to what is done in the theory of minimal surfaces, when oriented surfaces are considered as particular elements of a much larger set, namely the space of currents [33], that enjoys the nice property of being a vector space. Going back to the case of points in the Euclidean space, if one minimizes the Delaunay energy in the larger set of simplicial chains with real coefficients and under adequate boundary constraints, one obtains a particular chain with coefficients in $\{0, 1\}$ whose simplices, roughly speaking, do not “overlap”. The support of that chain, that is the set of simplices with coefficient 1, coincides with the Delaunay triangulation. The proof is quite direct and relies on the geometric interpretation provided by the lifting construction [22, 39].

We show that when transposing this to the case of points $P$ that sample a $d$-dimensional submanifold $\mathcal{M}$, minimizing the Delaunay energy provides indeed a triangulation of $\mathcal{M}$. The proof requires us to introduce a more elaborate construction, the *Dalloc complex* of $P$, as a tool to describe the solution. The $d$-simplices of that complex possess exactly the property that we need for our analysis. In a companion paper [4] we show that the Dalloc complex indeed provides a triangulation of the manifold, assuming the set of sample points $P$ to be sufficiently dense, safe, and not too noisy. Incidentally, the Dalloc complex coincides with the *flat Delaunay complex* introduced in our companion paper [4] and is akin to the *tangential Delaunay complex* introduced and studied in [6, 7]. When the manifold is sufficiently densely sampled by the data points, all three constructions are locally isomorphic to a (weighted) Delaunay triangulation computed in a local tangent space to the manifold. Intuitively, this indicates that the Delaunay energy should locally reach a minimum for all three constructions and, therefore ought to be also a global minimum. Actually, turning this intuitive reasoning into a correct proof turns out to be more tricky than it appears and is the main purpose of the present paper. In particular, we need to globally compare the Delaunay energy of the cycle carrying the Dalloc complex with that of alternate $d$-cycles, and this requires us to carefully distribute the Delaunay energy along barycentric coordinates (see Section 6).

**Algorithms.** Several authors, with computational topology or topological data analysis motivations, have considered the computation of $\ell_1$-minimum homology representative cycles, [17, 12, 23, 14, 24], generally for integers or integers modulo $p$ coefficients. The celebrated sparsity of $\ell_1$-minima manifests itself in this context by the fact that the support of such minima is sparse, in other words it is non-zero only on a small subset of simplices of $K$.

Note that an alternative algorithm to the one proposed in this paper could be to compute a triangulation of $\mathcal{M}$ by returning such a minimal sparse representative. Indeed, when the data points sample sufficiently densely and accurately the manifold compared to the reach of the manifold, one could – in theory – take either the Čech complex or the Vietoris-Rips complex as the

<footnote n="1">¹Or relative $d$-cycles when the considered domain has a boundary.</footnote>
complex $K$, since it is known that by choosing the scale parameter of these complexes carefully, they are guaranteed to have the same homotopy type as $\mathcal{M}$ [16, 15, 5, 37, 31]. Recall that, when $\mathcal{M}$ is orientable and connected, its $d$-homology group with real coefficients is one-dimensional, and a normalized generator of it is called the *manifold fundamental class*. Hence, when $K$ and $\mathcal{M}$ are homotopy equivalent, the $d$-homology group of $K$ is also one-dimensional. It follows that extracting any non-boundary cycle of $K$ (using standard linear algebra operations on the boundary operators $\partial_d$ and $\partial_{d+1}$ of $K$) provides a $d$-cycle $\gamma_0$ which is, up to a multiplicative constant, a representative of a generator of the fundamental class of $\mathcal{M}$. An alternate algorithm could then search, among chains homologous to $\gamma_0$, for the one with the minimal Delaunay energy. The solution of the corresponding linear optimization problem would then be a chain which carries the Delloc complex. While elegant in theory, the size required for the $(d+1)$-skeleton of the Čech or Vietoris-Rips complex may be prohibitive in practice.

Instead, we describe a procedure that only requires the milder condition on $K$ to be a simplicial complex large enough to contain the Delloc complex, at the cost of adding a certain form of normalization constraint. For the purpose of the proof, it is convenient to first consider a rather artificial problem, where, besides the sample $P$, the manifold $\mathcal{M}$ is known. In Section 8, we show how to turn this problem into a more realistic one that takes as input only the sample of the unknown manifold, and is correct assuming that reasonable sampling conditions hold. While we do not yet explore practical efficient algorithms in this paper, the minimization of a $\ell_1$-norm under linear constraints in $\mathbb{R}^n$, where $n$ is the number of $d$-simplices in the considered simplicial complex $K$, can be turned into a linear optimization problem in the standard form through slack variables, and can be addressed by standard linear programming techniques such as the simplex algorithm.

# 2 Preliminaries

In this section, we review the necessary background and explain some of our terms.

## 2.1 Subsets and submanifolds

Given a subset $A \subseteq \mathbb{R}^N$, the affine space spanned by $A$ is denoted by $\text{aff } A$ and the convex hull of $A$ by $\text{conv } A$. The *medial axis* of $A$, denoted as $\text{axis}(A)$, is the set of points in $\mathbb{R}^N$ that have at least two closest points in $A$. By definition, the *projection map* $\pi_A : \mathbb{R}^N \setminus \text{axis}(A) \to A$ associates to each point $x$ its unique closest point in $A$. The *reach* of $A$ is the infimum of distances between $A$ and its medial axis, and is denoted as $\text{reach } A$. By definition, the projection map $\pi_A$ is well-defined on every subset of $\mathbb{R}^N$ that does not intersect the medial axis of $A$. In particular, recalling that the *r-tubular neighborhood* of $A$ is the set of points $A^{\oplus r} = \{x \in \mathbb{R}^N \mid d(x, A) \le r\}$, the projection map $\pi_A$ is well-defined on every $r$-tubular neighborhood of $A$ with $r < \text{reach } A$. We denote the ball centered at $x \in \mathbb{R}^N$ and with radius $\rho \in \mathbb{R}$ by $B(x, \rho)$. For short, we say that a subset $\sigma \subseteq \mathbb{R}^N$ is $\rho$-small if it can be enclosed in a ball of radius $\rho$.

Throughout the paper, $\mathcal{M}$ designates a compact connected orientable $C^2$ $d$-dimensional submanifold of $\mathbb{R}^N$ for $d < N$. For any point $m \in \mathcal{M}$, the tangent plane to $m$ at $\mathcal{M}$ is denoted as $\text{T}_m\mathcal{M}$. Because $\mathcal{M}$ is $C^2$ and therefore $C^{1,1}$, the reach of $\mathcal{M}$ is positive [27]. We let $\mathcal{R}$ be a fixed finite constant such that $0 < \mathcal{R} \le \text{reach } \mathcal{M}$.

## 2.2 Simplicial complexes

In this section, we review some background notation on simplicial complexes [35]. We also introduce the concept of faithful reconstruction which encapsulates what we mean by a “desirable” approximation of a manifold.
All simplices and simplicial complexes that we consider in the paper are abstract. Each abstract simplex $\sigma \subseteq \mathbb{R}^N$ is naturally associated to a geometric simplex defined as $\text{conv } \sigma$. The dimension of $\text{conv } \sigma$ is the dimension of the affine space $\text{aff } \sigma$, and cannot be larger than the dimension of the abstract simplex $\sigma$. When the dimension of the geometric simplex $\text{conv } \sigma$ coincides with that of the abstract simplex $\sigma$, we say that $\sigma$ is non-degenerate. Equivalently, the vertices of $\sigma$ form an affinely independent set of points. The star of $x \in \mathbb{R}^N$ in a simplicial complex $K$ is $\text{St}(x, K) = \{\sigma \in K | x \in \text{conv } \sigma\}$.

Given a set of simplices $\Sigma$ with vertices in $\mathbb{R}^N$ (not necessarily forming a simplicial complex), we let $\Sigma^{[d]}$ designate the $d$-simplices of $\Sigma$. We define the shadow of $\Sigma$ as the subset of $\mathbb{R}^N$ covered by the relative interior of the geometric simplices associated to the abstract simplices in $\Sigma$, $|\Sigma| = \bigcup_{\sigma \in \Sigma} \text{relint}(\text{conv } \sigma)$. We shall say that $\Sigma$ is geometrically realized (or embedded) if (1) $\dim(\sigma) = \dim(\text{aff } \sigma)$ for all $\sigma \in \Sigma$, and (2) $\text{conv}(\alpha \cap \beta) = \text{conv } \alpha \cap \text{conv } \beta$ for all $\alpha, \beta \in \Sigma$.

**Definition 1** (Faithful reconstruction). Consider a subset $A \subseteq \mathbb{R}^N$ whose reach is positive, and a simplicial complex $K$ with a vertex set in $\mathbb{R}^N$. We say that $K$ reconstructs $A$ faithfully (or is a faithful reconstruction of $A$) if the following three conditions hold:

**Embedding:** $K$ is geometrically realized;

**Closeness:** $|K|$ is contained in the $r$-tubular neighborhood of $A$ for some $0 \le r < \text{reach } A$;

**Homeomorphism:** The restriction of $\pi_A : \mathbb{R}^N \setminus \text{axis}(A) \to A$ to $|K|$ is a homeomorphism.

## 2.3 Height, circumsphere and smallest enclosing ball

The height of a simplex $\sigma$ is height($\sigma$) = $\min_{v \in \sigma} d(v, \text{aff}(\sigma \setminus \{v\}))$. The height of $\sigma$ vanishes if and only if $\sigma$ is degenerate. If $\sigma$ is non-degenerate, then, letting $d = \dim \sigma = \dim \text{aff } \sigma$, there exists a unique ($d-1$)-sphere that circumscribes $\sigma$ and therefore at least one ($N-1$)-sphere that circumscribes $\sigma$. Hence, if $\sigma$ is non-degenerate, it makes sense to define $S(\sigma)$ as the smallest ($N-1$)-sphere that circumscribes $\sigma$. Let $Z(\sigma)$ and $R(\sigma)$ denote the center and radius of $S(\sigma)$, respectively. Let $c_\sigma$ and $r_\sigma$ denote the center and radius of the smallest $N$-ball enclosing $\sigma$, respectively. Clearly, $r_\sigma \le R(\sigma)$ and both $c_\sigma$ and $Z(\sigma)$ belong to $\text{aff } \sigma$. The intersection $S(\sigma) \cap \text{aff } \sigma$ is a ($d-1$)-sphere which is the unique ($d-1$)-sphere circumscribing $\sigma$ in $\text{aff } \sigma$.

## 2.4 Delaunay complexes

Consider a finite point set $Q \subseteq \mathbb{R}^N$. We say that $\sigma \subseteq Q$ is a Delaunay simplex of $Q$ if there exists an ($N-1$)-sphere $S$ that circumscribes $\sigma$ and such that no points of $Q$ belong to the open ball whose boundary is $S$. The set of Delaunay simplices form a simplicial complex called the Delaunay complex of $Q$ and denoted as $\text{Del}(Q)$.

**Definition 2** (General position). Let $d = \dim(\text{aff } Q)$. We say that $Q \subseteq \mathbb{R}^N$ is in general position if no $d+2$ points of $Q$ lie on a common ($d-1$)-dimensional sphere.

**Lemma 3.** When $Q$ is in general position, $\text{Del}(Q)$ is geometrically realized.

Let us recall a famous result which says that building a Delaunay complex in $\mathbb{R}^N$ is topologically equivalent to building a lower convex hull in $\mathbb{R}^{N+1}$. For simplicity, we shall identify each point $x \in \mathbb{R}^N$ with a point $(x, 0)$ in $\mathbb{R}^{N+1}$. Consider the paraboloid $\mathcal{P} \subseteq \mathbb{R}^{N+1}$ defined as the graph of the function $\|\cdot\|^2 : \mathbb{R}^N \to \mathbb{R}$, $x \mapsto \|x\|^2$, where $\|\cdot\|$ designates the Euclidean norm. For each point $x \in \mathbb{R}^N$, its vertical projection onto $\mathcal{P}$ is the point $\hat{x} = (x, \|x\|^2) \in \mathbb{R}^{N+1}$, which we call the *lifted image* of $x$. Similarly, the *lifted image* of $Q \subseteq \mathbb{R}^N$ is $\hat{Q} = \{\hat{q} | q \in Q\}$. Recall that the lower convex hull of $\hat{Q}$ is the portion of $\text{conv } \hat{Q}$ visible to a viewer standing at $x_{d+1} = -\infty$. A classical result says that $\sigma$ is a Delaunay simplex of $Q$ if and only if $\text{conv } \hat{\sigma}$ is contained in the lower convex hull of $\hat{Q}$ [26].
## 2.5 Delaunay energy for triangulations

We recall that a triangulation $T$ of $Q$ designates a simplicial complex with vertex set $Q$ which is geometrically realized and whose shadow covers $\text{conv } Q$. It is well-known that the Delaunay complex of $Q$ optimizes many functionals over the set of triangulations of $Q$ [11, 38, 36], one of them being the Delaunay energy that we shall now define [19]. Let $d = \text{dim}(\text{aff } Q)$. Given a triangulation $T$ of $Q$, the Delaunay energy $E_{\text{del}}(T)$ of $T$ is defined as the $(d+1)$-volume between the $d$-manifold $|\hat{T}| = \bigcup_{\sigma \in T} \text{conv } \hat{\sigma}$ and the paraboloid $\mathcal{P}$. Let us derive an expression for this $(d+1)$-volume. Consider a point $x \in \text{conv } Q$. By construction, $x$ belongs to at least one geometric $d$-simplex $\text{conv } \sigma$ for some $\sigma \in T$. Erect an infinite vertical half-line going up from $x$. This half-line intersects the paraboloid $\mathcal{P}$ at point $\hat{x}$ and the lifted geometric $d$-simplex $\text{conv } \hat{\sigma}$ at point $x_{\sigma}^*$. We have

$$E_{\text{del}}(T) = \sum_{\sigma} \int_{x \in \text{conv } \sigma} \|\hat{x} - x_{\sigma}^*\| dx.$$

**Theorem 4** (Delaunay complex by a variational approach). When $Q$ is in general position, the triangulation of $Q$ that minimizes the Delaunay energy is unique and equals $\text{Del}(Q)$.

Theorem 4 is a direct consequence of the lifting construction [36, 20].

## 2.6 Delaunay weight

To each non-degenerate $d$-dimensional abstract simplex $\alpha \in \mathbb{R}^N$ we assign a non-negative real number that we call the Delaunay weight of $\alpha$. The reasons for this will become clear shortly. Let $\alpha \subseteq \mathbb{R}^N$ be a non-degenerate abstract simplex. We recall that the power distance of point $x \in \mathbb{R}^N$ from $S(\alpha)$ is $\text{Power}_\alpha(x) = \|x - Z(\alpha)\|^2 - R(\alpha)^2$.

**Definition 5** (Delaunay weight). The Delaunay weight of a non-degenerate simplex $\alpha$ is:

$$\omega(\alpha) = - \int_{x \in \text{conv } \alpha} \text{Power}_{\alpha}(x) dx.$$

Easy computations show that $\text{Power}_\alpha(x) = -\|\hat{x} - x_\alpha^*\|$; see for instance [25]. Hence, if $d = \text{dim}(\alpha)$, we see that $\omega(\alpha)$ represents the $(d+1)$-volume between the lifted geometric simplex $\text{conv } \hat{\sigma}$ and the paraboloid $\mathcal{P}$. Therefore the Delaunay energy can be expressed as $E_{\text{del}}(T) = \sum_\alpha \omega(\alpha)$, where $\alpha$ ranges over all $d$-simplices of $T$. Below, we give a closed expression for the Delaunay weight due to Chen and Holst in [18]. Writing $\text{vol}(\alpha)$ for the $d$-dimensional volume of $\text{conv } \alpha$, we have:

**Lemma 6** ([18]). The weight of the non-degenerate $d$-simplex $\alpha = \{a_0, \dots, a_d\}$ is

$$\omega(\alpha) = \frac{1}{(d+1)(d+2)} \text{vol}(\alpha) \left[ \sum_{0 \le i < j \le d} \|a_i - a_j\|^2 \right].$$

For completeness, we provide a proof of Lemma 6 in Appendix A. The expression of the Delaunay weight given in Lemma 6 shows that two simplices that are isometric have the same Delaunay weight. Hence, a Delaunay energy can be straightforwardly associated to any “soup” $\Sigma$ of $d$-simplices living in $\mathbb{R}^N$ by setting $E(\Sigma) = \sum_{\sigma \in \Sigma} \omega(\sigma)$. It is then tempting to ask what would happen if one minimizes this energy when the vertices of $\Sigma$ sample a $d$-manifold.
## 2.7 Chains and weighted norms

In this section, we recall some standard notation concerning chains. Chains play an important role in this work as they provide a tool to embed the discrete set of candidate solutions (faithful reconstructions of $\mathcal{M}$) into a larger continuous space. Consider an abstract simplicial complex $K$ and assume that each simplex $\sigma$ in $K$ is given an arbitrary orientation. A $d$-chain of $K$ with coefficients in $\mathbb{R}$ is a formal sum $\gamma = \sum_{\sigma} \gamma(\sigma)\sigma$, where $\sigma$ ranges over all $d$-simplices of $K$ and $\gamma(\sigma) \in \mathbb{R}$ is the value (or the coordinate) assigned to the oriented $d$-simplex $\sigma$. The set of such $d$-chains is a vector space denoted by $C_d(K, \mathbb{R})$. Recall that the $l_1$-norm of $\gamma$ is defined by $\|\gamma\|_1 = \sum_{\sigma} |\gamma(\sigma)|$. Let $W$ be a weight function which assigns a non-negative weight $W(\sigma)$ to each $d$-simplex $\sigma$ of $K$. The $W$-weighted $l_1$-norm of $\gamma$ is expressed as $\|\gamma\|_{1,W} = \sum_{\sigma} W(\sigma)|\gamma(\sigma)|$. We shall say that a chain $\gamma$ is carried by a subcomplex $D$ of $K$ if $\gamma$ has value 0 on every simplex that is not in $D$. The support of $\gamma$ is the set of simplices on which $\gamma$ has a non-zero value. It is denoted by $\text{Supp } \gamma$.

# 3 Deloc complex

Given a finite set of points $P$ in $\mathbb{R}^N$, a dimension $d$, and a scale parameter $\rho$, we introduce a construction which we call the $d$-dimensional Deloc complex of $P$ at scale $\rho$. First, we define the property for a simplex to be deloc.

**Definition 7 (Deloc complex).** We say that a simplex $\sigma$ is *deloc* in $P$ at scale $\rho$ if $\sigma \in \text{Del}(\pi_{\text{aff}}\sigma(P \cap B(c_\sigma, \rho)))$. The $d$-dimensional *Deloc complex* of $P$ at scale $\rho$ is the set of $d$-simplices that are deloc in $P$ at scale $\rho$ together with all their faces, and is denoted by $\text{Deloc}_d(P, \rho)$.

We now state a theorem which establishes conditions under which the Deloc complex is a faithful reconstruction of $\mathcal{M}$. The theorem can be seen as a corollary of the main theorem that we establish in the companion paper [4]. We need some notations and definitions.

**Definition 8 (Dense, accurate, and separated).** We say that $P$ is an $\varepsilon$-dense sample of $\mathcal{M}$ if for every point $m \in \mathcal{M}$, there is a point $p \in P$ with $\|p - m\| \le \varepsilon$ or, equivalently, if $\mathcal{M} \subseteq P^{\oplus\varepsilon}$. We say that $P$ is a $\delta$-accurate sample of $\mathcal{M}$ if for every point $p \in P$, there is a point $m \in \mathcal{M}$ with $\|p - m\| \le \delta$ or, equivalently, if $P \subseteq \mathcal{M}^{\oplus\delta}$. Let separation $(P) = \min_{p \ne q \in P} \|p - q\|$.

We stress that our definition of a protected simplex differs slightly from the one in [8, 7].

**Definition 9 (Protection).** We say that a non-degenerate simplex $\sigma \subseteq \mathbb{R}^N$ is $\zeta$-protected with respect to $Q \subseteq \mathbb{R}^N$ if for all $q \in Q \setminus \sigma$, we have $d(q, S(\sigma)) > \zeta$.

Let $\mathcal{H}(\sigma) = \{\mathbf{T}_m\mathcal{M} \mid m \in \pi_{\mathcal{M}}(\text{conv } \sigma)\} \cup \{\text{aff } \sigma\}$, and $\Theta(\sigma) = \max_{H_0, H_1 \in \mathcal{H}(\sigma)} \angle(H_0, H_1)$. To the pair $(P, \rho)$ we now associate three quantities that describe the quality of $P$ at scale $\rho$:

* height$(P, \rho) = \min_{\sigma} \text{height}(\sigma)$, where the minimum is over all $\rho$-small $d$-simplices $\sigma \subseteq P$;

* $\Theta(P, \rho) = \max_{\sigma} \Theta(\sigma)$, where $\sigma$ ranges over all $\rho$-small $d$-simplices of $P$;

* protection$(P, \rho) = \min_{\sigma} \min_{q} d(q, S(\sigma))$, where the minima are over all $\rho$-small $d$-simplices $\sigma \subseteq P$ and all points $q \in \pi_{\text{aff}}\sigma(P \cap B(c_{\sigma}, \rho)) \setminus \sigma$.

**Theorem 10 (Faithful reconstruction by a geometric approach).** Let $\varepsilon, \delta, \rho, \theta \ge 0$ and set $A = 4\delta\theta + 4\rho\theta^2$. Assume that $\theta \le \frac{\pi}{6}$, $\delta \le \varepsilon$ and $16\varepsilon \le \rho < \frac{R}{4}$. Suppose that $P$ is a $\delta$-accurate $\varepsilon$-dense sample of $\mathcal{M}$ that satisfies the following safety conditions:

1. $\Theta(P, \rho) \le \theta - 2 \arcsin\left(\frac{\rho+\delta}{R}\right)$;
2. separation($P$) > $2A + 6\delta + \frac{2\rho^2}{R}$;

3. height($P, \rho$) > 0 and protection($P, 3\rho$) > $2A \left(1 + \frac{4d\epsilon}{\text{height}(P, \rho)}\right)$.

Then $D = \text{Deloc}_d(P, \rho)$ enjoys the following properties:

**Faithful reconstruction:** $D$ is a faithful reconstruction of $M$;

**Circumradii:** For all $d$-simplices $\sigma \in D$, we have that $R(\sigma) \le \epsilon$;

**Local behaviour:** For all $x \in |D|$, $\pi_{T_x M}(\text{St}(x, D))$ is geometrically realized.

Incidentally, under the assumption of Theorem 10, $\text{Deloc}_d(P, \rho)$ coincides $\text{FlatDel}_M(P, \rho)$, the complex introduced and studied in the companion paper [4]. Since all the results in this paper are based on the deloc property, we find it more enlightening to formulate the results of this paper using the Deloc complex. We recall that the safety conditions can be met in practice by assuming $P$ to be a sample of $M$ sufficiently dense and sufficiently accurate, and then perturbing the point set $P$ as explained in the companion paper [4].

**Remark 11.** It is easy to see that if $2R(\sigma) \le \rho$, then a deloc simplex $\sigma$ in $P$ at scale $\rho$ is also a *Gabriel simplex* of $P$, by which we mean that its smallest circumsphere $S(\sigma)$ does not enclose any point of $P$ in its interior. In particular, if $2R(\sigma) \le \rho$, the deloc simplex $\sigma$ is a *Delaunay simplex* of $P$. Hence, under the assumptions of Theorem 10, we have the inclusion $\text{Deloc}_d(P, \rho) \subseteq \text{Del}(P)$.

# 4 Statement of main result

In this section, we state our main result. Hereafter, we suppose that $K$ is a simplicial complex whose vertices are the points of $P$.

**Orienting and signing.** We also assume that $M$ together with all $d$-simplices of $K$ have received an (arbitrary) orientation. For each $d$-simplex $\alpha \in K$ such that $\Theta(\alpha) < \frac{\pi}{2}$, we define the sign of $\alpha$ with respect to $M$ as follows:

$$ \text{sign}_{\mathcal{M}}(\alpha) = \begin{cases} 1 & \text{if the orientation of } \alpha \text{ is consistent with that of } \mathcal{M}, \\ -1 & \text{otherwise.} \end{cases} $$

We refer the reader to Appendix F for a formal definition of consistency and more details. We associate to any subcomplex $D \subseteq K$ the $d$-chain $\gamma_D$ of $K$ whose coordinates are:

$$ \gamma_D(\alpha) = \begin{cases} \text{sign}_{\mathcal{M}}(\alpha) & \text{if } \alpha \in D^{[d]}, \\ 0 & \text{otherwise.} \end{cases} $$

**Lemma 12.** If $D$ is a faithful reconstruction of $M$ and, for all $x \in |D|$, $\pi_{T_x M}(\text{St}(x, D))$ is geometrically realized, then $\gamma_D$ is a cycle. In particular, this is true when $D = \text{Deloc}_d(P, \rho)$ under the assumptions of Theorem 10.

**Proof.** Since $D$ is a faithful reconstruction of $M$, $|D|$ is a $d$-manifold. Hence, each $(d-1)$-simplex $\tau \in D$ has exactly two $d$-cofaces $\sigma_1$ and $\sigma_2$. Consider a point $x$ in the relative interior of $\tau$ and its projection $m = \pi_M(x)$ onto $M$. The set $\pi_{T_x M}(\text{St}(x, D))$ possesses exactly two $d$-simplices $\sigma'_1 = \pi_{T_m M}(\sigma_1)$ and $\sigma'_2 = \pi_{T_m M}(\sigma_2)$, and one $(d-1)$-simplex $\tau' = \pi_{T_m M}(\tau)$. As we project the $d$-simplex $\sigma_i = [u_0, \dots, u_d]$, we preserve the vertex ordering, that is, we let $\sigma'_i = [\pi_{T_m M}(u_0), \pi_{T_m M}(u_1), \dots, \pi_{T_m M}(u_d)]$. It follows from Appendix F that each $d$-simplex $\sigma'_i$ in $\text{Star}_{P,M}(m, \rho)$ has the same orientation with respect to $T_m M$ than that of $\sigma_i$ with respect to
M. Let $s_i = \text{sign}_{T_m M}(\sigma'_i) = \text{sign}_M(\sigma_i)$. Since the two geometric $d$-cofaces $\text{conv } \sigma'_1$ and $\text{conv } \sigma'_2$ of $\text{conv } \tau'$ have disjoint interiors, we obtain that $\partial(s_1\sigma'_1 + s_2\sigma'_2)$ is 0 on $\tau'$, and consequently $\partial(s_1\sigma_1 + s_2\sigma_2)$ is 0 on $\tau$. $\square$

**Least $\ell_1$-norm problem.** We define the *Delaunay energy* of the chain $\gamma \in C_d(K, \mathbb{R})$ to be its $\omega$-weighted $\ell_1$-norm:

$$E_{\text{del}}(\gamma) = \|\gamma\|_{1,\omega} = \sum_{\alpha} \omega(\alpha) \cdot |\gamma(\alpha)| = \sum_{\alpha} \left( \int_{x \in \text{conv } \alpha} -\text{Power}_{\alpha}(x) \, dx \right) \cdot |\gamma(\alpha)|, \quad (1)$$

where $\omega$ is the Delaunay weight function defined in Section 2 and $\alpha$ ranges over all $d$-simplices of $K$. Given a $d$-manifold $\mathcal{A}$, a point $a \in \mathcal{A}$, a set of simplices $\Sigma \subseteq K$ and a $d$-chain $\gamma$ of $K$, we also introduce the real number:

$$\text{load}_{a, \mathcal{A}, \Sigma}(\gamma) = \sum_{\sigma \in \Sigma^{[d]}} \gamma(\sigma) \text{sign}_{\mathcal{A}}(\sigma) \mathbf{1}_{\pi_{\mathcal{A}}(\text{conv } \sigma)}(a)$$

and call it the *load* of $\gamma$ on $\mathcal{A}$ at $a$ restricted to $\Sigma$. Letting $m_0$ be a generic$^2$ point on $M$, we are interested in the following optimization problem over the set of chains in $C_d(K, \mathbb{R})$:

$$
\begin{array}{ll}
\underset{\gamma}{\text{minimize}} & E_{\text{del}}(\gamma) \\
\text{subject to} & \partial\gamma = 0, \qquad (\star) \\
& \text{load}_{m_0, \mathcal{M}, K}(\gamma) = 1
\end{array}
$$

Problem $(\star)$ is a convex optimization problem and as such is solvable by linear programming. More precisely, it is a least-norm problem whose constraint functions $\partial$ and $\text{load}_{m_0, \mathcal{M}, K}$ are clearly linear. The first constraint $\partial\gamma = 0$ expresses the fact that we are searching for $d$-cycles. The second constraint $\text{load}_{m_0, \mathcal{M}, K}(\gamma) = 1$ can be thought of as a kind of normalization of $\gamma$. It forbids the zero chain to belong to the feasible set and we shall see that, under the assumptions of our main theorem, it forces the solution to take its coordinate values in $\{0, +1, -1\}$.

In Problem $(\star)$, besides the simplicial complex $K$ that one can build from $P$, the knowledge of the manifold $M$ seems to be required as well for expressing the normalization constraint. In Section 8.1, we discuss how to transform Problem $(\star)$ into an equivalent problem that does not refer to $M$ anymore.

**Main theorem.** In our main theorem (see below), there is a constant $\Omega(\Delta_d)$ that depends only upon the dimension $d$ and whose definition is given in the proof of Lemma 20.

**Theorem 13** (Faithful reconstruction by a variational approach). Let $\varepsilon$, $\delta$, $\rho$ and $\theta$ be non-negative real-numbers such that $\theta \le \frac{\pi}{6}$, $\delta \le \varepsilon$ and $16\varepsilon \le \rho < \frac{\mathbb{R}}{4}$. Set

$$J = \frac{(\mathcal{R} + \rho)^d}{(\mathcal{R} - \rho)^d (\cos \theta)^{\min\{d, N-d\}}} - 1 \quad \text{and} \quad A = 4\delta\theta + 4\rho\theta^2.$$

Let $\zeta = \text{protection}(P, 3\rho)$ and suppose that $P$ is a $\delta$-accurate $\varepsilon$-dense sample of $M$ that satisfies the following safety conditions:

$$1. \quad \Theta(P, \rho) \le \theta - 2 \arcsin \left( \frac{\rho + \delta}{\mathcal{R}} \right).$$

<footnote>$^2$Generic in the sense that it is not in the projection on $M$ of the convex hull of any $(d-1)$-simplex of $K$.</footnote>
2. separation($P$) > $2A + 6\delta + \frac{3\rho^2}{R}$;

3. height($P, \rho$) > 0 and $\zeta > 2A \left(1 + \frac{4d\varepsilon}{\text{height}(P, \rho)}\right)$;

4. $\zeta^2 + \zeta$ separation($P$) > $10\rho \sin\theta(\varepsilon + \rho \sin\theta)$;

5. $J\rho^2 < (1+J)^{-1} \frac{(d+2)(d-1)!}{4} (\zeta^2 + \zeta \text{ separation}(P)) \Omega(\Delta_d)$.

Suppose that $\text{Dello}_d(P, \rho) \subseteq K$ and that the $d$-simplices of $K$ are $\rho$-small. Then Problem (⋆) has a unique solution which is $\gamma_{\text{Dello}_d(P, \rho)}$. The support of that solution together with all its faces coincides with $\text{Dello}_d(P, \rho)$ and is a faithful reconstruction of $M$.

One may ask about the feasability of realizing the assumptions of Theorem 13. While assuming the sample to be $\varepsilon$-dense and $\delta$-accurate seems realistic enough (perhaps after filtering outliers), the safety conditions seem less likely to be satisfied by natural data. In Section 8.2, we show how to apply Moser Tardos Algorithm ([34] and [7, Section 5.3.4]) as a perturbation scheme to enforce the safety conditions of Theorem 13.

**Choosing the simplicial complex K.** Recall that the Čech complex of $P$ at scale $\rho$, denoted as $C(P, \rho)$, is the set of simplices of $P$ that are $\rho$-small. The Rips complex of $P$ at scale $\rho$, denoted as $\mathcal{R}(P, \rho)$, is a more easily-computed version which consists of all simplices of $P$ with diameter at most $2\rho$. We stress that our main theorem applies to any simplicial complex $K$ such that $\text{Dello}_d(P, \rho) \subseteq K \subseteq C(P, \rho)$. Since $C(P, r) \subseteq \mathcal{R}(P, r) \subseteq C(P, \sqrt{2}r)$ and $\text{Dello}_d(P, \rho) \subseteq C(P, \varepsilon)$, it applies to any $K = \mathcal{R}(P, r)$ with $\varepsilon \le r \le \frac{\rho}{\sqrt{2}}$. This choice of $K$ is well-suited for applications in high dimensional spaces. Observe that under the assumptions of Theorem 13, $\text{Dello}_d(P, \rho) \subseteq \text{Del}(P) \cap C(P, \varepsilon)$ (see Remark 11) and choosing $K = \text{Del}(P) \cap C(P, r)$ for any $\varepsilon \le r \le \rho$ may then be more suited for applications in low dimensional spaces.

# 5 Technical lemma

The proof of our main theorem relies on a technical lemma which we now state and prove.

**Lemma 14.** Let $\mathcal{D} \subseteq \mathbb{R}^N$ be a $d$-manifold (with or without boundary) and $K$ a simplicial complex with vertices in $\mathbb{R}^N$. Assume that there is a map $\varphi : |K| \to \mathcal{D}$. Suppose that for each $d$-simplex $\alpha \in K$, we have two positive weights $W(\alpha) \ge W_{\min}(\alpha)$ and that there exists a map $f : \mathcal{D} \to \mathbb{R}$ such that $W_{\min}(\alpha) = \int_{\varphi(\text{conv } \alpha)} f$. Consider the $d$-chain $\gamma_{\min}$ on $K$ defined by

$$ \gamma_{\min}(\alpha) = \begin{cases} 1 & \text{if } W_{\min}(\alpha) = W(\alpha), \\ 0 & \text{otherwise.} \end{cases} $$

Suppose that $\sum_{\alpha \in K^{[d]}} \gamma_{\min}(\alpha) \mathbf{1}_{\varphi(\text{conv } \alpha)}(x) = 1$, for almost all $x \in \mathcal{D}$. Then the $l_1$-like norm $\|\gamma\|_{1,W}$ attains its minimum over all $d$-chains $\gamma$ such that

$$ \sum_{\alpha \in K^{[d]}} \gamma(\alpha) \mathbf{1}_{\varphi(\text{conv } \alpha)}(x) = 1, \quad \text{for almost all } x \in \mathcal{D} \qquad (2) $$

if and only if $\gamma = \gamma_{\min}$.

*Proof.* We write $\tilde{\alpha} = \varphi(\text{conv } \alpha)$ throughout the proof for a shorter notation. We prove the lemma by showing that for all $d$-chains $\gamma$ on $K$ that satisfy constraint (2), we have:

$$ \|\gamma\|_{1,W} \ge \|\gamma\|_{1,W_{\min}} \ge \int_{\mathcal{D}} f = \|\gamma_{\min}\|_{1,W_{\min}} = \|\gamma_{\min}\|_{1,W}, \qquad (3) $$
with the first inequality being an equality if and only if $\gamma = \gamma_{\min}$. Clearly, $\|\gamma\|_{1,W} \ge \|\gamma\|_{1,W_{\min}}$ because $W(\alpha) \ge W_{\min}(\alpha)$. To obtain the second inequality, recall that we have assumed $\sum_{\alpha} \gamma(\alpha) \mathbf{1}_{\tilde{\alpha}}(x) = 1$ almost everywhere in $\mathcal{D}$. We use this to write that:

$$ \|\gamma\|_{1,W_{\min}} \ge \sum_{\alpha} \gamma(\alpha) \int_{\tilde{\alpha}} f = \sum_{\alpha} \gamma(\alpha) \int_{\mathcal{D}} f \mathbf{1}_{\tilde{\alpha}} = \int_{\mathcal{D}} f \sum_{\alpha} \gamma(\alpha) \mathbf{1}_{\tilde{\alpha}} = \int_{\mathcal{D}} f, \quad (4) $$

where sums are over all $d$-simplices $\alpha$ in $K$. Setting $\gamma = \gamma_{\min}$ in (4), we observe that the inequality in (4) becomes an equality because none of the coefficients of $\gamma_{\min}$ are negative by construction. It follows that $\int_{\mathcal{D}} f = \|\gamma_{\min}\|_{1,W_{\min}}$. Finally, $\|\gamma_{\min}\|_{1,W_{\min}} = \|\gamma_{\min}\|_{1,W}$ because $\gamma_{\min}$ has been defined so that for all simplices $\alpha$ in its support, $W_{\min}(\alpha) = W(\alpha)$. We have thus established (3). Suppose now that $\gamma \ne \gamma_{\min}$ and let us prove that $\|\gamma\|_{1,W} > \|\gamma\|_{1,W_{\min}}$, or equivalently that

$$ \sum_{\alpha \in \text{Supp } \gamma} |\gamma(\alpha)| (W(\alpha) - W_{\min}(\alpha)) > 0. $$

Since none of the terms in the above sum are negative, it suffices to show that there exists at least one simplex $\alpha \in \text{Supp } \gamma$ for which $W(\alpha) > W_{\min}(\alpha)$. By contradiction, assume that for all $\alpha \in \text{Supp } \gamma$, $W(\alpha) = W_{\min}(\alpha)$. By construction, we thus have the implication: $\gamma(\alpha) \ne 0 \implies \gamma_{\min}(\alpha) = 1$, and therefore $\text{Supp } \gamma \subseteq \text{Supp } \gamma_{\min}$. But, since $\sum_{\alpha} \gamma_{\min}(\alpha) \mathbf{1}_{\tilde{\alpha}}(x) = 1$ for almost all $x \in \mathcal{D}$ and coefficients of $\gamma_{\min}$ are either 0 or 1, it follows that for almost all $x \in \mathcal{D}$, point $x$ is covered by a unique $d$-simplex in the support of $\gamma_{\min}$. Hence, the simplices in $\text{Supp } \gamma_{\min}$ have pairwise disjoint interiors while their union covers $\mathcal{D}$. Since $\sum_{\alpha} \gamma(\alpha) \mathbf{1}_{\tilde{\alpha}}(x) = 1$ for almost all $x \in \mathcal{D}$, the simplices in $\text{Supp } \gamma$ must also cover $\mathcal{D}$ while using only a subset of simplices in $\text{Supp } \gamma_{\min}$. The only possibility is that $\gamma = \gamma_{\min}$, yielding a contradiction. $\square$

# 6 Comparing power distances

The goal of this section is to relate the two maps $\text{Power}_\alpha(x)$ and $\text{Power}_\beta(y)$ for two $d$-simplices $\alpha \in \text{Dello}_d(P, \rho)$ and $\beta \subseteq P$, and for two points $x \in \text{conv } \alpha$ and $y \in \text{conv } \beta$, such that $\pi_M(x) = \pi_M(y)$. The main result of the section is stated in the following lemma and proved at the end of the section.

**Lemma 15.** Let $\varepsilon, \delta, \rho \ge 0$ such that $0 \le 2\varepsilon \le \rho$, and $16\delta \le \rho \le \frac{R}{3}$. Suppose that $P \subseteq \mathcal{M}^{\oplus\delta}$. Let $\zeta = \text{protection}(P, 3\rho)$ and assume that $\Theta(P, \rho) \le \frac{\pi}{6}$, separation($P$) > $\frac{3\rho^2}{R} + 3\delta$ and

$$ 10\rho \Theta(P, \rho) \cdot (\varepsilon + \rho \Theta(P, \rho)) < \zeta^2 + \zeta \text{ separation}(P). $$

Then, for every $\varepsilon$-small $d$-simplex $\alpha \in \text{Dello}_d(P, \rho)$, every $\rho$-small $d$-simplex $\beta \subseteq P$, every $x \in \text{conv } \alpha$, and every $y \in \text{conv } \beta$ such that $\pi_M(x) = \pi_M(y)$:

$$ \text{Power}_\beta(y) \le \text{Power}_\alpha(x) - \frac{1}{2} (\zeta^2 + \zeta \text{ separation}(P)) \sum_{b \in \beta \setminus \alpha} \mu_b, $$

where $\mu_b \ge 0$ are real numbers such that $y = \sum_{b \in \beta} \mu_b b$ and $\sum_{b \in \beta} \mu_b = 1$.

To prove the lemma, we need a few auxiliary results. We start by recalling a useful expression of the power distance of a point $x$ from the circumsphere $S(\alpha)$ of $\alpha$ when $x$ is an affine combination of the vertices of $\alpha$.

**Lemma 16.** Let $\alpha \subseteq \mathbb{R}^N$. If $x = \sum_{a \in \alpha} \lambda_a a$ with $\sum_{a \in \alpha} \lambda_a = 1$, then for every $z \in \mathbb{R}^N$

$$ \text{Power}_\alpha(x) = \|x - z\|^2 - \sum_{a \in \alpha} \lambda_a \|a - z\|^2. $$
Proof. Recall that Power$_{α}$(x) = ||x - Z(α)||² - R(α)². On one hand, we have that

$$ \|x - Z(\alpha)\|^2 = \|x - z\|^2 + 2(x - z) \cdot (z - Z(\alpha)) + \|z - Z(\alpha)\|^2. $$

On the other hand, we have that

$$ \begin{aligned} R(\alpha)^2 &= \sum_{a \in \alpha} \lambda_a \|Z(\alpha) - a\|^2 \\ &= \sum_{a \in \alpha} \lambda_a [\|Z(\alpha) - z\|^2 + 2(Z(\alpha) - z) \cdot (z - a) + \|z - a\|^2] \\ &= \|Z(\alpha) - z\|^2 + 2(Z(\alpha) - z) \cdot (z - x) + \sum_{a \in \alpha} \lambda_a \|z - a\|^2. \end{aligned} $$

Subtracting the above expressions of ||x - Z(α)||² and R(α)² yields the result. □

<figure><img src="image_3.png" /><figcaption>Figure 1: Notation for the proof of Lemma 17.</figcaption></figure>

**Lemma 17.** Let α and β be two non-degenerate abstract d-simplices in $\mathbb{R}^N$. Suppose that $α \in \text{Del}(\pi_{\text{aff } α}(α \cup β))$ and it is $\zeta$-protected with respect to $\pi_{\text{aff } α}(α \cup β)$. Suppose furthermore that the map $\pi_{\text{aff } α}|_{α \cup β}$ is injective. Then for every convex combination $y = \sum_{b \in β} \mu_b b$ with $\mu_b \ge 0$ and $\sum_{b \in β} \mu_b = 1$, we have

$$ \text{Power}_{\beta}(y) \le \text{Power}_{\alpha}(\pi_{\text{aff } \alpha}(y)) - (\zeta^2 + 2\zeta R(\alpha)) \sum_{b \in \beta \setminus \alpha} \mu_b. $$

Proof. See Figure 1. Let Z(α) be the radius of the (d-1)-dimensional circumsphere of α. Clearly, ||a - Z(α)|| = R(α) for all a ∈ α. Let $Q = \pi_{\text{aff } α}(α \cup β)$. Since $α \in \text{Del}(Q)$ and is $\zeta$-protected with respect to Q, we get:

$$ (R(\alpha) + \zeta)^2 < \|\pi_{\text{aff } \alpha}(b) - Z(\alpha)\|^2, \quad \text{for all } b \in \beta \setminus \alpha, $$

$$ R(\alpha)^2 = \|\pi_{\text{aff } \alpha}(b) - Z(\alpha)\|^2, \quad \text{for all } b \in \beta \cap \alpha. $$

Multiplying both sides of each equation above by $\mu_b$ and summing over all $b \in \beta$, we obtain:

$$ R(\alpha)^2 + (\zeta^2 + 2\zeta R(\alpha)) \sum_{b \in \beta \setminus \alpha} \mu_b \le \sum_{b \in \beta} \mu_b \|\pi_{\text{aff } \alpha}(b) - Z(\alpha)\|^2. \quad (5) $$

For short, write $y' = \pi_{\text{aff } α}(y)$ and $\beta' = \pi_{\text{aff } α}(β)$. Noting that $y' = \sum_{b \in β} \mu_b b'$ and applying Lemma 16 with $z = Z(α)$, we get that

$$ \text{Power}_{\beta'}(y') = \|y' - Z(\alpha)\|^2 - \sum_{b \in \beta} \mu_b \|\pi_{\text{aff } \alpha}(b) - Z(\alpha)\|^2. $$
Substracting $||y' - Z(\alpha)||^2$ from both sides of (5) and using the above expression, we obtain

$$ - \text{Power}_{\alpha}(y') + (\zeta^2 + 2\zeta R(\alpha)) \sum_{b \in \beta \setminus \alpha} \mu_b \le - \text{Power}_{\beta'}(y'). $$

Applying Lemma 16 again, with $Z = y'$ and $Z = y$ respectively, we get that:

$$ - \text{Power}_{\beta'}(y') = \sum_{b \in \beta} \mu_b ||\pi_{\text{aff } \alpha}(b) - \pi_{\text{aff } \alpha}(y)||^2 \le \sum_{b \in \beta} \mu_b ||b - y||^2 = - \text{Power}_{\beta}(y), $$

which concludes the proof. □

**Lemma 18.** Let $\alpha$ and $\beta$ be two non-degenerate abstract d-simplices in $\mathbb{R}^N$. Suppose that $\alpha \in \text{Del}(\pi_{\text{aff } \alpha}(\alpha \cup \beta))$ and $\alpha$ is $\zeta$-protected with respect to $\pi_{\text{aff } \alpha}(\alpha \cup \beta)$. Suppose that the map $\pi_{\text{aff } \alpha}|_{\alpha \cup \beta}$ is injective and that both $\text{conv } \alpha$ and $\text{conv } \beta$ are contained in the $\rho$-tubular neighborhood of $M$. Suppose furthermore that $\beta$ is $\rho$-small. If $\Theta(\alpha) < \frac{\pi}{6}$ and

$$ 5\rho \sin \Theta(\alpha) \cdot (2R(\alpha) + 2\rho \sin \Theta(\alpha)) < \zeta^2 + 2\zeta R(\alpha), $$

then for every $x \in \text{conv } \alpha$ and every $y \in \text{conv } \beta$ with $\pi_M(x) = \pi_M(y)$, we have

$$ \text{Power}_{\beta}(y) \le \text{Power}_{\alpha}(x) - \frac{1}{2}(\zeta^2 + 2\zeta R(\alpha)) \sum_{b \in \beta \setminus \alpha} \mu_b, $$

where $\mu_b \ge 0$ are real numbers such that $y = \sum_{b \in \beta} \mu_b b$ and $\sum_{b \in \beta} \mu_b = 1$.

*Proof.* Consider a point $x \in \text{conv } \alpha$ and a point $y \in \text{conv } \beta$ with $\pi_M(x) = \pi_M(y)$. We distinguish two cases depending on whether $y$ belongs to $\text{conv}(\alpha \cap \beta)$ or not.

First, assume that $y \in \text{conv}(\alpha \cap \beta)$. In that case, we claim that the only possibility is that $x = y$. Indeed, assume for a contradiction that this is not the case. Then, we would have two distinct points $x \ne y$ of $\text{conv } \alpha$ that share the same projection onto $M$, showing that $\angle(\text{aff } \alpha, \mathbf{T}_{\pi_M(x)}M) = \frac{\pi}{2}$ for some $x \in \text{conv } \alpha$ and contradicting our assumption that $\Theta(\alpha) < \frac{\pi}{6}$. Hence, $x = y \in \text{conv}(\alpha \cap \beta)$. We claim that furthermore $\text{Power}_\alpha(x) = \text{Power}_\beta(y)$. Indeed, Lemma 16 implies that when $x$ is an affine combination of points in $\alpha$, that is, when $x = \sum_{a \in \alpha} \lambda_a a$ with $\sum_a \lambda_a = 1$, then $\text{Power}_\alpha(x) = - \sum_{a \in \alpha} \lambda_a ||x - a||^2$. In particular, if $x$ belongs to the convex hull of a face of $\alpha$, the expression of the power distance depends only upon the vertices of that face. It follows that

$$ \text{Power}_{\alpha}(x) = \text{Power}_{\alpha \cap \beta}(x) = \text{Power}_{\alpha \cap \beta}(y) = \text{Power}_{\beta}(y). $$

Since $y \in \text{conv}(\alpha \cap \beta)$, we have $\sum_{b \in \beta \setminus \alpha} \mu_b = 0$ and combining this with the above equality, we get the desired inequality.

Second, assume that $y \in \text{conv } \beta \setminus \text{conv}(\alpha \cap \beta)$; see Figure 2. Suppose $y = \sum_{b \in \beta} \mu_b b$ with $\mu_b \ge 0$ and $\sum_{b \in \beta} \mu_b = 1$. Letting $y' = \pi_{\text{aff } \alpha}(y)$, we know by Lemma 17 that:

$$ \text{Power}_{\beta}(y) \le \text{Power}_{\alpha}(y') - (\zeta^2 + 2\zeta R(\alpha)) \sum_{b \in \beta \setminus \alpha} \mu_b. \quad (6) $$

Because $y \notin \text{conv}(\alpha \cap \beta)$, we have $\sum_{b \in \alpha \cap \beta} \mu_b \ne 1$ and therefore $\sum_{b \in \beta \setminus \alpha} \mu_b \ne 0$. First, suppose that $y = x$. In that case, $y' = x$ and the result follows immediately. Second, suppose that $y \ne x$. We claim that in that case we also have $y \ne y'$. Indeed, if we were to have that $y = y'$, then both $x$ and $y$ would belong to $\text{aff } \alpha$ and since $\pi_M(x) = \pi_M(y)$, this would mean that $\angle(\text{aff } \alpha, \mathbf{T}_{\pi_M(x)}M) = \frac{\pi}{2}$ for $x \in \text{conv } \alpha$, contradicting our assumption that $\Theta(\alpha) < \frac{\pi}{6}$. Thus, $x \ne y$ and $y \ne y'$,
<figure><img src="image_4.png" /><figcaption>Figure 2: Right: Notation for the proof of Lemma 18.</figcaption></figure>

and we can define the angle $\theta = \angle xyz'$. Noting that $\theta \le \angle(\text{aff } \alpha, \mathbf{T}_{\pi_M(x)}\mathcal{M}) \le \Theta(\alpha)$ and $\|x - y'\| = \|x - y\|\sin\theta$, and recalling that $Z(\alpha)$ is the radius of the $(d-1)$-dimensional circumsphere of $\alpha$, we have:

$$ \begin{aligned} \text{Power}_{\alpha}(y') - \text{Power}_{\alpha}(x) &= \|y' - Z(\alpha)\|^2 - \|x - Z(\alpha)\|^2 = (y' - x) \cdot (x + y' - 2Z(\alpha)) \\ &\le \|x - y'\| \cdot (\|x - Z(\alpha)\| + \|y' - Z(\alpha)\|) \\ &\le \|x - y'\| \cdot (2\|x - Z(\alpha)\| + \|x - y'\|) \\ &\le \|x - y\| \sin\theta \cdot (2R(\alpha) + \|x - y\| \sin\theta). \end{aligned} \quad (7) $$

Writing $m = \pi_M(x) = \pi_M(y)$, we have $\|x - y\| \le \|x - m\| + \|m - y\| \le 2\rho$. Summing up Inequalities (6) and (7), we get

$$ \text{Power}_{\beta}(y) - \text{Power}_{\alpha}(x) \le - (\zeta^2 + 2\zeta R(\alpha)) \underbrace{\sum_{b \in \beta \setminus \alpha} \mu_b}_{A} + \underbrace{\|x - y\| \sin \theta \cdot (2R(\alpha) + 2\rho \sin \Theta(\alpha))}_{B}. $$

To establish the lemma in the second case, it suffices to show that $2B < A$, that is,

$$ 2\|x - y\| \sin \Theta(\alpha) \cdot (2R(\alpha) + 2\rho \sin \Theta(\alpha)) < (\zeta^2 + 2\zeta R(\alpha)) \sum_{b \in \beta \setminus \alpha} \mu_b. \quad (8) $$

We consider two subcases:

Subcase 1: $\alpha \cap \beta = \emptyset$. In that case, $\sum_{b \in \beta \setminus \alpha} \mu_b = 1$, and because $2\|x - y\| \le 4\rho \le 5\rho$, one can see that (8) follows from our assumptions.

Subcase 2: $\alpha \cap \beta \neq \emptyset$. In that case, we know that there exists a point $u \in \text{conv}(\beta \cap \alpha)$ and a point $v \in \text{conv}(\beta \setminus \alpha)$ such that $y = \sum_{b \in \beta \cap \alpha} \mu_b u + \sum_{b \in \beta \setminus \alpha} \mu_b v$; see Figure 2. Furthermore, letting $v' = \pi_{\text{aff } \alpha}(v)$ we have

$$ \sum_{b \in \beta \setminus \alpha} \mu_b = \frac{\|y - u\|}{\|v - u\|} \ge \frac{\|y - y'\|}{\|v - u\|} \ge \frac{\|x - y\| \cos \theta}{\text{Diam}(\beta)} \ge \frac{\|x - y\| \cos \theta}{2\rho} \ge \frac{\sqrt{3}}{4\rho} \cdot \|x - y\|. $$

Again, (8) follows from our assumptions.

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

*Proof of Lemma 15.* Since $\alpha$ is a $d$-simplex of $\text{Delloc}_d(P, \rho)$, we have that $\alpha \in \text{Del}(\pi_{\text{aff } \alpha}(P \cap B(c_{\sigma}, \rho)))$, and because $\alpha$ is $\varepsilon$-small, we have that $B(Z(\alpha), R(\alpha)) \subseteq B(c_{\sigma}, 2\varepsilon) \subseteq B(c_{\sigma}, \rho)$ and consequently $\alpha \in \text{Del}(\pi_{\text{aff } \sigma}(P \cap B(c_{\sigma}, 3\rho)))$. Consider a $\rho$-small $d$-simplex $\beta \subseteq P$ such that
$\pi_M(\alpha) \cap \pi_M(\beta) \neq \emptyset$ and let us show that $\beta \subseteq P \cap B(c_\sigma, 3\rho)$. Suppose that $x \in \text{conv } \alpha$ and $y \in \text{conv } \beta$ share the same projection $m$ onto $M$, that is, $m = \pi_M(x) = \pi_M(y)$. Since both $\alpha$ and $\beta$ are $\rho$-small, Lemma 23 implies that both $\text{conv } \alpha$ and $\text{conv } \beta$ are contained in the $(\frac{\rho}{4})$-tubular neighborhood of $M$ and in particular $\|x - y\| \le \|x - m\| + \|m - y\| \le \frac{\rho}{4} + \frac{\rho}{4} \le \frac{\rho}{2}$. For all vertices $b \in \beta$, we thus have

$$ \|c_{\alpha} - b\| \le \|c_{\alpha} - x\| + \|x - y\| + \|y - b\| \le \varepsilon + \frac{\rho}{2} + 2\rho \le 3\rho, $$

showing that $\beta \subseteq P \cap B(c_\sigma, 3\rho)$. Hence, we get that $\alpha \in \text{Del}(\pi_{\text{aff } \sigma}(\alpha \cup \beta))$ and the fact that $\text{protection}(P, 3\rho) = \zeta$ implies that $\alpha$ is $\zeta$-protected with respect to $\pi_{\text{aff } \alpha}(\alpha \cup \beta)$. By Lemma 24, the restriction of $\pi_{\text{aff } \alpha}$ to $P \cap B(c_\alpha, \rho)$ is injective. To apply Lemma 18, it simply remains to verify that

$$ 5\rho \sin \Theta(\alpha) \cdot (2R(\alpha) + 2\rho \sin \Theta(\alpha)) < \zeta^2 + 2\zeta R(\alpha). $$

Since $\frac{\text{separation}(P)}{2} \le R(\alpha) \le \varepsilon$ and $\sin t \le t$ for all $t \ge 0$, this follows from:

$$ 10\rho\Theta(\alpha) \cdot (\varepsilon + \rho\Theta(\alpha)) < \zeta^2 + \zeta \text{ separation}(P), $$

which is a consequence of our hypotheses. $\square$

# 7 Proving the main result

Suppose that $K$ is a simplicial complex with vertex set $P$. Write $D = \text{Del}_d(P, \rho)$, $\mathcal{D} = |D|$ and $\mathcal{K} = |K|$ for short. In this section, we prove our main theorem by applying Lemma 14. This requires us to define two maps $\varphi: K \to \mathcal{D}$ and $f: \mathcal{D} \to \mathbb{R}$, two weights $W(\alpha)$ and $W_{\min}(\alpha)$ for each $d$-simplex $\alpha \in K$, and to check that these maps and weights satisfy the requirements of Lemma 14. For each $\alpha \in K$, let $W(\alpha) = \omega(\alpha)$ be the Delaunay weight of $\alpha$. To be able to define $\varphi$, $f$, and $W_{\min}$, we assume that the following conditions are met:

(1) $D$ is a faithful reconstruction of $M$;

(2) For every $d$-simplex $\sigma \subseteq K$, the map $\pi_M|_{\text{conv } \sigma}$ is well-defined and injective.

These conditions are easily derived from the assumptions of the main theorem. We are now ready to introduce additional notation. Consider a subset $X \subseteq \mathbb{R}^N$ and suppose that the map $\pi_M|_X$ is well-defined and injective. Then it is possible to define a bijective map $\pi_{X \to M}: X \to \pi_M(X)$. Because $D$ is a faithful reconstruction of $M$, the map $\pi_{D \to M}$ is well-defined and bijective. Similarly, for every $d$-simplex $\sigma \in K$, the map $\pi_{\text{conv } \sigma \to M}$ is well-defined and bijective. We now introduce the map $\varphi: K \to \mathcal{D}$ defined by $\varphi = [\pi_{D \to M}]^{-1} \circ \pi_M$ and let $f: \mathcal{D} \to \mathbb{R}$ be the map defined by:

$$ f(x) = \min_{\sigma} \left( -\text{Power}_{\sigma}([\pi_{\text{conv } \sigma \to M}]^{-1} \circ \pi_{M}(x)) \right), \quad (9) $$

where the minimum is taken over all $d$-simplices $\sigma \in K$ such that $x \in \varphi(\text{conv } \sigma)$. Note that $f(x)$ can be defined equivalently as the minimum of $-\text{Power}_\beta(y)$ over all $d$-simplices $\beta \in K$ and all points $y \in \text{conv } \beta$ such that $\pi_M(x) = \pi_M(y)$. Given a $d$-simplex $\sigma \in K$, we associate to $\sigma$ the weight:

$$ W_{\min}(\sigma) = \int_{x \in \varphi(\text{conv } \sigma)} f(x) dx. \quad (10) $$

**Lemma 19.** Under the assumptions of Theorem 13:

* For every $d$-simplex $\alpha \in D$ and every point $x \in \text{conv } \alpha$, we have $f(x) = -\text{Power}_\alpha(x)$.
• For every d-simplex $\alpha \in D$, we have $W_{\min}(\alpha) = W(\alpha)$.

**Proof.** Consider a d-simplex $\alpha \in D$, a d-simplex $\beta \in K$, $x \in \text{conv } \alpha$ and $y \in \text{conv } \beta$ such that $\pi_M(x) = \pi_M(y)$. Applying Lemma 15, we obtain that $\text{Power}_\beta(y) \le \text{Power}_\alpha(x)$ or equivalently $\text{Power}_\beta([\pi_{\text{conv } \beta \to M}]^{-1} \circ \pi_M(x)) \le \text{Power}_\alpha(x)$ and therefore $f(x) = -\text{Power}_\alpha(x)$. To establish the second item of the lemma, notice that for all $\alpha \in D$, the restriction of $\varphi$ to $\text{conv } \alpha$ is the identity function, $\varphi|_{\text{conv } \alpha} = \text{Id}$ and therefore $\varphi(\text{conv } \alpha) = \text{conv } \alpha$. Since we have just established that $f(x) = -\text{Power}_\alpha(x)$, we get that

$$W_{\min}(\alpha) = \int_{x \in \varphi(\text{conv } \alpha)} f(x) dx = \int_{x \in \text{conv } \alpha} -\text{Power}_{\alpha}(x) dx = \omega(\alpha) = W(\alpha),$$

which concludes the proof. □

**Lemma 20.** Under the assumptions of Theorem 13, for every d-simplex $\beta \in K \setminus D$, we have $W_{\min}(\beta) < W(\beta)$.

**Proof.** We need some notation. Given $\alpha$ and $\beta$ in $K$, we write $\text{conv}|_{\alpha, \beta}$ for the set of points $y \in \text{conv } \beta$ for which there exists a point $x \in \text{conv } \alpha$ such that $\pi_M(x) = \pi_M(y)$. We define the map $\varphi_{\beta \to \alpha} : \text{conv}|_{\alpha, \beta} \to \text{conv}|_{\beta, \alpha}$ as $\varphi_{\beta \to \alpha}(y) = [\pi_{\text{conv } \alpha \to M}]^{-1} \circ \pi_{\text{conv } \beta \to M}(y)$. Note that $\varphi_{\beta \to \alpha}$ is invertible and its inverse is $\varphi_{\alpha \to \beta}$. Also, note that $J$ in Theorem 13 has been chosen precisely so that one can apply Lemma 38 and guarantee that $|\det(J\varphi_{\beta \to \alpha})(y)| \in [\frac{1}{1+J}, 1+J]$ for all $\alpha, \beta \in K$ and all $y \in \text{conv}|_{\alpha, \beta}$. Consider a d-simplex $\beta \in K \setminus D$. By Lemma 19, $f(x) = -\text{Power}_\alpha(x)$ and therefore:

$$W_{\min}(\beta) = \sum_{\alpha \in D^{[d]}} \int_{x \in \text{conv}|_{\beta, \alpha}} -\text{Power}_{\alpha}(x) dx.$$

For any convex combination $y$ of points in $\beta$, let $\{\mu_b^\beta(y)\}_{b \in \beta}$ designate the family of non-negative real numbers summing up to 1 such that $y = \sum_{b \in \beta} \mu_b^\beta(y)b$. Plugging in the upper bound on $-\text{Power}_\alpha(x)$ provided by Lemma 15, letting

$$c = \frac{1}{2} (\zeta^2 + \zeta \text{ separation}(P)),$$

and making the change of variable $x = \varphi_{\beta \to \alpha}(y)$, we upper bound $W_{\min}(\beta)$ as follows:

$$\begin{align*}
W_{\min}(\beta) &\le \sum_{\alpha \in D^{[d]}} \int_{x \in \text{conv}|_{\beta, \alpha}} \left[ -\text{Power}_{\beta}(\varphi_{\alpha \to \beta}(x)) - c \sum_{b \in \beta \setminus \alpha} \mu_{\beta}^{b}(\varphi_{\alpha \to \beta}(x)) \right] dx \\
&= \sum_{\alpha \in D^{[d]}} \int_{y \in \text{conv}|_{\alpha, \beta}} \left[ -\text{Power}_{\beta}(y) - c \sum_{b \in \beta \setminus \alpha} \mu_{\beta}^{b}(y) \right] |\det(J\varphi_{\beta \to \alpha})(y)| dy \\
&\le (1+J)W(\beta) - (1+J)^{-1}c \sum_{\alpha \in D^{[d]}} \int_{y \in \text{conv}|_{\alpha, \beta}} \sum_{b \in \beta \setminus \alpha} \mu_{\beta}^{b}(y) dy.
\end{align*}$$

A key observation is that, because $\beta \ne \alpha$, then $\beta \setminus \alpha \ne \emptyset$. Therefore the sum $\sum_{b \in \beta \setminus \alpha} \mu_b^\beta(y)$ does not vanish and is always lower bounded by $\inf_{b \in \beta} \mu_b^\beta(y)$. Associating the quantity

$$\Omega(\beta) = \int_{y \in \text{conv } \beta} \inf_{b \in \beta} \mu_{\beta}^{b}(y) dy,$$
to $\beta$ we thus obtain that $W_{\min}(\beta) \le (1+J)W(\beta) - (1+J)^{-1}c\Omega(\beta)$. Hence, $W_{\min}(\beta) < W(\beta)$ as long as

$$JW(\beta) < (1+J)^{-1}c\Omega(\beta). \qquad (11)$$

Using a change of variable, it is not too difficult to show that $\Omega(\beta) = d! \mathrm{vol}(\beta)\Omega(\Delta_d)$, where $\Delta_d = \{\lambda \in \mathbb{R}^d | \sum_{i=1}^d \lambda_i \le 1; \lambda_i \ge 0, i = 1, 2, \dots, d\}$ represents the standard $d$-simplex. Remark that $\Omega(\Delta_d)$ is a constant that depends only upon the dimension $d$ and is thus universal. Plugging in $\Omega(\beta) = d! \mathrm{vol}(\beta)\Omega(\Delta_d)$ on the right side of (11), and the expression of $W(\beta) = \omega(\beta)$ given by Lemma 6 on the left side of (11), and recalling that $\beta$ is $\rho$-small, we find that condition (11) is implied by the following condition:

$$J\rho^2 < (1+J)^{-1} \frac{(d+2)(d-1)!}{4} (\zeta^2 + \zeta \mathrm{separation}(P)) \Omega(\Delta_d),$$

which we have assumed to hold.

□

**Proof of Theorem 13.** We start with pointing out that Problem (⋆) is invariant under change of orientation of $d$-simplices in $K$ and thus we may assume that every $d$-simplex $\alpha$ in $K$ has an orientation that is consistent with that of $M$, that is, $\mathrm{sign}_M(\alpha) = 1$ for all $\alpha \in K^{[d]}$. Let $D = \mathrm{Dalloc}_d(P, \rho)$, $\mathcal{D} = |D|$ and $\mathcal{K} = |K|$. Theorem 10 ensures that $\mathcal{D}$ is a $d$-manifold and $\pi_M: \mathcal{D} \to M$ is a homeomorphism. Define $\varphi: \mathcal{K} \to \mathcal{D}$, $f: \mathcal{D} \to \mathbb{R}$, $W$, and $W_{\min}$ as explained at the beginning of the section. Consider the $d$-chain $\gamma_{\min}$ on $K$:

$$\gamma_{\min}(\alpha) = \begin{cases} 1 & \text{if } W_{\min}(\alpha) = W(\alpha), \\ 0 & \text{otherwise.} \end{cases}$$

By Lemma 19 and Lemma 20, the following property holds: for all $\alpha \in K$, $W_{\min}(\alpha) = W(\alpha)$ if and only if $\alpha$ is a $d$-simplex of $D$. It follows that $\gamma_{\min} = \gamma_D$. Furthermore, we have $\sum_{\alpha \in K^{[d]}} \gamma_{\min}(\alpha) \mathbf{1}_{\varphi(\mathrm{conv}\,\alpha)}(x) = \sum_{\alpha \in D^{[d]}} \mathbf{1}_{\mathrm{conv}\,\alpha}(x) = 1$ for almost all $x \in \mathcal{D}$. Recalling that $W = \omega$ and therefore $\|\gamma\|_{1,W} = \mathrm{E}_{\mathrm{del}}(\gamma)$, and applying Lemma 14, we deduce that $\gamma_{\min} = \gamma_D$ is the unique solution to the following optimization problem over the set of chains in $C_d(K, \mathbb{R})$:

$$\begin{array}{ll} \underset{\gamma}{\operatorname{minimize}} & \mathrm{E}_{\mathrm{del}}(\gamma) \\ \text{subject to} & \sum_{\alpha \in K^{[d]}} \gamma(\alpha) \mathrm{sign}_{\mathcal{M}}(\alpha) \mathbf{1}_{\varphi(\mathrm{conv}\,\alpha)}(x) = 1, \text{ for almost all } x \in \mathcal{D} \quad (\star\star) \end{array}$$

One can see that Problem (⋆⋆) remains unchanged if one replaces the constraint with

$$\sum_{\alpha \in K^{[d]}} \gamma(\alpha) \mathrm{sign}_{\mathcal{M}}(\alpha) \mathbf{1}_{\pi_{\mathcal{M}}(\mathrm{conv}\,\alpha)}(m) = 1, \quad \text{for almost all } m \in \mathcal{M}. \qquad (12)$$

Let $m_0$ be the arbitrary generic point of $M$, as in Problem (⋆). By Lemma 48, the above constraint is equivalent to the following set of constraints:

$$\left\{ \begin{array}{l} \partial\gamma = 0, \\ \sum_{\alpha \in K^{[d]}} \gamma(\alpha) \mathrm{sign}_{\mathcal{M}}(\alpha) \mathbf{1}_{\pi_{\mathcal{M}}(\mathrm{conv}\,\alpha)}(m_0) = 1. \end{array} \right.$$

We deduce that Problem (⋆) and Problem (⋆⋆) are equivalent, and we get the result.

□

# 8 Practical aspects

In this section, we discuss practical aspects.
## 8.1 Transforming the problem into a realistic algorithm

Besides the complex $K$ that one can build from $P$, Problem $(\star)$ seems to require the knowledge of $\mathcal{M}$ for expressing the normalization constraint $\text{load}_{m_0, \mathcal{M}, K}(\gamma) = 1$. What we call a realistic algorithm is an algorithm that takes only the point set $P$ as input. In this section, we explain how to transform Problem $(\star)$ into an equivalent problem that does not refer to $\mathcal{M}$ anymore, thus providing a realistic algorithm. Roughly, we simply replace the constraint $\text{load}_{m_0, \mathcal{M}, K}(\gamma) = 1$ by a constraint of the form $\text{load}_{p_0, \Pi, \Sigma}(\gamma) = 1$, where $p_0 \in P$, $\Pi$ is a $d$-flat that “roughly approximates” $\mathcal{M}$ near $p_0$ and $\Sigma$ are simplices of $K$ “close” to $p_0$. Lemma 21 (see below) makes this idea precise. Given a point $x \in \mathbb{R}^N$ and $r \ge 0$, let us introduce the subset of $K$:

$$K[x, r] = \{\sigma \in K \mid \text{conv } \sigma \cap B(x, r) \neq \emptyset\}.$$

Note that $K[x, r]$ is not necessarily a simplicial complex.

**Lemma 21.** Suppose $0 \le \rho \le \frac{R}{25}$. Consider a point $x \in \mathcal{M}^{\oplus \rho}$ and a $d$-dimensional affine space $\Pi$ passing through $x$. Suppose that $\angle(\Pi, \mathbf{T}_{\pi_{\mathcal{M}}(x)}\mathcal{M}) \le \frac{\pi}{8}$ and that the orientation of $\Pi$ is consistent with that of $\mathbf{T}_{\pi_{\mathcal{M}}(x)}\mathcal{M}$. Then, Problem $(\star)$ is equivalent to the problem obtained by replacing the constraint $\text{load}_{m_0, \mathcal{M}, K}(\gamma) = 1$ with the constraint $\text{load}_{x, \Pi, K[x, 4\rho]}(\gamma) = 1$.

*Proof.* This is a direct consequence of Lemma 49 which may be found in Appendix G. $\square$

Observe that the conditions on the $d$-flat $\Pi$ in the above lemma are rather mild. Indeed, we only require $\Pi$ to pass through a point $x$ such that $d(x, \mathcal{M}) \le \frac{R}{25}$ and $\angle(\Pi, \mathbf{T}_{\pi_{\mathcal{M}}(x)}\mathcal{M}) \le \frac{\pi}{8}$. Hence, $\Pi$ only needs to be what we could call a rough approximation of $\mathcal{M}$ near $x$. In practice, we may take for $x$ any point $p_0 \in P$ and for $\Pi$ the $d$-dimensional affine space $T_{p_0}(P, \rho)$ passing through $p_0$ and parallel to the $d$-dimensional vector space $V_{p_0}(P, \rho)$ defined as follows: $V_{p_0}(P, \rho)$ is spanned by the eigenvectors associated to the $d$ largest eigenvalues of the inertia tensor of $(P \cap B(p_0, \rho)) - c$, where $c$ is the center of mass of $P \cap B(p_0, \rho)$. By Lemma 51, for $\frac{\rho}{R}$ small enough and $\varepsilon < \frac{\rho}{16}$, we have

$$\angle(T_{p_0}(P, \rho), T_{\pi_{\mathcal{M}}(p_0)}\mathcal{M}) \le \frac{\pi}{8}.$$

See Section H for more details. Hence, the assumptions of the above lemma hold for $x = p_0$ and $\Pi = T_{p_0}(P, \rho)$. This shows that the normalization constraint in Problem $(\star)$ can be replaced by a constraint whose definition depends only upon the point set $P$, thus providing a realistic algorithm.

## 8.2 Perturbing the data set for ensuring the safety conditions

In this section, we assume that $P_0$ is a $\delta_0$-accurate $\varepsilon_0$-dense sample of $\mathcal{M}$ and perturbe it to obtain a point set $P$ that satisfies the assumptions of our main theorem. For this, we use the Moser Tardos Algorithm [34] as a perturbation scheme in the spirit of what is done in [7, Section 5.3.4].

The perturbation scheme is parametrized with real numbers $\rho \ge 0$, $r_{\text{pert.}} \ge 0$, Heigh$_{\min} > 0$, and Prot$_{\min} > 0$. To describe it, we need some notations and terminology. Let $T_{p_0}^* = T_{p_0}(P_0, 3\rho)$ be the $d$-dimensional affine space passing through $p_0$ and parallel to the $d$-dimensional vector space $V_{p_0}(P_0, 3\rho)$ whose definition has been given in the previous section. To each point $p_0 \in P_0$, we associate a perturbed point $p \in P$, computed by applying a sequence of elementary operations called reset. Precisely, given a point $p \in P$ associated to the point $p_0 \in P_0$, the reset of $p$ is the operation that consists in drawing a point $q$ uniformly at random in $V_{p_0} \cap B(p_0, r_{\text{pert.}})$ and assigning $q$ to $p$. Finally, we call any of the two situations below a bad event:
**Violation of the height condition by $\sigma$:** A $\rho$-small $d$-simplex $\sigma \subseteq P$ such that $\text{height}(\sigma) < \text{Heigh}_{\text{min}}$;

**Violation of the protection condition by $(p, \sigma)$:** A pair $(p, \sigma)$ made of a point $p \in P$ and a $d$-simplex $\sigma \subseteq P \setminus \{p\}$ such that $p \in B(c_{\sigma}, 3\rho)$ and $\sigma$ is not $\text{Prot}_{\text{min}}$-protected with respect to $\{\pi_{\text{aff}}\sigma(p)\}$.

In both situations, we associate to the bad event $E$ a set of points called the points *correlated* to $E$. In the first situation, the points correlated to $E$ are the $d+1$ vertices of $\sigma$ and in the second situation, they are the $d+2$ points of $\{p\} \cup \sigma$.

**Moser-Tardos Algorithm:**

1. For each $p_0 \in P_0$, compute the $d$-dimensional affine space $T_{p_0}^*$

2. For each point $p \in P$, reset $p$

3. WHILE (some bad event $E$ occurs):

------- For each point $p$ correlated to $E$, reset $p$

--- END WHILE

4. Return $P$

Roughly speaking, in our context, the Moser Tardos Algorithm reassigns new coordinates to any point $p \in P$ that is correlated to a bad event as long as a bad event occurs. A beautiful result from [34] tells us that the Moser-Tardos Algorithm terminates in a number of steps that is expected to be linear in the size of $P$. We thus have:

**Lemma 22.** Let $\varepsilon_0 \ge 0$, $\eta_0 > 0$, and $\rho = C_{\text{ste}}\varepsilon_0$, where $C_{\text{ste}} \ge 32$. Let $\delta_0 = \frac{\rho^2}{R}$, $r_{\text{pert.}} = \frac{\eta_0\varepsilon_0}{20}$, $\varepsilon = \frac{21}{20}\varepsilon_0$, and $\delta = 2\delta_0$. There are positive constants $c_1$, $c_2$, $c_3$, and $c_4$ that depend only upon $\eta_0$, $C_{\text{ste}}$, and $d$ such that if $\frac{\varepsilon_0}{R} < c_1$ then, given a point set $P_0$ such that $\mathcal{M} \subseteq (P_0)^{\oplus\varepsilon_0}$, $P_0 \subseteq \mathcal{M}^{\oplus\delta_0}$, and separation$(P_0) > \eta_0\varepsilon_0$, the point set $P$ obtained after resetting each of its points satisfies $\mathcal{M} \subseteq P^{\oplus\varepsilon}$, $P \subseteq \mathcal{M}^{\oplus\delta}$, and separation$(P) > \frac{9}{10}\eta_0\varepsilon_0$. Moreover, whenever we apply the Moser-Tardos Algorithm with $\text{Heigh}_{\text{min}} = c_2(\frac{\rho}{R})^{\frac{1}{3}}\rho$ and $\text{Prot}_{\text{min}} = c_3(\frac{\rho}{R})^{\frac{1}{3}}\rho$, the algorithm terminates with expected time $O(\#P_0)$ and returns a point set $P$ that satisfies:

$$ \text{height}(P, \rho) \ge c_2 \left(\frac{\rho}{R}\right)^{\frac{1}{3}} \rho $$

$$ \text{protection}(P, \rho) \ge c_3 \left(\frac{\rho}{R}\right)^{\frac{1}{3}} \rho $$

As a consequence of the above lower bound on $\text{height}(P, \rho)$, we have:

$$ \Theta(P, \rho) \le c_4 \left(\frac{\rho}{R}\right)^{\frac{2}{3}}. $$

The point set $P$ returned by the Moser-Tardos Algorithm is a $\delta$-accurate $\varepsilon$-dense sample of $\mathcal{M}$ that satisfies the assumptions of Theorem 13 with parameters $\varepsilon$, $\delta$, $\rho$, and some $\theta \ge 0$.

*Sketch of proof.* The computation for the perturbation section in Appendix C of [4] can be adapted in order to meet the claimed asymptotic bounds for height and protection, with the same perturbation radius $r_{\text{pert.}}$. Then it is possible to verify that, with these asymptotic bounds, when $\frac{\rho}{R}$ is small enough, the safety conditions of Theorem 13 hold. $\square$
## References

[1] Eddie Aamari, Jisu Kim, Frédéric Chazal, Bertrand Michel, Alessandro Rinaldo, Larry Wasserman, et al. Estimating the reach of a manifold. *Electronic journal of statistics*, 13(1):1359-1399, 2019.

[2] Pierre Alliez, David Cohen-Steiner, Mariette Yvinec, and Mathieu Desbrun. Variational tetrahedral meshing. *ACM Transactions on Graphics* (TOG), 24(3):617-625, 2005.

[3] D. Attali and A. Lieutier. Reconstructing shapes with guarantees by unions of convex sets. In *Proc. 26th Ann. Sympos. Comput. Geom.*, pages 344-353, Snowbird, Utah, June 13-16 2010.

[4] D. Attali and A. Lieutier. Flat delaunay complexes for homeomorphic manifold reconstruction, 2022. Technical report available on ArXiv.

[5] D. Attali, A. Lieutier, and D. Salinas. Vietoris-rips complexes also provide topologically correct reconstructions of sampled shapes. *Computational Geometry: Theory and Applications*, 46(4):448-465, 2013.

[6] J.-D. Boissonnat and A. Ghosh. Manifold reconstruction using tangential delaunay complexes. *Discrete & Computational Geometry*, 51(1):221-267, 2014.

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

[8] Jean-Daniel Boissonnat, Ramsay Dyer, and Arijit Ghosh. The stability of delaunay triangulations. *International Journal of Computational Geometry & Applications*, 23(04n05):303-333, aug 2013. URL: https://doi.org/10.1142/2Fs0218195913600078, doi:10.1142/s0218195913600078.

[9] Jean-Daniel Boissonnat, Ramsay Dyer, Arijit Ghosh, André Lieutier, and Mathijs Wintraecken. Local conditions for triangulating submanifolds of euclidean space. *Discrete & Computational Geometry*, pages 1-21, 2020.

[10] 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(1-2):29-58, 2019.

[11] Jean-Daniel Boissonnat and Mariette Yvinec. *Algorithmic geometry*. Cambridge university press, 1998.

[12] Glencora Borradaile, William Maxwell, and Amir Nayyeri. Minimum Bounded Chains and Minimum Homologous Chains in Embedded Simplicial Complexes. In Sergio Cabello and Danny Z. Chen, editors, *36th International Symposium on Computational Geometry (SoCG 2020)*, volume 164 of *Leibniz International Proceedings in Informatics (LIPIcs)*, pages 21:1-21:15, Dagstuhl, Germany, 2020. Schloss Dagstuhl-Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.SoCG.2020.21.

[13] Luitzen EJ Brouwer. Zur invarianz des n-dimensionalen gebiets. *Mathematische Annalen*, 72:55-56, 1912.

[14] Erin W. Chambers, Jeff Erickson, and Amir Nayyeri. Minimum cuts and shortest homologous cycles. In *Proceedings of the 25th Annual Symposium on Computational Geometry - SCG '09*, page 377, Aarhus, Denmark, 2009. ACM Press. doi:10.1145/1542362.1542426.
[15] 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.

[16] 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.

[17] Chao Chen and Daniel Freedman. Hardness Results for Homology Localization. *Discrete & Computational Geometry*, 45(3):425–448, April 2011. doi:10.1007/s00454-010-9322-8.

[18] L. Chen and M. Holst. Efficient mesh optimization schemes based on optimal delaunay triangulations. *Computer Methods in Applied Mechanics and Engineering*, 200(9):967–984, 2011.

[19] Long Chen. Mesh smoothing schemes based on optimal delaunay triangulations. In *Proceedings of the 13th International Meshing Roundtable, IMR 2004, Williamsburg, Virginia, USA, September 19-22, 2004*, pages 109–120, 2004. URL: http://imr.sandia.gov/papers/abstracts/Ch317.html.

[20] Long Chen and Jin-chao Xu. Optimal delaunay triangulations. *Journal of Computational Mathematics*, pages 299–308, 2004.

[21] Zhonggui Chen, Wenping Wang, Bruno Lévy, Ligang Liu, and Feng Sun. Revisiting optimal delaunay triangulation for 3d graded mesh generation. *SIAM Journal on Scientific Computing*, 36(3):A930–A954, 2014.

[22] David Cohen-Steiner, André Lieutier, and Julien Vuillamy. Regular triangulations as lexicographic optimal chains. Preprint HAL: hal-02391285, 2019.

[23] Tamal K. Dey, Anil N. Hirani, and Bala Krishnamoorthy. Optimal Homologous Cycles, Total Unimodularity, and Linear Programming. *SIAM Journal on Computing*, 40(4):1026–1044, January 2011. doi:10.1137/100800245.

[24] Tamal K. Dey, Tao Hou, and Sayan Mandal. Computing minimal persistent cycles: Polynomial and hard cases. In *Proceedings of the Thirty-First Annual ACM-SIAM Symposium on Discrete Algorithms*, SODA '20, pages 2587–2606, USA, January 2020. Society for Industrial and Applied Mathematics.

[25] H. Edelsbrunner. *Geometry and topology for mesh generation*. Cambridge Univ Pr, 2001.

[26] Herbert Edelsbrunner and Nimish R Shah. Incremental topological flipping works for regular triangulations. *Algorithmica*, 15(3):223–241, 1996.

[27] H. Federer. Curvature measures. *Trans. Amer. Math. Soc*, 93:418–491, 1959.

[28] Robert L Foote. Regularity of the distance function. *Proceedings of the American Mathematical Society*, 92(1):153–155, 1984.

[29] Victor Guillemin and Alan Pollack. *Differential topology*, volume 370. American Mathematical Soc., 2010.

[30] Camille Jordan. Essai sur la géométrie à n dimensions. *Bulletin de la Société Mathématique de France*, 3:103–174, 1875. URL: http://www.numdam.org/item/BSMF_1875__3__103_2, doi:10.24033/bsmf.90.
[31] Jisu Kim, Jaehyeok Shin, Frédéric Chazal, Alessandro Rinaldo, and Larry Wasserman. Homotopy reconstruction via the cech complex and the vietoris-rips complex. *arXiv preprint arXiv:1903.06955*, 2019.

[32] John Milnor. *Morse theory.* (AM-51), volume 51. Princeton university press, 2016.

[33] Frank Morgan. *Geometric measure theory: a beginner's guide.* Academic press, 2016.

[34] Robin A Moser and Gábor Tardos. A constructive proof of the general lovász local lemma. *Journal of the ACM (JACM)*, 57(2):1-15, 2010.

[35] J.R. Munkres. *Elements of algebraic topology*. Perseus Books, 1993.

[36] Oleg R Musin. Properties of the delaunay triangulation. In *Proceedings of the thirteenth annual symposium on Computational geometry*, pages 424-426, 1997.

[37] 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.

[38] Samuel Rippa. Minimal roughness property of the delaunay triangulation. *Computer Aided Geometric Design*, 7(6):489-497, 1990.

[39] Julien Vuillamy. *Simplification planimétrique et chaînes lexicographiques pour la reconstruction 3D de scènes urbaines*. PhD thesis, Université Côte d'Azur, 2021.

[40] H. Whitney. *Geometric integration theory*. Dover Publications, 2005.

[41] Sibylle Zeller and Maximilian Thaler. Almost sure escape from the unit interval under the logistic map. *American Mathematical Monthly*, pages 155-158, 2001.
A Additional lemmas and a missing proof

Proof of Lemma 6. Let $\alpha = \{a_0, a_1, \dots, a_d\} \subseteq \mathbb{R}^N$. If $\alpha$ is degenerate, then $\mathrm{vol}(\alpha) = 0$ and the result is clear. Suppose that $\alpha$ is non-degenerate and recall that the standard simplex is

$$ \Delta_d = \{\lambda \in \mathbb{R}^d \mid \sum_{i=1}^d \lambda_i \le 1; \lambda_i \ge 0, i = 1, 2, \dots, d\}. $$

We introduce the map $\psi : \mathbb{R}^d \to \mathbb{R}^d$, defined by $\psi(\lambda) = a_0 + \sum_{i=1}^d \lambda_i(a_i - a_0)$, which establishes a one-to-one correspondence between the points $\lambda$ of the standard simplex $\Delta_d$ and the points $x = \psi(\lambda)$ of conv $\alpha$. Making the change of variable $x = \psi(\lambda) \to \lambda$, we get that:

$$ w(\alpha) = \int_{\lambda \in \Delta_d} -\mathrm{Power}_{\alpha}(\psi(\lambda)) \cdot |\det(J\psi)(\lambda)| d\lambda. $$

Noting that $J\psi(\lambda)$ is the matrix whose $i$th column is the vector $a_i - a_0$, we deduce that $|\det(J\psi)(\lambda)| = d! \mathrm{vol}(\alpha)$. Observing that $\psi(\lambda)$ has absolute barycentric coordinates $(1 - \sum_{i=1}^d \lambda_i, \lambda_1, \lambda_2, \dots, \lambda_d)$ and applying Lemma 16 with $z = a_0$, we can write:

$$ \mathrm{Power}_{\alpha}(\psi(\lambda)) = - \left( \sum_{i=1}^{d} \lambda_i \|a_i - a_0\|^2 \right) + \|\psi(\lambda) - a_0\|^2, $$

and thus obtain (after plugging in the expression of $\psi(\lambda)$)

$$ w(\alpha) = d! \mathrm{vol}(\alpha) \int_{\lambda \in \Delta_d} \left[ \sum_{i=1}^{d} \lambda_i \|a_i - a_0\|^2 - \left\| \sum_{i=1}^{d} \lambda_i (a_i - a_0) \right\|^2 \right] d\lambda. $$

We then use the following formula [41] for integrating a homogeneous polynomial on the standard simplex:

$$ \int_{\lambda \in \Delta_d} \lambda_1^{\eta_1} \dots \lambda_d^{\eta_d} d\lambda = \frac{\eta_1! \dots \eta_d!}{(d + \sum_i \eta_i)!}, $$

to obtain that

$$ w(\alpha) = \frac{1}{(d+1)(d+2)} \mathrm{vol}(\alpha) \left[ d \sum_{i=1}^{d} \|a_i - a_0\|^2 - 2 \sum_{1 \le i < j \le d} (a_i - a_0) \cdot (a_j - a_0) \right]. $$

Observing that $\|a_i - a_0\|^2 + \|a_j - a_0\|^2 - 2(a_i - a_0) \cdot (a_j - a_0) = \|a_i - a_j\|^2$, we can further rearrange the above formula to get the result. $\square$

The next lemma says that if a subset $\sigma \subseteq \mathbb{R}^N$ is sufficiently small and sufficiently close to a subset $A \subseteq \mathbb{R}^N$ compare to its reach, then the convex hull of $\sigma$ is not too far away from A. The lemma will be useful to provide conditions under which the map $\pi_A|_{\mathrm{conv} \sigma}$ is well-defined.

**Lemma 23.** Let $16\delta \le \rho \le \frac{\mathrm{reach} A}{3}$. If the subset $\sigma \subseteq A^{\oplus\delta}$ is $\rho$-small, then $\mathrm{conv} \sigma \subseteq A^{\oplus\frac{\rho}{4}}$.

*Proof.* Let $\mathcal{R} = \mathrm{reach} A$. Applying Lemma 14 in [3], we get that $\mathrm{conv} \sigma \subseteq A^{\oplus r}$ for $r = \mathcal{R} - \sqrt{(\mathcal{R} - \delta)^2 - \rho^2}$. Since $\delta \le \frac{\rho}{16\mathcal{R}}$, we deduce that $\frac{r}{\mathcal{R}} \le 1 - \sqrt{(1 - \frac{\rho}{16\mathcal{R}})^2 - \frac{\rho^2}{\mathcal{R}^2}}$ and since for all $0 \le t \le \frac{1}{3}$ we have $1 - \sqrt{(1 - \frac{t}{16})^2 - t^2} \le \frac{t}{4}$, we obtain the result. $\square$
**Lemma 24** (Injectivity of $\pi_{\text{aff}\alpha}|_{P\cap B(c_{\alpha}, \rho)}$). Suppose that $P \subseteq \mathcal{M}^{\oplus\delta}$ with $16\delta \le \rho \le \frac{\mathcal{R}}{3}$ and separation($P$) $> \frac{3\rho^2}{\mathcal{R}} + 3\delta$. Consider a $\rho$-small $d$-simplex $\alpha \subseteq P$ such that $\Theta(\alpha) \le \frac{\pi}{6}$. Then, $\pi_{\text{aff}\alpha}|_{P\cap B(c_{\alpha}, \rho)}$ is injective.

*Proof.* Let $c_{\alpha}^* = \pi_{\mathcal{M}}(c_{\alpha})$. Consider two points $a, b \in P \cap B(c_{\alpha}, \rho)$. We have $\cos(\text{aff } \alpha, ab) \cdot \|a - b\| \le \|\pi_{\text{aff } \alpha}(a) - \pi_{\text{aff } \alpha}(b)\|$, showing that the restriction of $\pi_{\text{aff } \alpha}$ to $B(c_{\alpha}, \rho)$ is injective as soon as $\angle(\text{aff } \alpha, ab) < \frac{\pi}{2}$. Applying Lemma 36 with $\tau = \{a, b\}$ and $z = c_{\alpha}$, we obtain that $\angle(\text{aff } \alpha, ab)$ is upper bounded by

$$ 
\begin{aligned}
\angle(\text{aff } \alpha, ab) &\le \angle(\text{aff } \alpha, \mathbf{T}_{c_{\alpha}^*} \mathcal{M}) + \angle(\mathbf{T}_{c_{\alpha}^*} \mathcal{M}, ab) \\
&\le \Theta(\alpha) + \arcsin\left(\frac{2}{\|a-b\|}\left(\frac{\rho^2}{\mathcal{R}} + \delta\right)\right) \\
&\le \frac{\pi}{6} + \arcsin\left(\frac{2}{\text{separation}(P)}\left(\frac{\rho^2}{\mathcal{R}} + \delta\right)\right)
\end{aligned}
$$

and thus becomes smaller than $\frac{\pi}{2}$ for separation($P$) $> \frac{3\rho^2}{\mathcal{R}} + 3\delta$. $\square$

## B Angle between affine spaces

If $V_1$ and $V_2$ are two vector subspaces of a same euclidean space then their angle $\angle V_1, V_2 \in [0, \pi/2]$ is defined as:

**Definition 25.** The angle between two vector subspaces $V_1$ and $V_2$ of a same euclidean space is defined as (see also [30]):

$$ 
\begin{aligned}
\angle V_1, V_2 &= \sup_{\text{def.}} \inf_{v_1 \in V_1, v_2 \in V_2} \angle v_1, v_2 = \max_{v_1 \in V_1, v_2 \in V_2} \min_{v_1 \in V_1, v_2 \in V_2} \angle v_1, v_2 \\
\|v_1\| = 1 &\quad \|v_2\| = 1 &\quad \|v_1\| = 1 &\quad \|v_2\| = 1
\end{aligned}
\quad (13) $$

The angle between affine subspaces $A_1$ and $A_2$ is defined as the angle between associated vector spaces.

One gets trivially the equivalent definition:

$$ \angle V_1, V_2 = \inf \{ \theta \ge 0, \forall v_1 \in V_1 \setminus \{0\}, \exists v_2 \in V_2 \setminus \{0\}, \angle v_1, v_2 \le \theta \} \quad (14) $$

Since when $\dim V_1 = \dim V_2$ there is an isometry (mirror symmetry) that swaps $V_1$ and $V_2$ and preserves angles we have:

$$ \dim V_1 = \dim V_2 \Rightarrow \angle V_1, V_2 = \angle V_2, V_1 $$

and one gets from (14) and the triangular inequality on angles between vectors that:

$$ \angle V_1, V_3 \le \angle V_1, V_2 + \angle V_2, V_3 $$

The remainder of section B is classical, see [30] (Also the Wikipedia page "Angles between flats") .But Lemma 28 allows an explicit expression of the path of the orthonormal frame.

**Lemma 26** (Minimal angle corresponds to orthogonal projection). Let $V \subseteq \mathbb{R}^N$ be a vector subspace and $\pi_V$ the orthogonal projection on $V$. Let $v' \in \mathbb{R}^N$ a vector such that $\|v'\| = 1$, $\pi_V(v') \ne 0$ and $\theta = \min_{v^* \in V, \|v^*\|=1} \angle v^*, v'$. Then

$$ \arg \min_{v^* \in V, \|v^*\|=1} \angle v^*, v' = \frac{1}{\cos \theta} \pi_V(v') $$
Proof. One has by definition of $\pi_V$:

$$ \pi_V(v') = \arg \min_{v^* \in V} (v^* - v')^2 \quad (15) $$

and since $\|v'\| = 1$ and $\pi_V(v') - v'$ is orthogonal to $V$, one has $(\pi_V(v') - v')^2 = (\sin \angle \pi_V(v'), v')^2$. Also, for any vector $v^* \neq 0$, one has $(\sin \angle v^*, v')^2 = \min_{\lambda}(\lambda v^* - v')^2$ so that (15) implies that $\pi_V(v')$ (as well as all its positively collinear vectors) minimises $v^* \to \sin^2 \angle v^*, v'$ in $V$. It follows that $\pi_V(v')$ is collinear to $\arg \min_{v^* \in V, \|v^*\|=1} \angle v^*, v'$ and since its norm is $\cos \theta$ we get the result. $\square$

If $V$ is a vector subspace of $\mathbb{R}^N$, and $\pi_V$ the orthogonal projection on $V$ then it is well known that:

* $\pi_V$ is self-adjoint and therefore its matrix in any orthonormal frame is symmetric.

* $\pi_V \circ \pi_V = \pi_V$

* the kernel of $\pi_V$ is the vector space normal to $V$ and its restriction to $V$ is the identity.

Let $V$ and $V'$ be two $d$-dimensional vector subspaces of $\mathbb{R}^N$ such that $\theta = \angle V', V < \pi/2$ and let $\pi_V$ and $\pi_{V'}$ be their corresponding orthogonal projections. Thanks to Lemma 26, and since $\cos \theta$ is decreasing on $[0, \pi/2]$, one has:

$$ \cos \theta = \min_{v' \in V', \|v'\|=1} \|\pi_V(v')\| $$

So that, since $v' \in V' \Rightarrow v' = \pi_{V'}(v')$:

$$ (\cos \theta)^2 = \min_{v' \in V', \|v'\|=1} \langle \pi_V \circ \pi_{V'}(v') | \pi_V \circ \pi_{V'}(v') \rangle $$

Denoting $M_V$ and $M_{V'}$ the respective symmetric matrix of $\pi_V$ and $\pi_{V'}$ in some orthonormal basis it gives, since $M_V M_V = M_V$:

$$ \begin{aligned} (\cos \theta)^2 &= \min_{v' \in V', \|v'\|=1} (M_V M_{V'} v')^t M_V M_{V'} v' \\ &= \min_{v' \in V', \|v'\|=1} v'^t M_{V'}^t M_V M_V M_{V'} v' \\ &= \min_{v' \in V', \|v'\|=1} v'^t M_{V'}^t M_V M_{V'} v' \end{aligned} $$

Since $M_{V'}^t = M_{V'}$ and $v' \in V' \Rightarrow M_{V'} v' = v'$:

$$ (\cos \theta)^2 = \min_{v' \in V', \|v'\|=1} v'^t M_{V'} M_V v' $$

Let $A_{V'}: V \to V'$ be the restriction of $M_{V'}$ to $V$ and $A_V: V' \to V$ the restriction of $M_V$ to $V'$. One has:

$$ (\cos \theta)^2 = \min_{v' \in V', \|v'\|=1} v'^t A_{V'} A_V v' \quad (16) $$

Since $M_{V'}^t M_V M_V M_{V'}: \mathbb{R}^N \to V' \subseteq \mathbb{R}^N$ is self-adjoint, so is its restriction $C' = A_{V'} A_V: V' \to V'$. It follows that $C'$ has $d$ (counting multiplicities) real eigenvalues, associated to $d$ eigenvectors of $C'$ making an orthogonal basis of $V$, and (16) is the Rayleigh quotient of $C'$ which gives that the smallest eigenvalue of $C'$ is $(\cos \theta)^2$. Since $\theta < \pi/2$ we have that all eigenvalues of $C'$ are positive, in particular $C'$ is invertible.
It follows that $A_V$ and $A_{V'}$ have rank $d$ and are also invertible so that $C = A_V A_{V'} : V \to V$ is also invertible. If $v'_i$ is an eigenvector of $C'$ with eigenvalue $\lambda_i$, then $C'v'_i = A_{V'} A_V v'_i = \lambda_i v'_i$ and:

$$A_V A_{V'} A_V v'_i = \lambda_i A_V v'_i \qquad (17)$$

Since $A_V$ is invertible, $A_V v'_i \neq 0$ and (17) says that $v_i = A_V v'_i$ is an eigenvector of $C = A_V A_{V'}$ with eigenvalue $\lambda_i$:

$$C v_i = A_V A_{V'} v_i = \lambda_i v_i$$

Also, since $A_V$ and $A_{V'}$ have their $L^2$ operator norms upper bounded by 1, so is the operator norm of $C$ and $C'$. We have shown that:

**Lemma 27.** *The restriction to $V'$ of the orthogonal projection on $V$, sends an orthogonal basis of $V'$ made of eigenvectors of $C' = A_{V'} A_V$ to an orthogonal basis of $V$ made of eigenvectors of $C = A_V A_{V'}$ with same the eigenvalues. These eigenvalues are included in $[(\cos \theta)^2, 1]$ with the smallest one equal to $(\cos \theta)^2$.*

**Lemma 28** (Rotation between two vector spaces). Let $V$ and $V'$ be $d$-dimensional vector subspaces of Euclidean space such that the angle $\theta = \angle V, V'$ satisfies:

$$0 < \angle V, V' < \frac{\pi}{2}$$

and $d' = d - \dim(V \cap V')$.

Then there is an orthonormal basis $v_1, \dots, v_{d'}, v'_1, \dots, v'_{d'}, w_1, \dots, w_{d-d'}$ and a sequence of angles $\theta_1 \ge \theta_2 \ge \dots, \theta_{d'} > 0$ such that $\theta_1 = \theta$,

$$v_1, \dots, v_{d'}, w_1, \dots, w_{d-d'}$$

is a basis of $V$ and:

$$\cos \theta_1 v_1 + \sin \theta_1 v'_1, \dots, \cos \theta_{d'} v_{d'} + \sin \theta_{d'} v'_{d'}, w_1, \dots, w_{d-d'}$$

is a basis of $V'$.

*Proof.* We first claim that, for $v \in V$ one has:

$$Cv = v \iff A_{V'}v = v \iff v \in V \cap V' \qquad (18)$$

Indeed, if $v \in V \cap V'$ one has trivially $A_{V'}v = v$ and $Cv = A_V A_{V'}v = A_V v = v$. In the other direction, if $CV = A_V A_{V'}v = v$, since the operator norm of $A_{V'}$ is 1, one must have $\|A_{V'}v\| \le \|v\|$ and, since the operator norm of $A_V$ is 1, one must have $\|v\| = \|A_V A_{V'}v\| \le \|A_{V'}v\|$. Therefore one has $\|A_{V'}v\| = \|v\|$. But since $\|A_{V'}v\| = \|v\| \cos \angle v, A_{V'}v$ we get $\cos \angle v, A_{V'}v = 1$ and $\angle v, A_{V'}v = 0$. This with $\|A_{V'}v\| = \|v\|$ gives $A_{V'}v = v \in V \cap V'$.

It follows from (18) that the eigenspace of $C$ corresponding to the eigenvalue 1 coincides with $V \cap V'$. We sort the eigenvalues of $C$ in increasing order (see Lemma 27):

$$(\cos \theta)^2 = \lambda_1 \le \lambda_2 \le \dots \le \lambda_d,$$

with $\lambda_{d'+1} = \dots = \lambda_d = 1$ for $d' = d - \dim(V \cap V')$.

For any $k$, $1 \le k \le d'$, we define $v_k$ as an unit eigenvector associated$^3$ to the eigenvalue $\lambda_k$. For any $l$, $1 \le l \le d - d'$ we define $w_l \in V \cap V'$ such that $w_1, \dots, w_{d-d'}$ is an orthonormal basis of

<footnote>$^3$For multiple eigenvalues we choose orthogonal unit vectors as the eigenspace basis.</footnote>
$V \cap V'$, where $w_l$ is associated to the eigenvalue $\lambda_{d'+l} = 1$ by (18). Then $(v_1, \dots, v_{d'}, w_1, \dots, w_{d-d'})$ is an orthonormal basis of $V$ and, from (18), $(w_l)_{d' \le l \le d}$ is an orthonormal of $V \cap V'$.

For $1 \le k \le d'$ define $\theta_k$ as $\theta_k = \angle v_k, A_{V'}v_k$. We have seen that $\theta_1 = \theta$ and one has $0 < \theta_k \le \theta < \pi/2$ and:

$$ \theta_k = \angle v_k, A_{V'}v_k = \angle \lambda_k v_k, A_{V'}v_k = \angle C v_k, A_{V'}v_k = \angle A_V(A_{V'}v_k), A_{V'}v_k $$

It follows that:

$$ \lambda_k \|v_k\| = \|C v_k\| = \cos \theta_k \|A_{V'} v_k\| = \cos^2 \theta_k \|v_k\| $$

So that $(\cos \theta_k)^2 = \lambda_k$.

We define now for $1 \le k \le d'$:

$$ v'_{k} = \frac{A_{V'} v_{k} - \langle v_{k}, A_{V'} v_{k} \rangle v_{k}}{\|A_{V'} v_{k} - \langle v_{k}, A_{V'} v_{k} \rangle v_{k}\|} $$

where the denominator is no zero since $\theta_k > 0$. One has by construction that $\|v'_k\| = 1$, $v'_k$ is orthogonal to $v_k$ and:

$$ \frac{A_{V'} v_k}{\|A_{V'} v_k\|} = \cos \theta_k v_k + \sin \theta_k v'_k \quad (19) $$

Since $\left( \left( \frac{A_{V'} v_k}{\|A_{V'} v_k\|} \right)_{1 \le k \le d'}, w_1, \dots, w_{d-d'} \right)$ are unit eigenvectors of $C'$ they form an orthonormal basis of $V'$. In order to complete the proof, it remains to prove that, for $k' \neq k$, $v_k$ is orthogonal to $v'_{k'}$. One has from (19), using that $A_V A_{V'} v_k = \cos^2 \theta_k v_k$ and $\|A_{V'} v_k\| = \cos \theta_k$:

$$ \begin{aligned} \sin \theta_k v'_k &= \frac{A_{V'} v_k}{\|A_{V'} v_k\|} - \cos \theta_k v_k = \frac{A_{V'} v_k}{\|A_{V'} v_k\|} - \cos \theta_k \frac{A_V (A_{V'} v_k)}{\cos^2 \theta_k} \\ &= \frac{A_{V'} v_k}{\|A_{V'} v_k\|} - A_V \left( \frac{A_{V'} v_k}{\|A_{V'} v_k\|} \right) \end{aligned} $$

Recall that $A_V$ is the orthogonal projection on $V$ and the last equality shows then that $v'_k$ is orthogonal to $V$ and therefore orthogonal to any $v_{k'}$ for $1 \le k' \le d'$. $\square$

## C $C^2$-submanifold of Euclidean space

We recall the definition of a smooth submanifold. (https://maths-people.anu.edu.au/~andrews/DG/DG_chap3.pdf).

**Definition 29.** A subset $\mathcal{M}$ of $\mathbb{R}^N$ is a $C^2$ $d$-dimensional submanifold if for every point $x$ in $\mathcal{M}$ there exists a neighborhood $V$ of $x$ in $\mathbb{R}^N$, an open set $U \subseteq \mathbb{R}^d$ and a $C^2$ map $\xi: U \to \mathbb{R}^N$ such that $\xi$ is a homeomorphism onto $\mathcal{M} \cap V$, and $D_y\xi$ is injective for every $y \in U$.

A $C^2$ $d$-dimensional submanifold is a $C^2$ manifold topologically embedded in $\mathbb{R}^N$ but the converse in not true in general, as for example the circle $\mathbb{S}^1$ is a $\mathcal{C}^\infty$ manifold that can be topologically embedded as a square in $\mathbb{R}^2$ as the image by a $\mathcal{C}^\infty$ map that is not regular (i.e. whose derivative is not injective) at the pre-images of the square corners. A compact $C^2$ submanifold has positive reach [27]. Moreover one has (see for example Lemma 4 and following paragraph in [10] or Proposition 2.3 in[1]) that:

**Lemma 30** (The inverse of the reach bounds the curvature). If $\mathcal{M} \subseteq \mathbb{R}^N$ is a $C^2$ $d$-dimensional submanifold with reach($\mathcal{M}$) > 0 then $1/\text{reach}(\mathcal{M})$ bounds the (absolute values of the) principal curvatures at $m \in \mathcal{M}$ in the direction $v$ for any vector $v$ in the space normal to $\mathcal{M}$ at $m$. In particular $1/\text{reach}(\mathcal{M})$ bounds the principal curvatures when $\mathcal{M}$ has codimension 1.
The following lemma, due to Federer, bounds the distance of a point $q \in \mathcal{M}$ to the tangent space at a point $p \in \mathcal{M}$. It holds for any set with positive reach and in particular for $C^2$ submanifolds.

**Lemma 31** (Distance to tangent space, Theorem 4.8(7) of [27]). Let $p, q \in \mathcal{M} \subseteq \mathbb{R}^N$ such that $\|p - q\| < \text{reach}(\mathcal{M})$. We have

$$ \sin \angle([pq], T_p\mathcal{M}) \le \frac{\|p - q\|}{2 \text{ reach}(\mathcal{M})}, \qquad (20) $$

and

$$ d(q, T_p\mathcal{M}) \le \frac{\|p - q\|^2}{2 \text{ reach}(\mathcal{M})}. \qquad (21) $$

Next lemma bounds the angle variation for $C^2$ manifolds (a slightly weaker condition if given for $C^{1,1}$ manifolds in the same paper):

**Lemma 32** (Corollary 3 in [10]). For any $p, q \in \mathcal{M}$, we have

$$ \sin \left( \frac{\angle(T_p\mathcal{M}, T_q\mathcal{M})}{2} \right) \le \frac{\|p - q\|}{2 \text{ reach}(\mathcal{M})}. $$

Using Lemmas 31 and 32 we can show that the projection on a tangent space defines a local chart for $\mathcal{M}$. Indeed, if $m \in \mathcal{M}$ then for any $p, q \in \mathcal{M} \cap B(m, \sin(\pi/4) \text{ reach} \mathcal{M})$, (20) gives:

$$ \sin \angle([pq], T_p\mathcal{M}) \le \frac{\|p - q\|}{2 \text{ reach}(\mathcal{M})} \le \frac{2 \sin(\pi/4) \text{ reach} \mathcal{M}}{2 \text{ reach}(\mathcal{M})} = \sin(\pi/4) $$

So that:

$$ \angle([pq], T_p\mathcal{M}) \le \pi/4, \qquad (22) $$

and Lemma 32 gives:

$$ \sin \left( \frac{\angle(T_p\mathcal{M}, T_m\mathcal{M})}{2} \right) \le \frac{\|p - m\|}{2 \text{ reach}(\mathcal{M})} \le \frac{\sin(\pi/4) \text{ reach}(\mathcal{M})}{2 \text{ reach}(\mathcal{M})} = \frac{\sin(\pi/4)}{2} $$

so that:

$$ \angle(T_p\mathcal{M}, T_m\mathcal{M}) \le 2 \arcsin \left( \frac{\sin(\pi/4)}{2} \right) < \pi/4 $$

Summing with (22) gives:

$$ \angle([pq], T_m\mathcal{M}) < \pi/2 $$

and this in turn implies:

$$ p \ne q \Rightarrow \pi_{T_m\mathcal{M}}(p) \ne \pi_{T_m\mathcal{M}}(q) $$

We have shown that the restriction of $\pi_{T_m\mathcal{M}}$ to $\mathcal{M} \cap B(m, \sin(\pi/4) \text{ reach} \mathcal{M})$ is injective, and, by Invariance of Domain Theorem ([13]), it is an homeomorphism on its image, which gives us:

**Lemma 33** (Projection on tangent space is a local chart). If $\mathcal{M}$ is a compact $C^2$ submanifold of Euclidean space, and $m \in \mathcal{M}$ then, identifying $T_m\mathcal{M}$ with $\mathbb{R}^d$ through a given frame, the restriction of $\pi_{T_m\mathcal{M}}$ to $\mathcal{M} \cap B(m, \sin(\pi/4) \text{ reach} \mathcal{M})^\circ$ is a local chart of $\mathcal{M}$. Moreover, for any $p \in \mathcal{M} \cap B(m, \sin(\pi/4) \text{ reach} \mathcal{M})^\circ$, one has:

$$ \angle(T_p\mathcal{M}, T_m\mathcal{M}) < \pi/4 $$
Following [9, Notation 1.1], we call Thickness of a k-simplex:

$$t(\sigma) = \frac{h}{kL}$$

where h is the smallest altitude of σ and L the length of the longest edge. Then we have (adaptation of [40, Section IV.15], proven in [7, Lemma 8.11]):

**Lemma 34** (Angle between simplices tangent space). If $\mathcal{M}$ is a compact $\mathbb{C}^2$ submanifold of Euclidean space, $\sigma$ a d-simplex with vertices in $\mathcal{M}$, and $p$ a vertex of $\sigma$: then:

$$\angle \operatorname{aff} \sigma, T_p \mathcal{M} \le \frac{L}{t(\sigma) \operatorname{reach} \mathcal{M}} = \frac{dL^2}{h \operatorname{reach} \mathcal{M}}$$

We shall also need the Whitney angle bound established in [8].

**Lemma 35** (Whitney angle bound [8, Lemma 2.1]). Consider a d-dimensional affine space $H$ and a simplex $\sigma$ such that $\dim \sigma \le d$ and $\sigma \subseteq H^{\oplus t}$ for some $t \ge 0$. Then

$$\sin \angle (\operatorname{aff} \sigma, H) \le \frac{2t \dim(\sigma)}{\operatorname{height}(\sigma)}$$

Building on these results, we derive yet another bound between the affine space spanned by a simplex and a nearby tangent space.

**Lemma 36.** Consider a non-degenerate $\rho$-small simplex $\tau \subseteq \mathcal{M}^{\oplus \delta}$ with $16\delta \le \rho \le \frac{\mathbb{R}}{3}$. Let $z$ be a point such that $\tau \subseteq B(z, \rho)$ and $d(z, \mathcal{M}) \le \frac{\rho}{4}$. Then,

$$\angle (\operatorname{aff} \tau, \mathbf{T}_{\pi_{\mathcal{M}}(z)}\mathcal{M}) \le \arcsin \left( \frac{2 \dim(\tau)}{\operatorname{height}(\tau)} \left( \frac{\rho^2}{\mathcal{R}} + \delta \right) \right).$$

*Proof.* Let $v \in \tau$. Write $v^* = \pi_{\mathcal{M}}(v)$ and $z^* = \pi_{\mathcal{M}}(z)$. We know from [27, page 435] that for $0 \le h < \operatorname{reach} \mathcal{M}$, the projection map $\pi_{\mathcal{M}}$ onto $\mathcal{M}$ is $(\frac{\mathbb{R}}{\mathcal{R}-h})$-Lipschitz for points at distance less than $h$ from $\mathcal{M}$. Since both $z$ and $v$ belong to $\mathcal{M}^{\oplus h}$ for $h = \frac{\rho}{4}$, we thus have

$$\|v^* - z^*\| \le \frac{\mathcal{R}}{\mathcal{R} - \frac{\rho}{4}} \times \|v - z\| \le \frac{\mathcal{R}}{\mathcal{R} - \frac{\mathcal{R}}{3 \times 4}} \times \|v - z\| \le \sqrt{2\rho}.$$

Applying Lemma 31, we get that

$$d(v, \mathbf{T}_{z^*} \mathcal{M}) \le d(v^*, \mathbf{T}_{z^*} \mathcal{M}) + \|v - v^*\| \le \frac{\|v^* - z^*\|^2}{2\mathcal{R}} + \delta \le \frac{\rho^2}{\mathcal{R}} + \delta.$$

Hence, $\tau \subseteq (\mathbf{T}_{z^*} \mathcal{M})^{\oplus t}$ for $t = \frac{\rho^2}{\mathcal{R}} + \delta$ and applying Whitney angle bound (Lemma 35), we conclude that $\sin \angle (\operatorname{aff} \tau, \mathbf{T}_{z^*} \mathcal{M}) \le \frac{2 \dim(\tau)}{\operatorname{height}(\tau)} \left( \frac{\rho^2}{\mathcal{R}} + \delta \right)$. $\square$

# D Smooth local parametrization of the normal bundle

Let $\mathcal{M} \subseteq \mathbb{R}^N$ be a $\mathbb{C}^2$ d-dimensional submanifold with reach greater than $\rho > 0$. If $x \in \mathcal{M}$, the vector spaces $T_x \mathcal{M}$ and $N_x \mathcal{M}$ are the respective tangent and normal spaces to $\mathcal{M}$ at $x$. To avoid confusion, we denote by $\mathbf{T}_x \mathcal{M}$ and $\mathbf{N}_x \mathcal{M}$ the corresponding affine subspaces of ambient $\mathbb{R}^N$: $\mathbf{T}_x \mathcal{M} = x + T_x \mathcal{M}$ and $\mathbf{N}_x \mathcal{M} = x + N_x \mathcal{M}$.
We denote by $\mathcal{M}^{\oplus \rho}$ the $\rho$-tubular neighborhood of $\mathcal{M}$. The normal bundle of $\mathcal{M}$ is denoted $NM$ and defined as:

$$NM = \coprod_{\text{def.}} N_x \mathcal{M}$$

where $\coprod$ is the disjoint union. The normal bundle restricted to radius $\rho$ is denoted $N^\rho \mathcal{M}$:

$$N^\rho \mathcal{M} = \coprod_{\text{def.}} \{(x, v) \in N_x \mathcal{M}, \|v\| \le \rho\}$$

We know from [27][Item (13) of Theorem 4.8] that, since $\rho < \text{reach} \mathcal{M}$, the map $\Psi : \mathcal{M}^{\oplus \rho} \to N^\rho \mathcal{M} \subseteq \mathbb{R}^N \times \mathbb{R}^N$ defined by:

$$\Psi(y) = (\pi_{\mathcal{M}}(y), y - \pi_{\mathcal{M}}(y))$$

is a Lipschitz homeomorphism between $\mathcal{M}^{\oplus \rho}$ and $N^\rho \mathcal{M}$ whose inverse $\sigma : N^\rho \mathcal{M} \to \mathcal{M}^{\oplus \rho}$ defined as

$$\sigma(x, v) = x + v \qquad (23)$$

is Lipschitz as well. We have [28] that inside $\mathcal{M}^{\oplus \rho}$ the distance function $d_{\mathcal{M}}$ is $C^2$ and the projection $\pi_{\mathcal{M}}$ is $C^1$. It follows that $\Psi$ is $C^1$ and since its inverse is Lipschitz, its Jacobian cannot be singular. It follows that $\Psi$ is a $C^1$ diffeomorphims between $\mathcal{M}^{\oplus \rho}$ and $N^\rho \mathcal{M}$.

For $x \in \mathcal{M}$ we consider an open neighborhood $U_0$ of 0 in $\mathbb{R}^d$ and a $C^2$ injective map $\xi : U_0 \to \mathcal{M}$, regular in the sense that differential $(\frac{d\xi}{du^j}(u))_{j=1,d}$ has rank $d$ for any $u \in U_0$, and such that $\xi(0) = x$. Let us choose $\xi$ such that, moreover, $(\frac{d\xi}{du^j}|_{u=0})_{j=1,d}$ forms an orthonormal basis of $T_x \mathcal{M}$.

Also, we consider, as in the proof of Lemma 6.3 of [32], a set of $(N-d) C^1$-smooth vector valued maps $(w_k)_{k=1...N-d}$, where $w_k : U_0 \to \mathbb{R}^N$ and such that, for any $u \in U_0$, $(w_k(u))_{k=1,N-d}$ is an orthonormal basis of $N_{\xi(u)} \mathcal{M}$.

As done by J.Milnor in [32, paragraph 6, proof of Lemma 6.3], $\xi$ and $(w_k)_{k=1...N-d}$ defines a local trivialization of the normal bundle $NM$, that is a chart $\phi$ of $NM$ in the neighborhood of $(x, 0)$ where the parameter $(u^1, ..., u^d, t^1, ..., t^{N-d}) \in U_0 \times \mathbb{B}^{N-d}(0, \rho)$ corresponds to the point:

$$\phi(u, t) = \phi(u^1, \dots, u^d, t^1, \dots, t^{N-d}) \\ = \left( \xi(u^1, \dots, u^d), \sum_{k=1}^{N-d} t^k w_k(u^1, \dots, u^d) \right) \in N^\rho \mathcal{M}$$

and

$$\sigma \circ \phi(u, t) = \xi(u^1, \dots, u^d) + \sum_{k=1}^{N-d} t^k w_k(u^1, \dots, u^d) \in \mathcal{M}^{\oplus \rho} \subseteq \mathbb{R}^N \qquad (24)$$

Derivating (24) at $u = 0$ gives:

$$\frac{d}{du^j}|_{u=0} \sigma \circ \phi(u, t) = \frac{d\xi}{du^j}|_{u=0} + \sum_{k=1}^{N-d} t^k \frac{dw_k}{du^j}|_{u=0} \qquad (25)$$

$$\frac{d}{dt^k}|_{u=0} \sigma \circ \phi(u, t) = w_k(0) \qquad (26)$$
In order to express the derivative of $\sigma : N^\rho M \to M^{\oplus \rho}$ at point $(x, v) \in N^\rho M$ we need, besides the chart $\phi$ of a neighborhood of $(x, v)$, a chart $\hat{\phi}$ of a neighborhood of $\sigma(x, v) = x + v$ in euclidean space. A natural choice for $\hat{\phi}$ is

$$ \hat{\phi}(y) = \hat{\phi}(y^1, \dots, y^N) = x + v + \sum_{k=1}^{d} y^k \frac{d\xi}{du^k}|_{u=0} + \sum_{k=1}^{N-d} y^{d+k} w_k $$

Observe that, since $(\frac{d\xi}{du^1}|_{u=0}, \dots, \frac{d\xi}{du^d}|_{u=0}, w_1, \dots, w_{N-d})$ is an orthonormal basis, seeing $N^\rho M$ and $M^{\oplus \rho}$ as Riemannian manifolds, the metric tensor associated to the charts $\phi$ and $\hat{\phi}$ respectively at $(x, v)$ and $\sigma(x, v) = x + v$ are the identity matrix.

One has:

$$ D|_{y=0} \hat{\phi} = \left( \frac{d\xi}{du^1}|_{u=0} \dots, \frac{d\xi}{du^d}|_{u=0}, w_1, \dots, w_{N-d} \right) \qquad (27) $$

and since the columns of (27) are unitary and pairwise orthogonal, taking the inner product of (25) and (26) with the columns of $D|_{u=0} \hat{\phi}$, namely $(\frac{d\xi}{du^j}|_{u=0})_{j=1,d}$ and $(w_k)_{k=1,N-d}$, gives an expression of the Jacobian of $\sigma : N^\rho M \to M^{\oplus \rho} \subseteq \mathbb{R}^N$ at the point $\phi(0, t)$ in the charts $\phi$ and $\hat{\phi}$ as:

$$ D|_{u=0} (\hat{\phi}^{-1} \circ \sigma \circ \phi) = \left( \left\langle \frac{d\xi}{du^i}, \frac{d\xi}{du^j} \right\rangle + \sum_{k=1}^{N-d} t^k \left\langle \frac{dw_k}{du^i}, \frac{d\xi}{du^j} \right\rangle \quad \sum_{k=1}^{N-d} t^k \left\langle \frac{dw_k}{du^i}, w_l \right\rangle \right) \quad (28) $$

Where in both $N^\rho M \subseteq \mathbb{R}^N$ and $M^{\oplus \rho}$ the tangent space is decomposed as direct sum of the tangential and orthogonal fibers.

Denoting by $I$ the first fundamental form of $M$:

$$ I = \left\langle \frac{d\xi}{du^i}, \frac{d\xi}{du^j} \right\rangle. $$

Since we have chosen $\xi$ in such a way that $(\frac{d\xi}{du^j}|_{u=0})_{j=1,d}$ is an orthonormal basis of $T_x M$, we have at $x = \xi(0)$ that $I = 1$.

For a unit vector $v \in N_x M$ with $v = \sum_{k=1}^{N-d} t_v^k w_k$ we can call, following J. Milnor again, the second fundamental form in the direction $v$:

$$ \mathrm{II}_v = \sum_{k=1}^{N-d} t_v^k \left\langle \frac{dw_k}{du^i}, \frac{d\xi}{du^j} \right\rangle. $$

We also denote the “torsion” term by $T_v$:

$$ T_v = \sum_{k=1}^{N-d} t_v^k \left\langle \frac{dw_k}{du^i}, w_l \right\rangle $$

In fact we claim that, without loss of generality, one can choose the maps $(w_k)_{k=1,N-d}$ in such a way that $T_v = 0$. Indeed, since, for any $u \in U_0$, $\langle w_k(u), w_l(u) \rangle = \delta_{k,l}$ where $\delta_{k,l}$, the Kronecker delta, is constant, one has:

$$ 0 = \frac{d}{du^i} \langle w_k, w_l \rangle = \left\langle \frac{dw_k}{du^i}, w_l \right\rangle + \left\langle w_k, \frac{dw_l}{du^i} \right\rangle $$
in other words, $\langle \frac{dw_k}{du^i}, w_l \rangle$ is antisymmetric and can then be seen as an infinitesimal rotation, i.e., formally, an element of the Lie algebra of $SO(N-d)$. It results that if we replace $w$ by $w'$ defined by:

$$w'(u^1, \dots, u^d) = \exp \left( - \sum_{i=1}^{d} u_i \left\langle \frac{dw_k}{du^i} \Big|_{u=0}, w_l \right\rangle \right) w(u^1, \dots, u^d),$$

we get:

$$\left\langle \frac{dw'_k}{du^i} \Big|_{u=0}, w'_l \right\rangle = 0.$$

Since the exp term is a rotation depending smoothly $(C^\infty)$ on the $u_i$ and is applied to the basis $w, w$ can be replaced by $w'$ which proves the claim.

We have that for $\tau \in [0, \rho]$, at the point $(x, \tau v) \in N^\rho M$ with $\sigma(x, \tau v) = x + \tau v \in M^{\oplus \rho}$ the Jacobian (28) can be expressed as, with the assumption $T_v = 0$:

$$\begin{pmatrix} 1 + \tau \Pi_v & T_v \\ 0 & 1 \end{pmatrix} = \begin{pmatrix} 1 + \tau \Pi_v & 0 \\ 0 & 1 \end{pmatrix} \qquad (29)$$

Thanks to Lemma 30, $\|\Pi_v\|_2$, the operator $L^2$ norm of $\Pi_v$, which is the maximal extrinsic curvature of $M$, is upper bounded by the inverse of the reach of $M$:

$$\forall v \in N_x M, \|v\| = 1, \|\Pi_v\|_2 \le \frac{1}{\text{reach } M} \qquad (30)$$

Since in (29) one has $\tau \le \rho < \text{reach } M$, we get that $\|\tau \Pi_v\|_2 \le \frac{\tau}{\text{reach } M} < 1$ and $1 + \tau \Pi_v$, the upper left bloc in (29), is invertible. It follows that matrix (29) is invertible:

$$D|_{y=0} (\phi^{-1} \circ \Psi \circ \hat{\phi}) = \begin{pmatrix} 1 + \tau \Pi_v & 0 \\ 0 & 1 \end{pmatrix}^{-1} = \begin{pmatrix} (1 + \tau \Pi_v)^{-1} & 0 \\ 0 & 1 \end{pmatrix} \qquad (31)$$

By local inversion Theorem, (31) gives us the Jacobian of $\Psi = \sigma^{-1}$ at $x + \tau v \in M^{\oplus \rho}$. In particular, the first row of (31):

$$((1 + \tau \Pi_v)^{-1} \quad 0) \qquad (32)$$

is the Jacobian of $\xi^{-1} \circ \pi_M \circ \hat{\phi}$ at $x + \tau v \in M^{\oplus \rho}$.

## E Restriction of $\pi_M$ to a $d$-dimensional affine space in a neighborhood of $x + \tau v \in M^{\oplus \rho}$

Let $\Pi \subseteq \mathbb{R}^N$ denote a $d$-dimensional affine space that contains the point $y = x + \tau v \in M^{\oplus \rho}$ for $x \in M, v \in N_x M$ a unit vector and $\tau < \rho$. If $(y, e_1, \dots, e_d)$ is an orthonormal frame of $\Pi$ centered at $y$. This frame defines a parametrization $\mathbb{R}^d \to \Pi$ defined by

$$(z^1, \dots, z^d) \mapsto y + \sum_{i=1}^{d} z^i e_i. \qquad (33)$$

Each vector $e_i$ can be decomposed uniquely as a sum $e_i = e_i^T + e_i^N$ where $e_i^T \in T_x M$ and $e_i^N \in N_x M$. From the definition (13) one has:

$$\min_{z \in \mathbb{R}^d, \|z\|=1} \left\| \sum_{i=1}^{d} z^i e_i^T \right\| = \min_{z \in \mathbb{R}^d, \|z\|=1} \left\| \pi_{T_x M} \left( \sum_{i=1}^{d} z^i e_i \right) \right\| = \cos \angle \Pi, T_x M \qquad (34)$$
Using (32) we get:

$$ \frac{d}{dz^j}|_{z=0} \xi^{-1} \circ \pi_M \left( y + \sum_{i=1}^{d} z^i e_i \right) = (1 + \tau \Pi_v)^{-1} e_j^T \quad (35) $$

Since $\tau \le \rho$ and the eigenvalues of $\Pi_v$ are the principal curvatures, by Lemma 30 they are upper bounded by $\mathcal{R}^{-1}$, the inverse of the reach of $\mathcal{M}$. The eigenvalues of the symmetric matrix $(1 + \tau \Pi_v)^{-1}$ are therefore included in:

$$ \left[ \frac{\mathcal{R}}{\mathcal{R} + \rho}, \frac{\mathcal{R}}{\mathcal{R} - \rho} \right] $$

and therefore its determinant included by:

$$ \left[ \left( \frac{\mathcal{R}}{\mathcal{R} + \rho} \right)^d, \left( \frac{\mathcal{R}}{\mathcal{R} - \rho} \right)^d \right] $$

From (34) we have that the determinant of

$$ (z^1, \dots, z^d) \mapsto \pi_{T_x \mathcal{M}} \left( y + \sum_{i=1}^d z^i e_i \right) = \sum_{i=1}^d z^i e_i^T $$

is included in:

$$ \left[ (\cos \angle \Pi, T_x \mathcal{M})^d, 1 \right] $$

In fact, a finer analysis exploiting Lemma 28 allows to improve this bound to:

$$ \left[ (\cos \angle \Pi, T_x \mathcal{M})^{\min(d, N-d)}, \cos \angle \Pi, T_x \mathcal{M} \right], $$

since, when $N < 2d$, $T_x \mathcal{M}$ and the vector space associated to $\Pi$ have a common subspace of dimension at least $2d - N$.

Therefore, the determinant of the differential of $(z^1, \dots, z^d) \mapsto \xi^{-1} \circ \pi_M (y + \sum_{i=1}^d z^i e_i)$ is bounded by:

$$ \det \left( \left. \frac{d}{dz^j} \right|_{z=0} \xi^{-1} \circ \pi_M \left( y + \sum_{i=1}^d z^i e_i \right) \right) \quad (36) \\ \in \left[ \left( \frac{\mathcal{R}}{\mathcal{R} + \rho} \right)^d (\cos \angle \Pi, T_x \mathcal{M})^{\min(d, N-d)}, \left( \frac{\mathcal{R}}{\mathcal{R} - \rho} \right)^d \cos \angle \Pi, T_x \mathcal{M} \right] $$

If $\angle \Pi, T_x \mathcal{M} < \pi/2$, it follows from (34) that the set of vectors $(e_i^T)_{i=1,d}$ spans $T_x \mathcal{M}$. Since $(1 + \tau \Pi_v)^{-1}$ has full rank $d$ we get that $\left. \frac{d}{dz^j} \right|_{z=0} \xi^{-1} \circ \pi_M (y + \sum_{i=1}^d z^i e_i)$ has full rank. We have proven that:

**Lemma 37.** Let $\Pi \subseteq \mathbb{R}^N$ denote a $d$-dimensional affine space that contains the point $y \in \mathcal{M}^{\oplus \rho}$. If $\angle \Pi, T_{\pi_M(y)} \mathcal{M} < \pi/2$, then, in some open neighborhood $U_y$ of $y$ in $\Pi$, $\pi_M|_{U_y}$ is a $C^1$-diffeomorphism on its image.
We consider now $\Pi_1, \Pi_2 \subseteq \mathbb{R}^N$, two $d$-dimensional affine space, where, for $i=1,2$ the affine space $\Pi_i$ contains the point $y_i = x + \tau_i v_i \in \mathcal{M}^{\oplus \rho}$ for $x \in \mathcal{M}, v_i \in N_x \mathcal{M}$ a unit vector and $\tau_i < \rho$. We assume that, for $i=1,2$, one has $\angle \Pi_i, T_{\pi_{\mathcal{M}}(y)} \mathcal{M} < \pi/3$.

By Lemma 37, the projection on $\mathcal{M}$ restricted to some neighborhood of $y_i$ in $\Pi_i$, is an homeomorphism. For $i=1,2$, let $U_i$ be an open neighborhood of $y_i$ in $\Pi_i$ such that $\pi_{\mathcal{M}}|_{U_i}$ is an homeomorphism on its image and $U_i \subseteq \mathcal{M}^{\oplus \rho}$. Assume moreover that $\pi_{\mathcal{M}}(U_1) = \pi_{\mathcal{M}}(U_2)$. Then one can defines an homomorphism $\varphi_{1 \to 2} : U_1 \to U_2$ as:

$$ \varphi_{1 \to 2} \stackrel{\text{def.}}{=} (\pi_{\mathcal{M}}|_{U_2})^{-1} \circ \pi_{\mathcal{M}}|_{U_1} $$

One has, for a chart $\xi: U_0 \to \mathcal{M}$, where $U_0 \subseteq \mathbb{R}^d$, and is such that $\xi(U_0) \supset \pi_{\mathcal{M}}(U_1) = \pi_{\mathcal{M}}(U_2)$, that:

$$ \varphi_{1 \to 2} = (\pi_{\mathcal{M}}|_{U_2})^{-1} \circ \pi_{\mathcal{M}}|_{U_1} \\ (\pi_{\mathcal{M}}|_{U_2})^{-1} \circ \xi \circ \xi^{-1} \circ \pi_{\mathcal{M}}|_{U_1} $$

Choosing some coordinate systems for $\Pi_1$ and $\Pi_2$ defined by respective orthonormal frame $(y_1, e_{11}, \dots, e_{1d})$ and $(y_2, e_{21}, \dots, e_{2d})$, as in (33), we denote by $D\varphi_{1 \to 2}$ the matrix of the derivative of $\varphi_{1 \to 2}$ in these coordinate systems we have:

$$ D\varphi_{1 \to 2}(y) = \left( \frac{d}{dz_2^j}|_{z=0} \xi^{-1} \circ \pi_{\mathcal{M}} \left( y + \sum_{i=1}^d z_2^i e_{2i} \right) \right)^{-1} \left( \frac{d}{dz_1^j}|_{z=0} \xi^{-1} \circ \pi_{\mathcal{M}} \left( y_1 + \sum_{i=1}^d z_1^i e_{1i} \right) \right) $$

So that, using (36), we get:

$$ \det D\varphi_{1 \to 2}(y) \in \left[ \frac{\left(\frac{\mathcal{R}}{\mathcal{R}+\rho}\right)^d (\cos \angle \Pi_1, T_x \mathcal{M})^{\min(d,N-d)}}{\left(\frac{\mathcal{R}}{\mathcal{R}-\rho}\right)^d \cos \angle \Pi_2, T_x \mathcal{M}}, \frac{\left(\frac{\mathcal{R}}{\mathcal{R}-\rho}\right)^d \cos \angle \Pi_1, T_x \mathcal{M}}{\left(\frac{\mathcal{R}}{\mathcal{R}+\rho}\right)^d (\cos \angle \Pi_2, T_x \mathcal{M})^{\min(d,N-d)}} \right] $$

In other words:

$$ \det D\varphi_{1 \to 2}(y) \in \left[ \frac{(\mathcal{R} - \rho)^d (\cos \angle \Pi_1, T_x \mathcal{M})^{\min(d,N-d)}}{(\mathcal{R} + \rho)^d \cos \angle \Pi_2, T_x \mathcal{M}}, \frac{(\mathcal{R} + \rho)^d \cos \angle \Pi_1, T_x \mathcal{M}}{(\mathcal{R} - \rho)^d (\cos \angle \Pi_2, T_x \mathcal{M})^{\min(d,N-d)}} \right] $$

To sum up, we have proven:

**Lemma 38.** Let $\Pi_1, \Pi_2 \subseteq \mathbb{R}^N$, be two $d$-dimensional affine spaces, where, for $i=1,2$ $\Pi_i$ contains the point $y_i \in \mathcal{M}^{\oplus \rho}$ with $\pi_{\mathcal{M}}(y_i) = x \in \mathcal{M}$. For $i=1,2$, let $U_i \subseteq \Pi_i \cap \mathcal{M}^{\oplus \rho}$ be an open subset of $\Pi_i$ such that $\pi_{\mathcal{M}}(U_1) = \pi_{\mathcal{M}}(U_2)$ and, for $i=1,2, \forall z \in U_i, \angle \Pi_i, T_{\pi_{\mathcal{M}}(z)} \mathcal{M} < \theta < \pi/3$.

Then, the Jacobian, of the map $\varphi_{1 \to 2} = (\pi_{\mathcal{M}}|_{U_2})^{-1} \circ \pi_{\mathcal{M}}|_{U_1}$, taking as chart for $U_1$ and $U_2$ the coordinates associated to an orthonormal frame, is bounded by:

$$ |\det D\varphi_{1 \to 2}(y)| \in \left[ \frac{(\mathcal{R} - \rho)^d (\cos \theta)^{\min(d,N-d)}}{(\mathcal{R} + \rho)^d}, \frac{(\mathcal{R} + \rho)^d}{(\mathcal{R} - \rho)^d (\cos \theta)^{\min(d,N-d)}} \right] \quad (37) $$

Remark 39. The bound (37) can be expressed as:

$$ |\det D\varphi_{1 \to 2}(y)| \in [(1+J)^{-1}, 1+J] \quad (38) $$
with

$$J = \frac{(\mathcal{R} + \rho)^d}{(\mathcal{R} - \rho)^d (\cos \theta)^{\min(d, N-d)}} - 1$$

where, as $\rho/\mathcal{R} \to 0$, one has:

$$J = \mathcal{O}\left(\frac{\rho}{\mathcal{R}}\right) \qquad (39)$$

## F Transfering orientation

In this section, we start by recalling what it means for a manifold to be orientable. Given a manifold with a prescribed orientation, we then explain how to orient a simplex consistently with the manifold (Definition 43). Finally, we provide conditions under which the property for a simplex to be consistently oriented with a manifold is preserved under projection onto a nearby tangent plane (Lemma 47).

**Definition 40 (Manifold orientation).** An *orientation* of a $C^1$-manifold $\mathcal{M}$ consists of an atlas $\{(U_i \subseteq \mathcal{M}, \psi_i : U_i \to \mathbb{R}^d)\}_{i \in I}$ such that:

$$U_i \cap U_j \neq \emptyset \implies \forall m \in U_i \cap U_j, \det D(\psi_j \circ \psi_i^{-1})(\psi_i(m)) > 0.$$

$\mathcal{M}$ is said to be *orientable* if such an atlas exists.

**Definition 41 (Chart consistent with the orientation).** If $U$ is an open subset of the oriented manifold $\mathcal{M}$, a local chart $\psi: U \to \mathbb{R}^d$ is called consistent with the orientation of $\mathcal{M}$ defined by the atlas $\{(U_i, \psi_i)\}_{i \in I}$ if the following implication holds:

$$U_i \cap U \neq \emptyset \implies \forall m \in U_i \cap U, \det D(\psi \circ \psi_i^{-1})(\psi_i(m)) > 0.$$

Let $\sigma \subseteq \mathbb{R}^N$ be a non-degenerate abstract $d$-simplex. An orientation of $\sigma = [u_0, u_1, \dots, u_d]$ given by the order of the vertices induces an orientation on the affine subspace $\text{aff } \sigma$ by the multivector $(u_1 - u_0) \wedge \dots \wedge (u_d - u_0)$. In other words, for $\sigma = [u_0, u_1, \dots, u_d]$, the set $\text{conv } \sigma$ is an oriented $d$-manifold (with boundary) whose orientation is defined by the map

$$\psi_{\sigma}: \begin{cases} \text{aff } \sigma & \longrightarrow & \mathbb{R}^d \\ x & \longmapsto & (t^1, \dots, t^d), \end{cases} \qquad (40)$$

where $t^1, \dots, t^d$ are the coordinates of $x$ in the natural frame $(u_0, u_1 - u_0, \dots, u_d - u_0)$, that is, real numbers such that $x = u_0 + \sum_{i=1}^d t^i(u_i - u_0)$. Obviously, we may replace the natural frame by any frame with a consistent orientation, that is, any frame for which the change of coordinate matrix with respect to the natural frame has a positive determinant.

**Remark 42.** Let $\sigma$ be a $d$-simplex such that $\text{conv } \sigma \subseteq \mathcal{M}^{\oplus \rho}$ for some $\rho < \text{reach } \mathcal{M}$. Consider $x \in \text{conv } \sigma$ and suppose that for an open neighborhood $U_x$ of $x$ in $\text{aff } \sigma$, one has $\angle(\text{aff } \sigma, \mathbf{T}_{\pi_{\mathcal{M}}(x)}\mathcal{M}) < \frac{\pi}{2}$. Then, by Lemma 37, the map

$$\psi_{\sigma} \circ (\pi_{\mathcal{M}}|_{U_x})^{-1} : \pi_{\mathcal{M}}(U_x) \subseteq \mathcal{M} \to \psi_{\sigma}(U_x) \subseteq \mathbb{R}^d$$

is a valid $C^1$-chart for $\mathcal{M}$.

This remark allows us to transfer the orientation of $\mathcal{M}$ to $\sigma$:
**Definition 43** (Transfering orientation between a manifold and a simplex). Let $\mathcal{M} \subseteq \mathbb{R}^N$ be an orientable manifold with a reach greater than $\rho > 0$. Let $\sigma = [u_0, u_1, \dots, u_d] \subseteq \mathbb{R}^N$ be a non-degenerate $d$-simplex such that $\text{conv} \sigma \subseteq \mathcal{M}^{\oplus \rho}$, and suppose that

$$ \max_{x \in \text{conv} \sigma} \angle(\text{aff} \, \sigma, \mathbf{T}_{\pi_{\mathcal{M}}(x)}\mathcal{M}) < \frac{\pi}{2}. $$

We say that the orientation of $\sigma$ is consistent with a given orientation of $\mathcal{M}$ if there exists a point $x \in \text{conv} \sigma$ and an open neighborhood $U_x$ of $x$ in $\text{aff} \sigma$ such that the chart $\psi_{\sigma} \circ (\pi_{\mathcal{M}}|_{U_x})^{-1}$ is consistent with the orientation of $\mathcal{M}$.

Note that, in the above definition, the orientation consistency between $\sigma$ and $\mathcal{M}$ does not depend upon the choice of $x$ inside $\text{conv} \sigma$. Indeed, thanks to Lemma 37, the determinant of $\psi_{\sigma} \circ (\pi_{\mathcal{M}}|_{U_x})^{-1} \circ (\psi_i)^{-1}$, whose sign determines the orientation consistency, does not vanish on $\text{conv} \sigma$, and, since it is continuous and $\text{conv} \sigma$ is connected, this sign is constant over $\text{conv} \sigma$.

*Remark 44.* Recall that the boundary of an oriented simplex $[v_0, \dots, v_d]$ is defined as:

$$ \partial[v_0, \dots, v_d] = \sum_{i=0}^{d} (-1)^i [v_0, \dots, \hat{v}_i, \dots, v_d] $$

where $\hat{v}_i$ means that vertex $v_i$ is omitted, so that the simplex $\tau = [v_0, \dots, v_{d-1}]$ has the sign $(-1)^d$ in $\partial[v_0, \dots, v_d]$. It follows that for any $d$-coface $\sigma' = \tau \cup \{v'_d\}$ of $\tau$, $\tau$ appears in $\partial\sigma'$ with the same sign as in $\partial\sigma$ if and only if $\sigma'$ is oriented as $[v_0, \dots, v_{d-1}, v'_d]$.

Given two $d$-dimensional vector subspaces $V$ and $V'$ of $\mathbb{R}^N$ such that $\angle(V, V') < \frac{\pi}{2}$, Lemma 28 implicitly gives an expression of the matrix of the orthogonal projection $\pi_V|_{V'}$ on $V$ restricted to $V'$ in an orthonormal basis. In particular, it says that the matrix of $\pi_V|_{V'}$ has a full rank and therefore is invertible. Observe that if $B'$ is a basis of $V'$ that defines an orientation of $V'$, then $\pi_V|_{V'}(B')$ is a basis of $V$ that induces an orientation on $V$. This allows us to transfer the orientation of $V'$ to $V$ as follows.

**Definition 45** (Transfering orientation between simplices). Let $B$ (resp. $B'$) be a basis of $V$ (resp. $V'$). We say that $V$ and $V'$ have a consistent orientation through projection if the determinant of the matrix of $\pi_V|_{V'}$ in basis $(B', B)$ is positive.

As seen in the proof of Lemma 28, the map $\pi_V|_{V'} \circ \pi_{V'}|_V : V \to V$ admits a positive definite matrix in an orthonormal basis and therefore preserves the orientation. It follows that the relation “to have a consistent orientation through projection” is symmetric and could have been defined either by saying (as in the definition above) that the determinant of the matrix of $\pi_V|_{V'}$ in basis $(B', B)$ is positive, or by saying that the determinant of the matrix of $\pi_{V'}|_V$ in basis $(B, B')$ is positive.

However, the relation “to have a consistent orientation through projection” is not transitive in general. For example, if $\Delta_1, \Delta_2, \Delta_3$ are three 1-dimensional vector spaces in $\mathbb{R}^2$, each oriented by a basis $B_1 = \{(1,0)\}$, a basis $B_2 = \{(\cos \frac{\pi}{3}, \sin \frac{\pi}{3})\}$, and a basis $B_3 = \{(\cos \frac{2\pi}{3}, \sin \frac{2\pi}{3})\}$ respectively, then $(\Delta_1, B_1)$ and $(\Delta_2, B_2)$ have a consistent orientation through projection, as do $(\Delta_2, B_2)$ and $(\Delta_3, B_3)$, but not $(\Delta_1, B_1)$ and $(\Delta_3, B_3)$. However, one has the following lemma, useful for the proof of Lemma 47:

**Lemma 46** (Making orientation propagating through projections transitive). Let $V, V_1, V_2$, and $V_3$ be $d$-dimensional vector subspaces of $\mathbb{R}^N$ such that:

$$ \angle(V, V_i) < \frac{\pi}{4}, \quad \text{for } i \in \{1, 2, 3\}. $$
Then, in any basis $B_1$ of $V_1$ the matrix of the linear map from $V_1$ to $V_1$:

$$ \pi_{V_1}|_{V_3} \circ \pi_{V_3}|_{V_2} \circ \pi_{V_2}|_{V_1} $$

has a positive determinant. Equivalently, assuming $B_1, B_2$, and $B_3$ are bases defining orientation of $V_1, V_2$, and $V_3$ respectively, we have the following: If $V_1$ and $V_2$, and $V_2$ and $V_3$ have a consistent orientation through projection, then so do $V_1$ and $V_3$.

**Proof.** The lemma holds trivially when $V_1 = V_2 = V_3 = V$. In this case, the matrix associated to $\pi_{V_1}|_{V_3} \circ \pi_{V_3}|_{V_2} \circ \pi_{V_2}|_{V_1}$ is the identity and its determinant is 1. Using Lemma 28, it is easy to build a basis $B_i(t)$ of a $d$-dimensional vector space $V_i(t)$ for each $i \in \{1, 2, 3\}$, parametrized by $t \in [0, 1]$ and continuous as a function of $t$, such that $B_i(0)$ is a basis of $V$, $B_i(1)$ a basis of $V_i$, and $\angle(V, V_i(t)) < \frac{\pi}{4}$ for all $t \in [0, 1]$. In this condition, the determinant of:

$$ \pi_{V_1(t)}|_{V_3(t)} \circ \pi_{V_3(t)}|_{V_2(t)} \circ \pi_{V_2(t)}|_{V_1(t)} $$

is a continuous function of $t$ which equals 1 when $t = 0$. Since for any $i, j \in \{1, 2, 3\}$ one has $\angle(V_i(t), V_j(t)) < \frac{\pi}{2}$, each projection has a full rank and therefore so does their composition. Thus, the determinant does not vanish and must remain positive for all $t \in [0, 1]$. $\square$

**Lemma 47** (Projection on a tangent space gives the orientation). Let $\mathcal{M}$ be a compact, orientable, $C^2$ d-submanifold of the Euclidean space with a reach greater than $\rho > 0$, and let $m \in \mathcal{M}$. For a given orientation of $T_m\mathcal{M}$, we assume $\mathcal{M}$ to be oriented by the chart$^4 \pi_{T_m\mathcal{M}}$.

Let $\sigma = [v_0, \dots, v_d]$ be an oriented, non-degenerate $d$-simplex such that $\text{conv } \sigma \subseteq \mathcal{M}^{\oplus \rho}$, $\pi_{\mathcal{M}}(\text{conv } \sigma) \subseteq B(m, \sin(\frac{\pi}{4})\text{ reach } \mathcal{M})$, and $\angle(\text{aff } \sigma, T_m\mathcal{M}) < \frac{\pi}{4}$. Then the orientation of $\sigma$ is consistent with the orientation of $\mathcal{M}$ if and only if the orientation of

$$ \pi_{T_m\mathcal{M}}(\sigma) = [\pi_{T_m\mathcal{M}}(v_0), \dots, \pi_{T_m\mathcal{M}}(v_d)] $$

is consistent with the orientation of $T_m\mathcal{M}$.

**Proof.** For $x \in \text{conv } \sigma$, let us denote by $\tilde{x} = \pi_{\mathcal{M}}(x)$ the projection of $x$ on $\mathcal{M}$. According to Lemma 33, since $x \in \text{conv } \sigma$ implies $\tilde{x} \in \mathcal{M} \cap B(m, \sin(\frac{\pi}{4})\text{ reach } \mathcal{M})$, one has:

$$ \angle(T_m\mathcal{M}, T_{\tilde{x}}\mathcal{M}) < \frac{\pi}{4}. \qquad (41) $$

Using the above inequality and our assumption that $\angle(\text{aff } \sigma, T_m\mathcal{M}) < \frac{\pi}{4}$, Lemma 46 can be applied with spaces $\text{aff } \sigma, T_m\mathcal{M}$, and $T_{\tilde{x}}\mathcal{M}$, and, we can therefore choose orthonormal bases for $T_m\mathcal{M}$, $\text{aff } \sigma$, and $T_{\tilde{x}}\mathcal{M}$ which have a consistent orientation through projection. These bases define respective frames of $T_m\mathcal{M}$, $\text{aff } \sigma$, and $T_{\tilde{x}}\mathcal{M}$ centered at $m$, $x$, and $\tilde{x}$, respectively. These frames define coordinate systems, or charts, for $T_m\mathcal{M}$, $\text{aff } \sigma$, and $T_{\tilde{x}}\mathcal{M}$.

Since, with this choice of charts, the projection of $\text{aff } \sigma$ to $T_{\tilde{x}}\mathcal{M}$ preserves the orientation, $\pi_{T_m\mathcal{M}}(\sigma) = [\pi_{T_m\mathcal{M}}(v_0), \dots, \pi_{T_m\mathcal{M}}(v_d)]$ is oriented positively with respect to the orientation of $T_m\mathcal{M}$. To prove the lemma, it is enough to prove that, with this choice of coordinate systems, the orientation of $\sigma$ is consistent with the orientation of $\mathcal{M}$.

According to Definitions 43 and 41, if $U_x$ is an open neighborhood of $x$ in $\text{aff } \sigma$, using the coordinate system $\psi_\sigma: U_x \to \mathbb{R}^d$, consistent with the orientation of $\sigma$, is consistent with the orientation of $\mathcal{M}$ if and only if, using the notation $\mathcal{M}_m$ for $\mathcal{M} \cap B(m, \sin(\frac{\pi}{4})\text{ reach } \mathcal{M})$:

$$ \det \text{D} \left( \left( \pi_{\mathcal{M}|_{U_x}} \right)^{-1} \circ \left( \pi_{T_m \mathcal{M}|_{\mathcal{M}_m}} \right)^{-1} \right) (\pi_{T_m \mathcal{M}}(x)) > 0 \qquad (42) $$

<footnote>$^4$Indeed, by Lemma 33 the restriction of $\pi_{T_m\mathcal{M}}$ to $\mathcal{M} \cap B(m, \sin(\frac{\pi}{4})\text{ reach } \mathcal{M})$ is a local chart of $\mathcal{M}$.</footnote>
for any $x \in \text{conv } \sigma$. Equivalently:

$$ \det D \left( \pi_{T_m M|_{M_m}} \circ \pi_{M|_{U_x}} \right) (x) > 0. \qquad (43) $$

Since $M$ and $T_{\tilde{x}}$ are tangent at $\tilde{x}$, we obtain, by using the chart $\pi_{T_{\tilde{x}}M|_{M_{\tilde{x}}}}$ for $M$ in a neighborhood $M_{\tilde{x}}$ of $\tilde{x}$ in $M$:

$$ D \left( \pi_{T_{\tilde{x}}M|_{M_{\tilde{x}}}} \right) (\tilde{x}) = 1. \qquad (44) $$

Since (35) assumes the projection on $T_{\tilde{x}}M$ equipped with the orthonormal basis $(e_1, \dots, e_d)$ of $T_{\tilde{x}}M$ as a chart for $M$ in a neighborhood $M_{\tilde{x}}$ of $\tilde{x}$, it gives us an expression of the derivative of $\pi_{T_{\tilde{x}}M|_{M_{\tilde{x}}}} \circ \pi_{M|_{U_x}}$:

$$ D \left( \pi_{T_{\tilde{x}}M|_{M_{\tilde{x}}}} \circ \pi_{M|_{U_x}} \right) (x) = (1 + \sigma \Pi_v(\tilde{x}))^{-1} e_j^T = (1 + \sigma \Pi_v(\tilde{x}))^{-1} \pi_{T_{\tilde{x}}M|_{U_x}}, $$

where $v$ is a unit vector such that $x = \tilde{x} + \sigma v$, and $\pi_{T_{\tilde{x}}M|_{U_x}}$ is the differential of $\pi_{T_{\tilde{x}}M|_{U_x}}$. Then, using (44):

$$ D \left( \pi_M|_{U_x} \right) (x) = (1 + \sigma \Pi_v(\tilde{x}))^{-1} \pi_{T_{\tilde{x}}M|_{U_x}}. \qquad (45) $$

Using (44), that is the tangent space at $\tilde{x}$ to $M_m$ or $M_x$ coincides, with the same chart, with the tangent space at at $\tilde{x}$ to $T_{\tilde{x}}M$, we get:

$$ D \left( \pi_{T_m M|_{M_m}} \right) (\tilde{x}) = D \left( \pi_{T_m M|_{T_{\tilde{x}}M}} \right) (\tilde{x}) = \pi_{T_m M|_{T_{\tilde{x}}M}}, \qquad (46) $$

since $\pi_{T_m M|_{T_{\tilde{x}}M}}$ is the derivative of $\pi_{T_m M|_{T_{\tilde{x}}M}}$. In order to get (43), we need to use (45) and (46) and prove that the determinant of

$$ \pi_{T_m M|_{T_{\tilde{x}}M}} (1 + \sigma \Pi_v(\tilde{x}))^{-1} \pi_{T_{\tilde{x}}M|_{U_x}} $$

is positive. This holds since each of the matrices associated to the three linear maps has a positive determinant: indeed, it holds for the two projections by the choice of coordinate systems, and for $(1 + \sigma \Pi_v(\tilde{x}))^{-1}$ because, since $\sigma \le \rho < \text{reach } M$ and $\|\sigma \Pi_v(\tilde{x})\|_2 < 1$, the matrix $1 + \sigma \Pi_v(\tilde{x})$ is symmetric and positive definite. $\square$

# G Establishing practical conditions

**Lemma 48.** Let $K$ be a simplicial complex with vertices in $\mathbb{R}^N$ such that $|K| \subseteq M^{\oplus \rho}$ and suppose that the $d$-simplices of $K$ are non-degenerate and have a diameter upper bounded by $\rho$. We also assume that for all $d$-simplices $\tau \in K$ and all points $y \in \text{conv } \tau$, we have

$$ \angle \operatorname{aff} \tau, T_{\pi_M(y)} < \frac{\pi}{2}. \qquad (47) $$

Choose an orientation for $M$ and assume that all $d$-simplices of $K$ inherit this orientation. Then, for any $d$-cycle $\gamma$ in $K$, the map

$$ \sum_{\alpha} \gamma(\alpha) \mathbf{1}_{\pi_M(\text{conv } \alpha)} $$

is constant almost everywhere.
Proof. Given a set $\Sigma$ of $d$-simplices in $K$ and a $d$-chain $\gamma$ in $K$, we denote by $\gamma|_{\Sigma}$ the restriction of $\gamma$ to $\Sigma$. In other words, $\gamma|_{\Sigma}$ is the chain that coincides with $\gamma$ on $\Sigma$ and is zero elsewhere. We define the map $\pi_{\mathcal{M}}^{\sharp}\gamma: M \to \mathbb{R}$ as the regularization of $m \mapsto \sum_{\alpha} \gamma(\alpha) \mathbf{1}_{\pi_{\mathcal{M}}(\text{conv } \alpha)}$:

$$ (\pi_{\mathcal{M}}^{\sharp}\gamma)(m) = \underset{\text{def.}}{\sum} \gamma(\alpha) \mathbf{1}_{\pi_{\mathcal{M}}(\text{conv } \alpha)}(m). $$

The notation $\pi_{\mathcal{M}}^{\sharp}\gamma$ is justified by the fact that $\pi_{\mathcal{M}}^{\sharp}$ is a linear map from the set of chains in $K$ to the set of piecewise-constant real valued functions on $M$ modulo equality almost everywhere. The regularized version of it is:

$$ (\overline{\pi_{\mathcal{M}}^{\sharp}\gamma})(m) = \lim_{\text{def. } r \to 0^+} \frac{\int_{m' \in \mathcal{M} \cap B(m,r)} (\pi_{\mathcal{M}}^{\sharp}\gamma)(m') d\mu_{\mathcal{M}}}{\int_{m' \in \mathcal{M} \cap B(m,r)} d\mu_{\mathcal{M}}}, $$

where, as usual, $B(m, r)$ designates the ambient ball with center $m$ and radius $r$, and $\mu_{\mathcal{M}}$ is the $d$-volume on $M$. This regularization will allow us to conclude the proof by exploiting the continuity of this regularized function.

For a simplex $\sigma \in K$, we denote the set of $d$-simplices in the star of $\sigma$ in $K$ by $\overline{\text{St}}(\sigma, K)$. We denote the $k$-skeleton of $K$ by $\text{Sk}^k(K)$. We start by proving three claims:

**Claim 1:** $\pi_{\mathcal{M}}(\text{Sk}^{d-1}(K))$ has $\mu_{\mathcal{M}}$-measure zero and $M \setminus \pi_{\mathcal{M}}(\text{Sk}^{d-2}(K))$ is open and connected.

Since $\pi_{\mathcal{M}}$ is $C^1$, the image $\pi_{\mathcal{M}}(\sigma)$ of a $(d-1)$-simplex $\sigma$ has a zero $d$-Hausdorff measure. $\text{Sk}^{d-1}(K)$ is a finite union of such images. $\pi_{\mathcal{M}}(\text{Sk}^{d-2}(K))$, as the image of a compact set by $\pi_{\mathcal{M}}$, is a compact set and its complement is therefore open. Similarly, $\pi_{\mathcal{M}}(\text{Sk}^{d-2}(K))$ is a finite union of smooth compact $(d-2)$-submanifolds of $M$. It follows that any intersection of $\pi_{\mathcal{M}}(\text{Sk}^{d-2}(K))$ with a smooth curve is non generic. Therefore, for any two points $m_1, m_2 \in M \setminus \pi_{\mathcal{M}}(\text{Sk}^{d-2}(K))$, there must exist a smooth curve in $M \setminus \pi_{\mathcal{M}}(\text{Sk}^{d-2}(K))$ connecting $m_1$ to $m_2$. This proves Claim 1.

**Claim 2:** If $\tau \in K$ is a $d$-simplex and $m \in \pi_{\mathcal{M}}(\tau^\circ)$, then $\overline{\pi_{\mathcal{M}}^{\sharp}\gamma}|_{\overline{\text{St}}(\tau, K)} = \pi_{\mathcal{M}}^{\sharp}\gamma|_{\overline{\text{St}}(\tau, K)}$ is constant in a neighborhood of $m$ in $M$.

Indeed, $\overline{\text{St}}(\tau, K) = \{\tau\}$ and for any $m' \in \pi_{\mathcal{M}}(\tau^\circ)$ one has $\overline{\pi_{\mathcal{M}}^{\sharp}\gamma}|_{\overline{\text{St}}(\tau, K)}(m') = \gamma(\tau)$. Due to Lemma 37, $\pi_{\mathcal{M}}|_{\tau^\circ}$ is an open map and there is a neighborhood $U_m$ of $m$ in $M$ such that $U_m \subseteq \pi_{\mathcal{M}}(\tau^\circ)$. It follows that for any $m' \in U_m$, $\overline{\pi_{\mathcal{M}}^{\sharp}\gamma}|_{\overline{\text{St}}(\tau, K)}(m') = \gamma(\tau)$. This proves Claim 2.

Note that Claim 2 does not use the assumption that $\partial\gamma = 0$. Since, for any $d$-simplex $\tau$, the complement of $\pi_{\mathcal{M}}(\tau)$ in $M$ is open in $M$, a consequence of Claim 2 is that $\overline{\pi_{\mathcal{M}}^{\sharp}\gamma}$ and $\pi_{\mathcal{M}}^{\sharp}\gamma$ coincide on $M \setminus \pi_{\mathcal{M}}(\text{Sk}^{d-1}(K))$.

**Claim 3:** If $\sigma \in K$ is a $(d-1)$-simplex and if $\partial\gamma = 0$ then for any $m \in \pi_{\mathcal{M}}(\sigma^\circ)$, $\overline{\pi_{\mathcal{M}}^{\sharp}\gamma}|_{\overline{\text{St}}(\sigma, K)}$ is constant in a neighborhood of $m$ in $M$.

In order to prove the claim, pick one $d$-dimensional coface $\tau$ of $\sigma$ and let $y \in \sigma^\circ$ be such that $\pi_{\mathcal{M}}(y) = m$. Thanks to Remark 42, one can use $\xi = \psi_\tau \circ (\pi_{\mathcal{M}}|_{U_{y,\tau}})^{-1}$ as a chart for $M$ in an open neighborhood $U_m$ of $m$ in $M$. $U_m$ can be chosen small enough to be included in $\pi_{\mathcal{M}}(\text{St}(\sigma, K)^\circ)$ and $U_{\xi(m)} = \xi(U_m) \subseteq \mathbb{R}^d$ is an open neighborhood of $\xi(m)$.

Without loss of generality, assume that $\sigma = [v_0, \dots, v_{d-1}]$ and that the orientation of $\tau$ defined by $\tau = [v_0, \dots, v_{d-1}, v_d]$ is consistent with the given orientation of $M$.
From the definition of $\xi$ and $\psi_{\tau}$ in Definition 43, one has:

$$ \xi(U_m \cap \pi_M(\sigma)) = U_{\xi(m)} \cap (\mathbb{R}^{d-1} \times \{0\}). $$

For a $d$-simplex $\tau' \in \overline{\mathrm{St}(\sigma, K)}$, since the restriction of $\xi \circ \pi_M$ to $\tau'$ is an homeomorphism, the boundary of $\xi(U_m \cap \pi_M(\tau'))$ in $U_{\xi(m)}$ has to coincide with $U_{\xi(m)} \cap (\mathbb{R}^{d-1} \times \{0\})$ and, $\xi(U_m \cap \pi_M(\tau'))$ therefore equals either $U_{\xi(m)} \cap (\mathbb{R}^{d-1} \times \mathbb{R}^-)$ or $U_{\xi(m)} \cap (\mathbb{R}^{d-1} \times \mathbb{R}^+)$.

Let us denote the vertex in $\tau' \setminus \sigma$ by $v'_d$ and consider the curve $y'(t) = y + t(v'_d - v_0)$, with $t \in [0, \lambda]$, $\lambda > 0$ small enough to have $y'([0, \lambda]) \subseteq \tau'^{\circ}$ and $\pi_M(y'([0, \lambda])) \subseteq U_m$. If $\tau'$ is oriented as $[v_0, \dots, v_{d-1}, v'_d]$ and if both $\tau$ and $\tau'$ have been given orientations consistent with $M$, we have (Definition 43):

$$ \det \mathrm{D}(\xi \circ \pi_M \circ \psi_{\tau'}^{-1})(\psi_{\tau'}(y)) > 0, $$

which is equivalent to:

$$ \det \left( \mathrm{D}(\xi \circ \pi_M)(y) \cdot (v_1 - v_0), \dots, \mathrm{D}(\xi \circ \pi_M)(y) \cdot (v_{d-1} - v_0), \mathrm{D}(\xi \circ \pi_M)(y) \cdot (v'_d - v_0) \right) > 0. \quad (48) $$

But by definition of $\xi$ one has that for $i = 1, \dots, d-1$, $\mathrm{D}(\xi \circ \pi_M)(y) \cdot (v_i - v_0) \in \mathbb{R}^d$ equals $(0, \dots, 0, 1, 0, \dots, 0)$ where the 1 appears in position $i$ and thus (48) implies that the last coordinate of $\mathrm{D}(\xi \circ \pi_M)(y) \cdot (v'_d - v_0)$ is positive, which implies that, for $t$ small enough, $\xi \circ \pi_M(y'(t)) \in \mathbb{R}^{d-1} \times \mathbb{R}^+$ under our assumption for $\tau'$ to be oriented as $[v_0, \dots, v_{d-1}, v'_d]$. At the same time, we know from Remark 44 that $\sigma$ appears with the same sign in $\partial\tau'$ as in $\partial\tau$ if and only if $\tau'$ is oriented as $[v_0, \dots, v_{d-1}, v'_d]$. Since the orientations of $\tau$ and $\tau'$ are consistent with the chosen orientation of $M$, $\xi(U_m \cap \pi_M(\tau'))$ is therefore included in $H^- = \mathbb{R}^{d-1} \times \mathbb{R}^-$ or $H^+ = \mathbb{R}^{d-1} \times \mathbb{R}^+$ respectively depending on whether $\sigma$ appears negatively or positively in $\partial\tau$.

The set $\overline{\mathrm{St}(\sigma, K)}$ of $d$-cofaces of $\sigma$ can be decomposed in $\overline{\mathrm{St}(\sigma, K)}^-$ and $\overline{\mathrm{St}(\sigma, K)}^+$ such that:

$$ \partial\tau(\sigma) = -1 \iff \tau \in \overline{\mathrm{St}(\sigma, K)}^- \quad \text{and} \quad \partial\tau(\sigma) = 1 \iff \tau \in \overline{\mathrm{St}(\sigma, K)}^+. $$

Then:

$$ \partial\gamma = 0 \Rightarrow \left( \sum_{\tau \in \overline{\mathrm{St}(\sigma, K)}^+} \gamma(\tau) \right) - \left( \sum_{\tau \in \overline{\mathrm{St}(\sigma, K)}^-} \gamma(\tau) \right) = 0. \quad (49) $$

If $m^- \in \xi_{\sigma}^{-1}(H^- \cap \xi_{\sigma} \circ \pi_M(U_x) \setminus \Pi)$ then:

$$ \pi_M^\sharp \gamma|_{\overline{\mathrm{St}(\sigma, K)}}(m^-) = \pi_M^\sharp \gamma|_{\overline{\mathrm{St}(\sigma, K)}}(m^-) = \sum_{\tau \in \overline{\mathrm{St}(\sigma, K)}^-} \gamma(\tau), \quad (50) $$

and if $m^+ \in \xi_{\sigma}^{-1}(H^+ \cap \xi_{\sigma} \circ \pi_M(U_x) \setminus \Pi)$ then:

$$ \pi_M^\sharp \gamma|_{\overline{\mathrm{St}(\sigma, K)}}(m^+) = \pi_M^\sharp \gamma|_{\overline{\mathrm{St}(\sigma, K)}}(m^+) = \sum_{\tau \in \overline{\mathrm{St}(\sigma, K)}^+} \gamma(\tau). \quad (51) $$

Now (49), (50), and (51) give us:

$$ \pi_M^\sharp \gamma|_{\overline{\mathrm{St}(\sigma, K)}}(m^+) - \pi_M^\sharp \gamma|_{\overline{\mathrm{St}(\sigma, K)}}(m^-) = 0, $$
which proves Claim 3.

One has, for any $m \in \mathcal{M}$:

$$ \pi_{\mathcal{M}}^{\sharp} \gamma(m) = \sum_{m \in \pi_{\mathcal{M}}(\sigma^{\circ})} \pi_{\mathcal{M}}^{\sharp} \gamma|_{\overline{\mathrm{St}(\sigma, K)}}(m). \qquad (52) $$

If $m \in \mathcal{M} \setminus \pi_{\mathcal{M}}(\mathrm{Sk}^{d-2}(K))$ then the simplices $\sigma$ such that $m \in \pi_{\mathcal{M}}(\sigma^{\circ})$ that contribute to the sum (52) are of dimension either $d$ either $d-1$. It follows from Claims 1, 2, and 3, that if $m \in \mathcal{M} \setminus \pi_{\mathcal{M}}(\mathrm{Sk}^{d-2}(K))$ then $\pi_{\mathcal{M}}^{\sharp} \gamma$ is constant in an open neighborhood of $m$. As a consequence, for $m_0 \in \mathcal{M} \setminus \pi_{\mathcal{M}}(\mathrm{Sk}^{d-2}(K))$, the set

$$ \{m \in \mathcal{M} \setminus \pi_{\mathcal{M}}(\mathrm{Sk}^{d-2}(K)) \mid \overline{\pi_{\mathcal{M}}^{\sharp} \gamma(m)} = \overline{\pi_{\mathcal{M}}^{\sharp} \gamma(m_0)}\} $$

is open. Since $\mathcal{M} \setminus \pi_{\mathcal{M}}(\mathrm{Sk}^{d-2}(K))$ is connected by Claim 1, it follows that $\psi_{\gamma,K}$ is constant on $\mathcal{M} \setminus \pi_{\mathcal{M}}(\mathrm{Sk}^{d-2}(K))$. Since $\psi_{\gamma,K}$ and $m \mapsto \sum_{\alpha \in K} \gamma(\alpha) \mathbf{1}_{\pi_{\mathcal{M}}(\mathrm{conv} \, \alpha)}$ coincide on $\mathcal{M} \setminus \pi_{\mathcal{M}}(\mathrm{Sk}^{d-1}(K))$, and since, due to Claim 1, $\pi_{\mathcal{M}}(\mathrm{Sk}^{d-1}(K))$ has a zero Lebesgue measure, we have shown that $\sum_{\alpha \in K} \gamma(\alpha) \mathbf{1}_{\pi_{\mathcal{M}}(\mathrm{conv} \, \alpha)}$ is constant almost everywhere. $\square$

The next lemma is useful to derive a realistic algorithm in Section 8.1. Roughly, it says that the normalization constraint in Problem (⋆) can be replaced by a constraint which does not refer to $\mathcal{M}$ anymore but refers only to a rough approximation $\Pi$ of $\mathcal{M}$. Such an approximation can be derived from the mere knowledge of the point set $P$, as explained in Section 8.1. For any $x \in \mathbb{R}^N$ and any $r \ge 0$, recall that $K[x, r] = \{\sigma \in K \mid \mathrm{conv} \, \sigma \cap B(x, r) \neq \emptyset\}$ and note that $K[x, r]$ is not necessarily a simplicial complex.

**Lemma 49** (Practical normalization lemma). Suppose $0 \le \rho \le \frac{\mathbb{R}}{25}$. Let $K$ be a simplicial complex with vertices in $\mathbb{R}^N$ such that $|K| \subseteq \mathcal{M}^{\oplus \rho}$ and suppose that the $d$-simplices of $K$ are non-degenerate and have a diameter upper bounded by $\rho$. Suppose furthermore that for all $d$-simplices $\tau \in K$ and all points $y \in \mathrm{conv} \, \tau$, we have

$$ \angle(\mathrm{aff} \, \tau, \mathbf{T}_{\pi_{\mathcal{M}}(y)}\mathcal{M}) < \frac{\pi}{2} \qquad (53) $$

and that every $d$-simplex in $K$ inherits the orientation of the manifold $\mathcal{M}$. Consider a $d$-dimensional affine space $\Pi$ passing through a point $x \in \mathcal{M}^{\oplus \rho}$ such that

$$ \angle(\Pi, \mathbf{T}_{\pi_{\mathcal{M}}(x)}\mathcal{M}) < \frac{\pi}{8}. \qquad (54) $$

Assume that $\Pi$ is oriented consistently with $\mathcal{M}$. Let $K' = K[x, 4\rho]$ and suppose that the following conditions hold:

(i) $\forall \beta \in K'^{|d-1|}, x \notin \pi_{\Pi}(\mathrm{conv} \, \beta);$

(ii) $\forall \alpha \in K'^{|d|}, \angle \mathrm{aff} \, \alpha, T_{\pi_{\mathcal{M}}(x)}\mathcal{M} < \frac{\pi}{4};$

(iii) $\forall \alpha \in K'^{|d|}, \alpha$ inherits its orientation from $\Pi$.

Then, for all $d$-cycles $\gamma$ in $K$ and all points $m \in \mathcal{M} \setminus \pi_{\mathcal{M}}(|K^{[d-1]}|)$, we have

$$ \sum_{\alpha \in K'^{|d|}} \gamma(\alpha) \mathbf{1}_{\pi_{\mathcal{M}}(\mathrm{conv} \, \alpha)}(m) = \sum_{\alpha \in K'^{|d|}} \gamma(\alpha) \mathbf{1}_{\pi_{\Pi}(\mathrm{conv} \, \alpha)}(x). \qquad (55) $$
Proof. Let $\Pi_0$ be defined as the unique affine space passing through $x$ and parallel to $T_{\pi_M(x)}\mathcal{M}$. We distinguish two cases depending on whether $\Pi = \Pi_0$ or not.

**Case** $\Pi = \Pi_0$. We first claim that:

$$ (\pi_{\mathcal{M}|_{\mathcal{M}^{\oplus\rho}}})^{-1}(\{\pi_{\mathcal{M}}(x)\}) = \pi_{\Pi_0}^{-1}(\{x\}) \cap \mathcal{M}^{\oplus\rho} \cap B(x, 5\rho). \quad (56) $$

Indeed, the left hand member is equal to $N_{\pi_M(x)}\mathcal{M} \cap B(\pi_M(x), \rho)$, where $N_{\pi_M(x)}\mathcal{M} = \{\pi_M(x)\} + N_{\pi_M(x)}\mathcal{M}$ is the $(N-d)$-dimensional affine subspace subspace of $\mathbb{R}^N$ orthogonal to $\mathcal{M}$ at $\pi_M(x)$. Notice that $N_{\pi_M(x)}\mathcal{M}$ contains $x$ and coincides with $\pi_{\Pi_0}^{-1}(\{x\})$ — the affine space through $x$ orthogonal to $\Pi_0$. Since $B(\pi_M(x), \rho) \subseteq B(x, 5\rho)$, the left hand member is included in the right hand member. To get the reverse inclusion we only need to show that:

$$ \pi_{\Pi_0}^{-1}(\{x\}) \cap \mathcal{M}^{\oplus\rho} \cap B(x, 5\rho) \subseteq B(\pi_M(x), \rho). $$

For that observe that for $y \in \pi_{\Pi_0}^{-1}(\{x\}) \cap \mathcal{M}^{\oplus\rho} \cap B(x, 5\rho)$ one has $y \in B(\pi_M(x), 6\rho)$ and, since $6\rho < \mathcal{R}$ and $y \in N_{\pi_M(x)}\mathcal{M}$, one has $\pi_M(y) = \pi_M(x)$ and $d(y, \mathcal{M}) = d(y, \pi_M(x))$. Thus, $y \in \mathcal{M}^{\oplus\rho}$ implies $y \in B(\pi_M(x), \rho)$. Equality (56) is proved.

Let $y \in \text{conv } \alpha \subseteq \mathcal{M}^{\oplus\rho}$ and assume that $x = \pi_{\Pi_0}(y)$. If $\text{conv } \alpha \subseteq B(x, 5\rho)$, then $y \in \pi_{\Pi_0}^{-1}(\{x\}) \cap \mathcal{M}^{\oplus\rho} \cap B(x, 5\rho)$ and (56) gives $\pi_M(y) = \pi_M(x)$. Then

$$ (\text{conv } \alpha \subseteq B(x, 5\rho) \text{ and } x \in \pi_{\Pi_0}(\text{conv } \alpha)) \iff \pi_M(x) \in \pi_M(\text{conv } \alpha). $$

If we assume the diameter of simplices to be upper bounded by $\rho$, then $\text{conv } \alpha \cap B(x, 4\rho) \neq \emptyset$ implies $\text{conv } \alpha \subseteq B(x, 5\rho)$, and we get:

$$ (\text{conv } \alpha \cap B(x, 4\rho) \neq \emptyset \text{ and } x \in \pi_{\Pi_0}(\text{conv } \alpha)) \iff \pi_M(x) \in \pi_M(\text{conv } \alpha). $$

It results that for any $\alpha \in K$, $\pi_M(x) \in \pi_M(\text{conv } \alpha)$ implies $\alpha \in K'$, and:

$$ \sum_{\alpha \in K^{[d]}} \gamma(\alpha) \mathbf{1}_{\pi_M(\text{conv } \alpha)}(\pi_M(x)) = \sum_{\alpha \in K^{[d]}} \gamma(\alpha) \mathbf{1}_{\pi_{\Pi_0}(\text{conv } \alpha)}(x). \quad (57) $$

We assume the following generic condition:

$$ \pi_M(x) \in \mathcal{M} \setminus \pi_M\left(\left|K^{[d-1]}\right|\right). \quad (58) $$

The condition is generic because, if it does not hold, a sufficiently small $C^2$-perturbation $M'$ of $\mathcal{M}$ would satisfy it and still meet all the conditions of the lemma. Assuming the generic condition to hold, one can see using (57) that, in the particular case where $\Pi = \Pi_0$, the lemma is just another formulation of Lemma 48.

**Case** $\Pi \neq \Pi_0$. From now on, we assume that $\Pi \neq \Pi_0$. Consider a differentiable path $\Gamma: [0, 1] \to (\mathbb{R}^N)^{d+1}$, with $\Gamma(t) = (x, \mathcal{B}(t))$ in the space of orthonormal $d$-dimensional frames in $\mathbb{R}^N$. Precisely, $\Gamma(t) = (x, \mathcal{B}(t))$ is the orthonormal frame of a $d$-dimensional affine space $\Pi(t)$ containing $x$, with $\Pi(0) = \Pi_0$ and $\Pi(1) = \Pi$, and $\mathcal{B}(t)$ is an orthonormal basis of the vector space associated to $\Pi(t)$. Lemma 28 allows us to give an explicit formulation for $\mathcal{B}$. Since $\Pi \neq \Pi_0$, $\theta = \angle(\Pi_0, \Pi)$ satisfies $0 < \theta < \frac{\pi}{8}$, and both affine spaces contain $x$. Consider two $d$-dimensional vector spaces $V$ and $V'$ such that $\Pi_0 = x + V$ and $\Pi = x + V'$, respectively. Applying Lemma 28
to $V$ and $V'$ and borrowing its notation, we define the parametrized family of orthonormal bases $\mathcal{B}(t)$ for $t \in [0, 1]$ as:

$$ 
\begin{aligned}
\mathcal{B}(t) &= (\mathcal{B}_1(t), \dots, \mathcal{B}_d(t)) \\
&= (u_1(t), \dots, u_{d'}(t), w_1, \dots, w_{d-d'}), \\
\text{where } u_k(t) &= \cos(t\theta_k)v_k + \sin(t\theta_k)v_k'.
\end{aligned} 
\tag{59} $$

For any $t \in [0, 1]$, $\Gamma(t) = (x, \mathcal{B}(t))$ is an orthonormal frame of $\Pi(t)$. We want to follow the evolution of the function $\phi: [0, 1] \to \mathbb{R}$ defined as:

$$ \phi(t) = \sum_{\text{def.}} \gamma(\alpha) \mathbf{1}_{\Pi(t) (\text{conv } \alpha)}(x), $$

or its regularization $\hat{\phi}$, defined similarly as in the proof of Lemma 48:

$$ \hat{\phi}(t) = \lim_{\text{def.}} \frac{1}{h \to 0} \frac{\min(1, t+h) - \max(0, t-h)}{\max(0, t-h)} \int_{\max(0, t-h)}^{\min(1, t+h)} \phi(s) ds. $$

The proof then consists of showing that $\hat{\phi}(t)$ remains constant along the path $t \mapsto \Pi(t)$ and thus, since Equation 55 is satisfied for $\Pi_0 = \Pi(0)$ by (57), it will extend to $\Pi = \Pi(1)$.

The family of bases $\mathcal{B}(t) = (u_1(t), \dots, u_{d'}(t), w_1, \dots, w_{d-d'})$, parametrized by $t \in [0, 1]$, induces a smooth map $\psi: [0, 1] \times \mathbb{R}^N \to \mathbb{R}^d$ where, for $y \in \mathbb{R}^N$, the components of $\psi(t, y) \in \mathbb{R}^d$ are the coordinates of $\pi_{\Pi(t)}(y) - x$ in the basis $\mathcal{B}(t)$:

$$ \psi(t, y)_k = \langle \mathcal{B}_k(t), \pi_{\Pi(t)}(y) - x \rangle = \langle \mathcal{B}_k(t), y - x \rangle. $$

With this definition one has:

$$ \psi(t, y) = 0 \iff \pi_{\Pi(t)}(y) = x. \tag{60} $$

If $\sigma \in K'^{[d-2]}$, the set $\psi([0, 1], \text{conv } \sigma)$ is included in a compact smooth $(d-1)$-manifold with boundary in $\mathbb{R}^d$. Since it corresponds to the finite union of complements of sets of codimension 1, the condition:

$$ 0 \notin \psi \left( [0, 1], \bigcup_{\sigma \in K'^{[d-2]}} \text{conv } \sigma \right) \tag{61} $$

is generic. We now make the assumption that this generic condition holds, since, if it does not, it can be satisfied after an arbitrarily small perturbation of $t \mapsto \Gamma(t)$. One can easily check using (59) that for any $t \in [0, 1]$, $\angle \Pi(t), \Pi_0 \le \angle \Pi, \Pi_0$, and even if a small perturbation is required for ensuring the generic condition, we can assume that, from (54):

$$ \forall t \in [0, 1], \angle \Pi(t), T_{\pi_M(x)}\mathcal{M} = \angle \Pi(t), \Pi_0 < \frac{\pi}{8}. \tag{62} $$

We will need the following claim:

$$ \forall t \in [0, 1], \quad (\pi_{\Pi(t)})^{-1}(x) \cap \mathcal{M}^{\oplus \rho} \cap B(\pi_M(x), 6\rho) \subseteq B(\pi_M(x), 3\rho). \tag{63} $$

Indeed, consider $y \in (\pi_{\Pi(t)})^{-1}(x) \cap \mathcal{M}^{\oplus \rho} \cap B(\pi_M(x), 6\rho)$. Then $\pi_M(y) \in B(\pi_M(x), 7\rho)$, and using Lemma 31, one has:

$$ \pi_M(y) \in (T_{\pi_M(x)}\mathcal{M})^{\oplus \frac{(7\rho)^2}{2\mathbb{R}}} \subseteq (T_{\pi_M(x)}\mathcal{M})^{\oplus \rho}, $$
which, since $d(y, \pi_M(y)) < \rho$, implies:

$$y \in (T_{\pi_M(x)} \mathcal{M})^{\oplus 2\rho}. \qquad (64)$$

Denote the orthogonal projection onto $N_{\pi_M(x)}\mathcal{M}$ by $\pi_{N_{\pi_M(x)}\mathcal{M}}$. Then, since $x \in N_{\pi_M(x)}\mathcal{M} \cap (T_{\pi_M(x)}\mathcal{M})^{\oplus \rho}$, one has with (64):

$$\| \pi_{N_{\pi_M(x)}\mathcal{M}}(y) - \pi_{N_{\pi_M(x)}\mathcal{M}}(x) \| \le 2\rho + \rho = 3\rho.$$

From (62), one has that $\angle(y - x), N_{\pi_M(x)}\mathcal{M} < \frac{\pi}{8}$, which gives:

$$d(y, N_{\pi_M(x)}\mathcal{M}) \le 3\rho \tan \frac{\pi}{8} < \frac{3}{2}\rho.$$

Applying (64) again, we obtain

$$d(y, \pi_M(x)) \le \sqrt{d(y, T_{\pi_M(x)}\mathcal{M})^2 + d(y, N_{\pi_M(x)}\mathcal{M})^2} < \sqrt{4 + \frac{9}{4}}\rho < 3\rho,$$

which proves Equation (63). Since $B(x, 5\rho) \subseteq B(\pi_M(x), 6\rho)$ and $B(\pi_M(x), 3\rho) \subseteq B(x, 4\rho)$, Equation (63) gives us:

$$\forall t \in [0, 1], (\pi_{\Pi(t)})^{-1}(x) \cap \mathcal{M}^{\oplus \rho} \cap B(x, 5\rho) \subseteq B(x, 4\rho). \qquad (65)$$

Since $K'$ is not a simplicial complex, it is convenient to introduce the smallest simplicial complex $\overline{K}'$ containing $K'$, in other words the set of all faces of simplices in $K'$. In particular, $\overline{K}'$ contains all $(d-1)$-faces of the $d$-simplices in $K'$. One has $|\overline{K}'| \subseteq B(x, 5\rho)$ and, using (60), (65) yields:

$$\sigma \in \overline{K'}^{[d-1]}, \quad \text{and} \quad 0 \in \psi([0, 1], \text{conv } \sigma) \Rightarrow \sigma \in K'^{[d-1]}. \qquad (66)$$

As shown below, the changes in $t \mapsto \hat{\phi}(t)$ may happen only when $\psi(t, \text{conv } \sigma) = 0$, where $\sigma$ is a $(d-1)$-face of some $d$-simplex $\alpha \in K'^{[d]}$, in other words $\sigma \in \overline{K'}^{[d-1]}$. We need (66) to ensure that every such $\sigma$ in fact belongs to $K'^{[d-1]}$.

Let $\sigma \in K'^{[d-1]}$ be such that $0 \in \psi([0, 1], \text{conv } \sigma)$, and denote the set of $d$-cofaces of $\sigma$ in $K'$ (respectively in $K$) by $\text{St}(\sigma, K')$ (respectively $\text{St}(\sigma, \overline{K}')$). Note that, if $\tau$ is a $d$-coface of $\sigma$ in $K$, and since $\text{conv } \sigma \subseteq \text{conv } \tau$, one has the implication $\text{conv } \sigma \cap B(x, 4\rho) \ne \emptyset \Rightarrow \text{conv } \tau \cap B(x, 4\rho) \ne \emptyset$. Thus, $\tau \in K'$ and we have:

$$\sigma \in K'^{[d-1]} \implies \overline{\text{St}}(\sigma, K') = \overline{\text{St}}(\sigma, K). \qquad (67)$$

*Remark 50.* Thanks to (67), the cycle condition $(\partial\gamma)(\sigma) = 0$ is inherited on each $(d-1)$-simplex $\sigma \in K'^{[d-1]}$ by the restriction of $\gamma$ to $K'$. This is not true for the $(d-1)$-simplices of $\overline{K'}^{[d-1]} \setminus K'^{[d-1]}$. Thanks to (66) we only have to consider how $\phi(t)$ evolves as $t$ continuously increases from 0 to 1 on $(d-1)$-simplices in $K'^{[d-1]}$ and benefit from the cycle condition.

From Condition (ii) and (62) we get that:

$$\forall t \in [0, 1], \tau \in K'^{[d]} \implies \angle \text{aff}(\tau), \Pi(t) < \frac{3\pi}{8}. \qquad (68)$$

As a consequence of Lemma 28, the restriction of $\pi_{\Pi(t)}$ to $\text{aff } \sigma$ is an affine bijection and in particular an homeomorphism. It sends the boundary of a $d$-simplex $\text{conv } \alpha$ onto the boundary of the image of $\text{conv } \alpha$: $\pi_{\Pi(t)}(\partial \text{conv } \alpha) = \partial \pi_{\Pi(t)}(\text{conv } \alpha)$.
The fact that $\psi$ is uniformly continuous (in fact $C^\infty$ with a compact domain) also in $t$, means that in particular:

$$ \forall \epsilon > 0, \exists \eta > 0, \forall y \in \text{aff } \sigma, \forall t, t^* \in [0, 1], \quad |t^* - t| < \eta \implies \|\psi(t^*, y) - \psi(t, y)\| < \epsilon. $$

If $0$ is not on the boundary of $\psi(t, \text{conv } \alpha)$ there is a $\epsilon > 0$ such that either $B(0, \epsilon) \subseteq \psi(t, \text{conv } \alpha)^\circ$ or $B(0, \epsilon) \cap \psi(t, \text{conv } \alpha) = \emptyset$. It follows that:

$$ 0 \in \psi(t, \text{conv } \alpha)^\circ \implies \exists \eta > 0, 0 \in \bigcap_{t^* \in [t-\eta, t+\eta]} \psi(t^*, \text{conv } \alpha), \quad (69) $$

$$ 0 \notin \psi(t, \text{conv } \alpha) \implies \exists \eta > 0, 0 \notin \psi([t-\eta, t+\eta], \text{conv } \alpha). \quad (70) $$

We are now ready to track the evolution of $t \mapsto \hat{\phi}(t)$. For that we consider two cases. First we consider the values of $t$ such that $x \notin \pi_{\Pi(t)}(\overline{K'}^{[d-1]})$, or in other words $0 \notin \psi(t, |\overline{K'}^{[d-1]}|)$. Let $\alpha \in K'^{[d]}$. Since $0$ is not on the boundary of $\psi(t, \text{conv } \alpha)$, one of the two cases (69) or (70) must occur. This implies that, for some $\eta > 0$, $t \mapsto \phi(t)$ is constant on $[t - \eta, t + \eta]$, which in turn implies that in this case $\phi$ and $\hat{\phi}$ coincide:

$$ 0 \notin \psi(t, |\overline{K'}^{[d-1]}|) \Rightarrow \phi(t) = \hat{\phi}(t). $$

We now consider the second case, namely when $t$ is such that $x \in \pi_{\Pi(t)}(|\overline{K'}^{[d-1]}|)$. According to (66), if $x \in \pi_{\Pi(t)}(\text{conv } \sigma)$ for some $\sigma \in \overline{K'}^{[d-1]}$, then $\sigma \in K'^{[d-1]}$. Therefore (67) and Remark 50 applies.

We are interested in the possible change of value of $\phi(t^*)$ when $t^*$ belongs to a neighborhood of $t$. Generically, if $x \in \pi_{\Pi(t)}(|K'^{[d-1]}|)$, there is a unique $\sigma \in K'^{[d-1]}$ such that $x \in \pi_{\Pi(t)}(\text{conv } \sigma)$. However, we do not need this generic condition, since $\phi(t^*)$ can be expressed as the following sum for any $t^* \in [0, 1]$. We consider the $d$-simplices $\alpha$ separately, depending on whether the inverse image of $0$ by $\psi(t, \cdot)$ is (1) interior: $0 \in \psi(t, \text{conv } \alpha)^\circ$ (the first sum below), (2) on the boundary: $0 \in \partial(\psi(t, \text{conv } \alpha))$ (the second sum below), or (3) the complement: $0 \in \psi(t, \text{conv } \alpha)^c$ (the third sum below):

$$ \begin{aligned} \forall t^* \in [0, 1], \phi(t^*) &= \sum_{\substack{\alpha \in K'^{[d]} \\ 0 \in \psi(t^*, \text{conv } \alpha)}} \gamma(\alpha) \\ &= \sum_{\substack{\alpha \in K'^{[d]} \\ 0 \in \psi(t, \text{conv } \alpha)^\circ \\ 0 \in \psi(t^*, \text{conv } \alpha)}} \gamma(\alpha) + \sum_{\substack{\alpha \in K'^{[d]} \\ 0 \in \partial(\psi(t, \text{conv } \alpha)) \\ 0 \in \psi(t^*, \text{conv } \alpha)}} \gamma(\alpha) + \sum_{\substack{\alpha \in K'^{[d]} \\ 0 \in \psi(t, \text{conv } \alpha)^c \\ 0 \in \psi(t^*, \text{conv } \alpha)}} \gamma(\alpha). \end{aligned} $$

Thanks to (69) and (70) there is a $\eta > 0$ such that, for any $t^* \in [\max(0, t - \eta), \min(1, t + \eta)]$, $0 \in \psi(t^*, \text{conv } \alpha)$ always holds in the first sum and never occurs in the third one. Then:

$$ \begin{aligned} \forall t^* \in [\max(0, t - \eta), \min(1, t + \eta)], \phi(t^*) &= \sum_{\substack{\alpha \in K'^{[d]} \\ 0 \in \psi(t, \text{conv } \alpha)^\circ}} \gamma(\alpha) + \sum_{\substack{\alpha \in K'^{[d]} \\ 0 \in \partial(\psi(t, \text{conv } \alpha)) \\ 0 \in \psi(t^*, \text{conv } \alpha)}} \gamma(\alpha) \\ &= \sum_{\substack{\alpha \in K'^{[d]} \\ 0 \in \psi(t, \text{conv } \alpha)^\circ}} \gamma(\alpha) + \sum_{\substack{\sigma \in K'^{[d-1]} \\ 0 \in \psi(t, \text{conv } \sigma) \\ 0 \in \psi(t^*, \text{conv } \alpha)}} \sum_{\substack{\alpha \in \text{St}(\sigma, K') \\ 0 \in \psi(t^*, \text{conv } \alpha)}} \gamma(\alpha). \end{aligned} \quad (71) $$
In (71), the $d$-simplices in the second sum have been regrouped by the stars of $(d-1)$-simplices.
Notice that no $d$-simplex can be counted twice as, under the generic condition (61) and with the
angle bound (68), one has:

$$
\sigma_1 \neq \sigma_2 \quad \text{and} \quad 0 \in \psi(t, \operatorname{conv} \sigma_1), \quad \text{and} \quad 0 \in \psi(t, \operatorname{conv} \sigma_2) \Rightarrow \overline{\operatorname{St}(\sigma_1, K')} \cap \overline{\operatorname{St}(\sigma_2, K')} = \emptyset. \quad (72)
$$

The first sum does not depend on $t^* \in [\max(0, t-\eta), \min(1, t+\eta)]$ and therefore remains constant in this interval, as in the first case. Thanks to (72), there are several $(d-1)$-simplices $\sigma \in K'^{[d-1]}$ such that $0 \in \psi(t, \operatorname{conv} \sigma)$ in the second sum, their stars are disjoint. It is then enough to study the variation of:

$$
t^* \mapsto \phi_{\sigma}(t^*) = \sum_{\substack{\text{def.} \\ \alpha \in \overline{\text{St}}(\sigma, K') \\ 0 \in \psi(t^*, \text{conv } \alpha)}} \gamma(\alpha)
$$

for a single $\sigma \in K'^{[d-1]}$ such that $0 \in \psi(t, \operatorname{conv} \sigma)$, when $t^*$ belongs to a neighborhood of $t \in [0, 1]$.

According to Lemma 33, the projection $\pi_{\Pi(0)}$ is a chart of $\mathcal{M}$ with a domain $U_0 = \mathcal{M} \cap B(\pi_{\mathcal{M}}(x), \sin(\pi/4) \text{ reach } \mathcal{M})$. Since $\mathcal{M}$ is orientable, we can orient $\mathcal{M}$ consistently with a given orientation of $\pi_{\Pi(0)}$. The simplices in $|K'^{[d]}| \subseteq \mathbb{B}(x, 5\rho)$ are sent into $\mathcal{M} \cap \mathbb{B}(x, 6\rho) \subseteq \mathcal{M} \cap \mathbb{B}(\pi_{\mathcal{M}}(x), 7\rho)$ by $\pi_{\mathcal{M}}$. Since, as assumed in the lemma, one has $\rho < \frac{R}{25}$, we get $\pi_{\mathcal{M}}(|K'^{[d]}|) \subseteq U_0$. In other words, $\psi(0, \cdot)$ restricted to $U_0$ is a chart of $\mathcal{M}$ consistent with the orientation.

Let $\tau$ be a $d$-simplex in $K'$ oriented consistently with the orientation of $\mathcal{M}$, $y \in \tau$, and $U_y$ a neighborhood of $y$ in $\text{aff}(\tau)$. According to Lemma 47, the projection $\psi(0, \cdot)(\tau)$ onto $\Pi(0)$ is positively oriented with respect to the orientation of $\Pi(0)$. Since, for $y \in \tau$, the map $t \mapsto \det D(\psi(t, \cdot)|_{\text{conv } \tau}) (y)$ is continuous and does not vanish by (68), one has

$$
\det D \left( \psi(0, \cdot) \middle|_{\text{conv } \tau} \right) (y) > 0 \Rightarrow \forall t \in [0, 1], \det D \left( \psi(t, \cdot) \middle|_{\text{conv } \tau} \right) (y) > 0.
$$

We have proven that $\psi(t, \cdot)|_{\text{conv } \tau}$ preserves the orientation of any $d$-simplex in $K'$, which means that the projection $\psi(t, \tau) = [\psi(t, v_0), \dots, \psi(t, v_d)]$ of any $d$-simplex $\tau = [v_0, \dots, v_d]$ oriented consistently with $\mathcal{M}$ is positively oriented with respect to the orientation of $\Pi(t)$.

Therefore, we can apply the same argument as for Claim 3 of the proof of Lemma 48 to the
$d$-simplices in the star of $\sigma$: if $x \in \pi_{\Pi(t)}(\text{conv } \sigma)$, in other words if for some $y \in \text{conv } \sigma^\circ$ one
has $\psi(t, y) = 0$, and if $H^-$ and $H^+$ are the two half spaces in $\mathbb{R}^d$ bounded by the hyperplane
spanned by $\psi(t, \sigma)$, then $\alpha \in \overline{\text{St}}(\sigma, K')$ appears positively (resp. negatively) in the boundary of
a $d$-coface $\alpha \in \overline{\text{St}}(\sigma, K')$ if $\psi(t, \alpha) \subseteq H^+$ (resp. $\psi(t, \alpha) \subseteq H^-$).

It follows that, for a point $z$ in a neighborhood of $V_0$ of 0,

$$
z \mapsto \sum_{\substack{\alpha \in \overline{\text{St}}(\sigma, K') \\ z \in \psi(t^*, \text{conv } \alpha)}} \gamma(\alpha)
$$

has the same value in $V_0 \cap (H^-)^\circ$ and in $V_0 \cap (H^+)^\circ$. We consider the $C^1$ map $F : [0, 1] \times \text{conv } \sigma^\circ \to [0, 1] \times \mathbb{R}^d$ defined by:

$$
F(t^*, y^*) = \underset{\text{def.}}{(t^*, \psi(t^*, y^*))}.
$$

We note that, in particular, $F(t, y) = (t, 0)$.

By the Thom Transversality Theorem [29, Chapter 2] the map $F$ is generically transversal to
the manifold $[0,1] \times \{0\}$, which implies that $F$ is regular at $(t, y)$, i.e., its derivative at $(t, y)$ has
rank $d$ and the vector $(1,0) \in \mathbb{R} \times \mathbb{R}^d$ does not belong to the image of the derivative of $F$ when
$F(t^*, y^*) \in (0,1) \times \{0\}$. Since the transversality property on $F$ is generic, if it does not hold, it
will after an arbitrary small perturbation of $F$.
It follows that the image of $F$ in a neighborhood of $F(t, y)$ is a smooth hyper-surface whose tangent space does not contain the vector $(1, 0) \in \mathbb{R} \times \mathbb{R}^d$ and therefore separates the two vectors $(t - \eta, 0)$ and $(t + \eta, 0)$ of $\mathbb{R} \times \mathbb{R}^d$ for $\eta > 0$ small enough. In particular, (since $K'^{[d-1]}$ is finite) the set of all $t'$ such that $\psi(t', |K'^{[d-1]}|)$ is made of isolated values.

Therefore, for some $\epsilon > 0$ and $\alpha > 0$, the complement of $B((t, 0), \epsilon)^{\circ} \cap F([t - \eta, t + \eta], \text{conv } \sigma^{\circ})$ in $B((t, 0), \epsilon)^{\circ}$ has exactly two connected components, which are open and contain $(\{t\} \times (H^{-})^{\circ}) \cap B((t, 0), \epsilon)$ and $(\{t\} \times (H^{+})^{\circ}) \cap B((t, 0), \epsilon)$ respectively.

We know by (69) and (70) that the sum

$$ \sum_{\substack{\alpha \in \text{St}(\sigma, K') \\ 0 \in \psi(t^*, \text{conv } \alpha)}} \gamma(\alpha) $$

is locally constant in each connected component. Then, since it has same value in $(\{t\} \times (H^{-})^{\circ}) \cap B((t, 0), \epsilon)$ and $(\{t\} \times (H^{+})^{\circ}) \cap B((t, 0), \epsilon)$, it has same value in both connected components. We have proven that $t^* \mapsto \phi_{\sigma}(t^*)$ has the same value for $t^* \in (t - \eta, t)$ and $t^* \in (t, t + \eta)$, and therefore its regularization $\hat{\phi}_{\sigma}$ is locally constant. This ends the proof of the lemma. $\square$

## H Approximate tangent space computed by PCA

**Lemma 51.** Let $0 < 16\epsilon \le \rho < \frac{\mathbb{R}}{10}$, and suppose that $P \subseteq \mathcal{M}^{\oplus\delta}$ for some $0 \le \delta < \frac{\rho^2}{4\mathbb{R}}$, $\mathcal{M} \subseteq P^{\oplus\epsilon}$ and separation($P$) $> \eta\epsilon$ for some $\eta > 0$. If, for any point $p \in P$, $c_p$ is the center of mass of $P \cap B(p, \rho)$ and $V_p$ the linear space spanned by the $n$ eigenvectors corresponding to the $n$ largest eigenvalues of the inertia tensor of $(P \cap B(p, \rho)) - c_p$, then one has:

$$ \angle V_p, T_{\pi_{\mathcal{M}(p)}}\mathcal{M} < \Xi_0(\eta, d) \frac{\rho}{\mathbb{R}}, $$

where the function $\Xi_0$ is polynomial in $\eta$ and exponential in $d$.

*Proof.* Consider a frame centered at $c_p$ with an orthonormal basis of $\mathbb{R}^N$, whose $d$ first vectors $e_1, \dots, e_d$ belong to $T_{\pi_{\mathcal{M}(p)}}\mathcal{M}$ and the $N - d$ last vectors $e_{d+1}, \dots, e_N$ to the normal fiber $N_{\pi_{\mathcal{M}(p)}}\mathcal{M}$. Consider the symmetric $N \times N$ normalized inertia tensor $\mathbf{A}$ of $P \cap B(p, \rho)$ in this frame:

$$ \mathbf{A}_{ij} \stackrel{\text{def.}}{=} \frac{1}{\#P \cap B(p, \rho)} \sum_{p \in P \cap B(p, \rho)} \langle v_i, p - c_p \rangle \langle v_j, p - c_p \rangle. $$

The symmetric matrix $\mathbf{A}$ decomposes into 4 blocs:

$$ \mathbf{A} = \begin{pmatrix} \mathbf{A}_{TT} & \mathbf{A}_{TN} \\ \mathbf{A}_{TN}^{t} & \mathbf{A}_{NN} \end{pmatrix}, \qquad (73) $$

where the tangential inertia $\mathbf{A}_{TT}$ is a $d \times d$ symmetric define positive matrix. Because of the sampling conditions, we claim<fnref n="5" /> that there is a constant $C_{TT} > 0$ depending only on $\eta$ and $d$ such that the smallest eigenvalue of $\mathbf{A}_{TT}$ is at least $C_{TT}\rho^2$:

$$ \forall u \in \mathbb{R}^d, \|u\| = 1 \Rightarrow u^t \mathbf{A}_{TT} u \ge C_{TT} \rho^2. \qquad (74) $$

Observe that, by Lemma 31, the points in $P \cap B(p, \rho)$ are at a distance less than $(\rho+\delta)^2/2\mathbb{R}$ from the space $\pi_{\mathcal{M}}(p) + T_{\pi_{\mathcal{M}}(p)}\mathcal{M}$, and therefore so is $c_p$. Thus, the points in $P \cap B(p, \rho)$ are at a

<footnote n="5">⁵This claim has to be detailed if one wants to provide an explicit expression of the quantity $\Xi_0(\eta, d)$.</footnote>
distance less than $2\frac{(\rho+\delta)^2}{2\mathcal{R}} \le 2\frac{\rho^2}{\mathcal{R}}$ (assuming $(\rho+\delta)^2 \le 2\rho^2$) from the space $c_p + T_{\pi_M(p)}\mathcal{M}$. Then, there are constants $C_{TN}$ and $C_{NN}$ such that the operator norms of $\mathbf{A}_{TN}$ and $\mathbf{A}_{NN}$ induced by the Euclidean vector norm are upper bounded by:

$$ \forall u, v \in \mathbb{R}^d, \|u\| = \|v\| = 1 \Rightarrow v^t \mathbf{A}_{TN} u \le C_{TN} \frac{\rho^2}{\mathcal{R}} \rho, \quad (75) $$

and:

$$ \forall u \in \mathbb{R}^d, \|u\| = 1 \Rightarrow u^t \mathbf{A}_{NN} u \le C_{NN} \frac{\rho^2}{\mathcal{R}} \frac{\rho^2}{\mathcal{R}}. \quad (76) $$

Let $v \in \mathbb{R}^N$ be a unit eigenvector of $\mathbf{A}$ with an eigenvalue $\lambda$:

$$ \mathbf{A} v = \lambda v. \quad (77) $$

Define $T = \mathbb{R}^d \times \{0\}^{N-d} \subseteq \mathbb{R}^N$ and $N = \mathbb{0}^d \times \mathbb{R}^{N-d} \subseteq \mathbb{R}^N$, corresponding, in the space of coordinates, to $T_{\pi_M(p)}\mathcal{M}$ and $N_{\pi_M(p)}\mathcal{M}$ respectively.

Let $\theta$ be the angle between $v$ and $T$. There are unit vectors $v_T \in \mathbb{R}^d$ and $v_N \in \mathbb{R}^{N-d}$ such that:

$$ v = ((\cos \theta)v_T, (\sin \theta)v_N)^t, $$

where for a matrix $u$, $u^t$ denotes the transpose of $u$. (77) can be rewritten as:

$$ \begin{pmatrix} \mathbf{A}_{TT} & \mathbf{A}_{TN} \\ \mathbf{A}_{TN}^t & \mathbf{A}_{NN} \end{pmatrix} \begin{pmatrix} (\cos \theta)v_T \\ (\sin \theta)v_N \end{pmatrix} = \lambda \begin{pmatrix} (\cos \theta)v_T \\ (\sin \theta)v_N \end{pmatrix}. \quad (78) $$

Equivalently:

$$ (\cos \theta) \mathbf{A}_{TT} v_T + (\sin \theta) \mathbf{A}_{TN} v_N = \lambda (\cos \theta) v_T, \quad (79) $$

$$ (\cos \theta) \mathbf{A}_{TN}^t v_T + (\sin \theta) \mathbf{A}_{NN} v_N = \lambda (\sin \theta) v_N. \quad (80) $$

Multiplying the two equations on the left hand side by $(\sin \theta)v_T^t$ and $(\cos \theta)v_N^t$ respectively, we get:

$$ \begin{aligned} & (\sin \theta)(\cos \theta)v_T^t \mathbf{A}_{TT} v_T + (\sin \theta)^2 v_T^t \mathbf{A}_{TN} v_N = \lambda(\sin \theta)(\cos \theta), \\ & (\cos \theta)^2 v_N^t \mathbf{A}_{TN} v_T + (\cos \theta)(\sin \theta)v_N^t \mathbf{A}_{NN} v_N = \lambda(\cos \theta)(\sin \theta). \end{aligned} $$

Thus,

$$ (\sin \theta)(\cos \theta)v_T^t \mathbf{A}_{TT} v_T + (\sin \theta)^2 v_T^t \mathbf{A}_{TN} v_N = (\cos \theta)^2 v_N^t \mathbf{A}_{TN} v_T + (\cos \theta)(\sin \theta)v_N^t \mathbf{A}_{NN} v_N. $$

Using (75) and (76), we get:

$$ (\sin \theta)(\cos \theta)v_T^t \mathbf{A}_{TT} v_T \le 2C_{TN} \frac{\rho^2}{\mathcal{R}} \rho + C_{NN} \frac{\rho^2}{\mathcal{R}} \frac{\rho^2}{\mathcal{R}}. $$

Using (74), we get:

$$ (\sin \theta)(\cos \theta) \le 2 \frac{C_{TN}}{C_{TT}} \frac{\rho}{\mathcal{R}} + C_{NN} \frac{C_{NN}}{C_{TT}} \frac{\rho^2}{\mathcal{R}^2}. $$

Using $\sin 2\theta = 2 \sin \theta \cos \theta$, we get:

$$ \frac{1}{2} \sin 2\theta \le 2 \frac{C_{TN}}{C_{TT}} \frac{\rho}{\mathcal{R}} + C_{NN} \frac{C_{NN}}{C_{TT}} \frac{\rho^2}{\mathcal{R}^2} = \mathcal{O}\left(\frac{\rho}{\mathcal{R}}\right). \quad (81) $$
Thus,

$$ \theta \in [0, t] \cup \left[ \frac{\pi}{2} - t, \frac{\pi}{2} \right], $$

with

$$ t = \frac{1}{2} \arcsin 2 \left( 2 \frac{C_{TN}}{C_{TT}} \frac{\rho}{R} + C_{NN} \frac{C_{NN}}{C_{TT}} \frac{\rho^2}{R^2} \right) = \mathcal{O} \left( \frac{\rho}{R} \right). $$

This means that the eigenvectors of $\mathbf{A}$ form an angle less than $\mathcal{O}(\frac{\rho}{R})$ with either $T$ or $N$. For the non-generic situation of a multiple eigenvalue, one chooses arbitrarily the vectors of an orthogonal basis of the corresponding eigenspace. Since no more than $d$ pairwise orthogonal vectors can make a small angle with the $d$-dimensional space $T$, and the same holds for the $(N-d)$-dimensional space $T$, we know that $d$ eigenvectors form an angle $\mathcal{O}(\frac{\rho}{R})$ with $T$ and the $(N-d)$ others, an angle $\mathcal{O}(\frac{\rho}{R})$ with $N$. Multiplying the left hand side of (79) by $v_T^t$, and the left hand side of (80) by $v_N^t$, we get:

$$ \begin{aligned} (\cos \theta) v_T^t \mathbf{A}_{TT} v_T + (\sin \theta) v_T^t \mathbf{A}_{TN} v_N &= \lambda(\cos \theta), \\ (\cos \theta) v_N^t \mathbf{A}_{TN} v_T + (\sin \theta) v_N^t \mathbf{A}_{NN} v_N &= \lambda(\sin \theta). \end{aligned} $$

When the angle between the eigenvector $v$ and the space $T$ is in $\mathcal{O}(\frac{\rho}{R})$, then $|1-\cos \theta| = \mathcal{O}(\frac{\rho^2}{R^2})$ and $|\sin \theta| = \mathcal{O}(\frac{\rho}{R})$. The first equation implies that $\lambda$ approximately equals $v_T^t \mathbf{A}_{TT} v_T \ge C_{TT} \rho^2$. When the angle between the eigenvector $v$ and the space $N$ is in $\mathcal{O}(\frac{\rho}{R})$, the second equation implies that $\lambda = \mathcal{O}(\frac{\rho^2}{R^2})$, which is smaller than $C_{TT} \rho^2$ for $\frac{\rho}{R}$ small enough.

So far we have proven that the $d$ orthonormal eigenvectors $v_1, \dots, v_d$ corresponding to the $d$ largest eigenvalues of $\mathbf{A}$ form an angle with $T_{\pi_M(p)}\mathcal{M}$ that is upper bounded by $C(\frac{\rho}{R})$, for some constant $C$ that depends only upon $d$ and $\eta$. For any unit vector $u$, its angle with $T_{\pi_M(p)}\mathcal{M}$ satisfies:

$$ \sin \angle u, T_{\pi_M(p)}\mathcal{M} = \|u - \pi_{T_{\pi_M(p)}\mathcal{M}}(u)\|. $$

Any unit vector $u = \sum_{i=1,d} a_i v_i$ in the $d$-space spanned by $v_1, \dots, v_d$ satisfies:

$$ \begin{aligned} \sin \angle u, T_{\pi_M(p)}\mathcal{M} &= \left\| \sum_{i=1,d} a_i v_i - \pi_{T_{\pi_M(p)}\mathcal{M}} \left( \sum_{i=1,d} a_i v_i \right) \right\| \\ &= \left\| \sum_{i=1,d} a_i \left( v_i - \pi_{T_{\pi_M(p)}\mathcal{M}}(v_i) \right) \right\| \\ &\le \sum_{i=1,d} |a_i| \left\| v_i - \pi_{T_{\pi_M(p)}\mathcal{M}}(v_i) \right\| \\ &\le \sum_{i=1,d} |a_i| C \left( \frac{\rho}{R} \right) \le \sqrt{d} C \left( \frac{\rho}{R} \right), \end{aligned} $$

since $\sum_{i=1,d} a_i^2 = 1$, we conclude that $\sum_{i=1,d} |a_i| \le \sqrt{d}$. $\square$

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