# Local Conditions for Triangulating Submanifolds of Euclidean Space

Jean-Daniel Boissonnat, Ramsay Dyer, Arijit Ghosh, Andre Lieutier, Mathijs Wintraecken

► To cite this version:

Jean-Daniel Boissonnat, Ramsay Dyer, Arijit Ghosh, Andre Lieutier, Mathijs Wintraecken. Local Conditions for Triangulating Submanifolds of Euclidean Space. Discrete and Computational Geometry, 2021, 66 (2), pp.666-686. 10.1007/s00454-020-00233-9. hal-03372073

HAL Id: hal-03372073

https://amu.hal.science/hal-03372073

Submitted on 9 Oct 2021

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_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Local Conditions for Triangulating Submanifolds of Euclidean Space

Jean-Daniel Boissonnat¹ · Ramsay Dyer¹ · Arijit Ghosh² · Andre Lieutier³ · Mathijs Wintraecken⁴

Received: 12 June 2019 / Revised: 20 February 2020 / Accepted: 6 July 2020 / Published online: 10 August 2020
© The Author(s) 2020

## Abstract

We consider the following setting: suppose that we are given a manifold $M$ in $\mathbb{R}^d$ with positive reach. Moreover assume that we have an embedded simplicial complex $\mathcal{A}$ without boundary, whose vertex set lies on the manifold, is sufficiently dense and such that all simplices in $\mathcal{A}$ have sufficient quality. We prove that if, locally, interiors of the projection of the simplices onto the tangent space do not intersect, then $\mathcal{A}$ is a triangulation of the manifold, that is, they are homeomorphic.

**Keywords** Triangulation criteria · Pseudo-manifolds · Submanifolds of Euclidean space · Whitney

## 1 Introduction

Triangulations have played a central role in Computational Geometry since its foundation, Delaunay triangulations being the ones that have been studied most frequently [1,2,11,20]. One of the main applications of Delaunay triangulations was to find triangulations of surfaces or, more generally, manifolds embedded in Euclidean space. Sometimes a distinction is made between meshing, where one assumes that the manifold is known, and reconstruction or learning, where one cannot query the manifold as needed but can only use a given sample.

Although the Computational Geometry community has mainly focused on Delaunay triangulations (until recently), the classical mathematics literature did not constrain

Editor in Charge: Kenneth Clarkson

This work has been funded by the European Research Council under the European Union’s ERC Grant Agreement number 339025 GUDHI (Algorithmic Foundations of Geometric Understanding in Higher Dimensions). The third author is supported by Ramanujan Fellowship (No. SB/S2/RJN-064/2015), India. The fifth author also received funding from the European Union’s Horizon 2020 research and innovation programme under the Marie Skłodowska-Curie Grant Agreement No. 754411.

Extended author information available on the last page of the article
itself to it [7,21]. This paper, together with its companion [3], places itself in this
broader scope.

In the Delaunay setting, the closed ball property [14] is often used to prove that a simplicial complex<fnref n="1" /> is homeomorphic to the manifold in question, see for example [1]. Edelsbrunner and Shah [14] defined the restricted Delaunay complex of a submanifold *M* of Euclidean space as the nerve of the Voronoi diagram on *M* when the ambient Euclidean metric is used. They showed that if *M* is compact, then the restricted Delaunay complex is homeomorphic to *M* when the Voronoi diagram satisfies the closed ball property: Voronoi faces are closed topological balls of the appropriate dimension. The closed ball property is purely topological and finding sampling conditions that ensure that the closed ball property holds is not easy [8,11].

In this paper we will assume that $M$ is a $C^2$ submanifold of $\mathbb{R}^d$, whose (positive) reach is denoted by $\mathring{r}$. The *reach of* $M$, defined by [15], is the infimum of distances between points in $M$ and points in its *medial axis*, the points in ambient space for which there does not exist a unique closest point in $M$. The tangent space of $M$ at a point $p$ is denoted by $T_pM$.

A first attempt to depart from the use of the closed ball property and to define conditions similar in spirit to those reported in this paper can be found in [4]. In [3] we explored triangulation conditions in a very general setting, which does not require the manifold to be embedded, and for general maps. The conditions were chosen such that they are more directly applicable compared to the closed ball property.

The triangulation criteria of [3] encompass tangential Delaunay complexes [4], and the intrinsic triangulations explored in [12]. The search for a universal framework incorporating [4,12] was the main motivation for [3]. The new conditions we introduce in this paper are of the same vein as those results. There are however also noticeable differences:

- The setting of [3] is more abstract. In this paper we restrict ourselves to submanifolds of Euclidean space. This affords a more precise analysis and thus better constants.

- The conditions in [3] were formulated in terms of *vertex sanity*. Vertex sanity says that if a vertex is mapped by a 'nice' coordinate map into the star of some (other) vertex, then the vertex is in fact a vertex of this star. This is quite different from the conditions that we formulate here.

- In [3] the simplicial complex $\mathcal{A}$ was assumed to be a piecewise linear (PL) manifold [18,19]. This condition is much stronger than the one we examine here.

The conditions in this paper are very natural and seem to be generally applicable and complementary to the results of [3]. In particular, they apply to a recent triangulation algorithm due to one of the authors of the present paper [10].

In this algorithm, the triangulation is found as the support of a simplicial cycle over $\mathbb{Z}/2\mathbb{Z}$. As such, it is pure and any (m-1)-simplex has an even number of (and therefore at least 2) m-dimensional *cofaces*.<fnref n="2" /> It is therefore what is called below a *simplicial complex without boundary*. It is proven in [10] that, under precise sampling conditions,

<footnote n="1">¹ An (abstract) simplicial complex is a collection $\mathcal{K}$ of finite non-empty sets, called simplices, such that if $\sigma$ is an element of $\mathcal{K}$, so is every non-empty subset of $\sigma$; see for example [18, p. 15].</footnote>

<footnote n="2">² If $\tau$ is a face of $\sigma$, we call $\sigma$ a coface of $\tau$, see for example [13, p. 52].</footnote>
the support of this minimal cycle meets both the topological and the local geometrical conditions required by Theorem 1.6 below. These conditions can be informally stated as follows:

*Simplicial complexes without boundary* We make a topological assumption on $\mathcal{A}$, namely that $\mathcal{A}$ is $m$-dimensional and each $(m-1)$-simplex in $\mathcal{A}$ has at least two $m$-dimensional cofaces. We call a complex satisfying these conditions a simplicial complex without boundary (Definition 3.6). We stress that this is a rather weak topological assumption compared to the condition of being a combinatorial $m$-manifold, which requires the link$^3$ of any $k$-simplex to be homeomorphic to the $(m-k-1)$-sphere $\mathbb{S}^{m-k-1}$.

*Local geometric conditions* We assume that the simplex diameters are small with respect to rch $M$ and that the ratio between the smallest height and the diameter of each simplex is lower bounded by some constant (see Theorem 1.6(a) for a precise statement). Moreover, for any $p \in \mathcal{P}$, two $m$-simplices lying in a small neighborhood of $p$ have disjoint interior projection on the plane tangent to $M$ at $p$ (Theorem 1.6(b)).

Intuitively, once the interiors of the (local) projection of $m$-simplices on a local tangent plane of $M$ are disjoint, the conditions for homeomorphism seem not far. In fact we will see that $\mathcal{A}$ is ambient isotopic to $M$.

Even though we have specific applications in mind, we formulate the statements in a setting that is as general as possible, albeit in the embedded setting. This is in the hope that it will be used in a wide range of applications in Manifold Meshing and Learning. We restrict ourselves to connected manifolds since the extension to non-connected manifolds consists merely of applying the result to each connected component.

## 1.1 Notation

**Notation 1.1 (Simplex quality)** The thickness of an $m$-simplex $\boldsymbol{\sigma}$, denoted $t(\boldsymbol{\sigma})$, is given by $a/mL$, where $a = a(\boldsymbol{\sigma})$ is the smallest altitude of $\boldsymbol{\sigma}$ and $L = L(\boldsymbol{\sigma})$ is the length of the longest edge. The altitude of a vertex in a simplex is the distance from the vertex to the affine hull of the opposite face. Observe that $t(\boldsymbol{\sigma}) \le 1/m$ and we have conjectured in [9] that the largest thickness that can be achieved is in fact $O(m^{-3/2})$. We set $t(\boldsymbol{\sigma}) = 1$ if $\boldsymbol{\sigma}$ has dimension 0.

**Remark 1.2** A sliver is a simplex whose thickness is small compared to its longest edge length. In Theorem 1.6 we will exclude slivers by assuming a lower bound on $t(\boldsymbol{\sigma})/L$.

**Notation 1.3 (Simplicial complexes)** We consider a simplicial complex $\mathcal{A}$ whose vertex set $\mathcal{A}^0$ is identified with a finite set $\mathcal{P} \subset \mathbb{R}^N$. The carrier of $\mathcal{A}$ (i.e., the underlying topological space), is denoted $|\mathcal{A}|$, and we have a natural piecewise linear

<footnote>$^3$ Let $\sigma$ be a simplex of a complex $K$. The star of $\sigma$ in $K$, denoted by $\text{star}\sigma$, is the union of the interiors of all simplices of $K$ having $\sigma$ as a face. The closure of $\text{star}\sigma$ is denoted $\overline{\text{star}}\sigma$; it is the union of all simplices of $K$ having $\sigma$ as a face and is called the closed star of $\sigma$ in $K$. The link of $\sigma$ in $K$, denoted by $\text{link}\sigma$, is a union of all simplices of $K$ lying in $\overline{\text{star}}\sigma$ that are disjoint from $\sigma$. Here we followed [18, p. 371], see also [19, p. 23].</footnote>
map $\iota: |\mathcal{A}| \to \mathbb{R}^N$, but we do not assume a priori that $\iota$ is an embedding, i.e., we cannot assume that $|\mathcal{A}| \subset \mathbb{R}^N$. Nonetheless, we identify the simplices in $\mathcal{A}$ with their image under $\iota$, and when there is no ambiguity, $\sigma \in \mathcal{A}$ may refer to a geometric simplex $\iota(\sigma) \subset \mathbb{R}^N$ as well as the abstract simplex $\sigma \in \mathcal{A}$. Similarly, we write $x \in |\mathcal{A}|$ as a shorthand for $x \in \iota(|\mathcal{A}|)$.

**Notation 1.4** (Projection maps) We denote by $\mathrm{pr}_{T_pM}$ the projection on the tangent plane $T_pM$, by $\mathrm{pr}_M$ the closest point projection onto the manifold, and by $\mathrm{pr}_M|_{|\mathcal{A}|}$ the composition $\mathrm{pr}_M \circ \iota$.

**Notation 1.5** (Balls) $B(x, \rho)$ and $B^\circ(x, \rho)$ respectively denote the closed and open ball with center $x$ and radius $\rho$.

## 1.2 Main Result

**Theorem 1.6** (Triangulation of submanifolds) Let $M \subset \mathbb{R}^N$ be a connected $C^2$ m-dimensional submanifold of $\mathbb{R}^N$ with reach $\mathrm{rch}\,M > 0$, and $\mathcal{P} \subset M$ a finite set of points. Suppose that $\mathcal{A}$ is an m-dimensional simplicial complex without boundary, as in Definition 3.6, whose vertex set $\mathcal{A}^0$ is identified with $\mathcal{P}$. Let $L, t > 0$ be such that for any m-simplex $\sigma \in \mathcal{A}$ one has $t \le t(\sigma)$ and $L(\sigma) \le L$. Suppose that the following conditions are satisfied.

(a) All simplices are small with respect to the reach, and with respect to their quality:

$$ \frac{L}{\mathrm{rch}\,M} \le \min \left( \frac{1}{8}, t \sin \frac{\pi}{8} \right). \qquad (1) $$

(b) The projection of m-simplices on local tangent planes have disjoint interiors: for every $p \in \mathcal{P}$ and $\sigma_1, \sigma_2 \in \mathcal{A}$ with $|\sigma_1|, |\sigma_2| \subset B(p, 2.8L)$,

$$ \sigma_1 \neq \sigma_2 \Rightarrow \mathrm{pr}_{T_pM}(|\sigma_1|)^\circ \cap \mathrm{pr}_{T_pM}(|\sigma_2|)^\circ = \emptyset, $$

where the superscript $\circ$ denotes the interior operator.

Then, the following conclusions hold:

(i) The inclusion $\iota: |\mathcal{A}| \to \mathbb{R}^N$ is an embedding, and we can identify $\iota(|\mathcal{A}|)$ with $|\mathcal{A}|$.

(ii) The closest-point projection map $\mathrm{pr}_M|_{|\mathcal{A}|}: |\mathcal{A}| \to M$ is a homeomorphism, so $M$ is compact, and there is an ambient isotopy bringing $|\mathcal{A}|$ to $M$.

**Remark 1.7** Thanks to condition (a) there are no slivers.

**Remark 1.8** As noticed in Notation 1.1, $t$ decreases with $m$ and the bound on $L/\mathrm{rch}\,M$ in condition (a) decreases at least as fast as $O(1/m)$ or perhaps $O(m^{-3/2})$ as the dimension $m$ of the manifold increases.

**Remark 1.9** Condition (a) of the theorem could be improved with minor, only quantitative, changes in the proof. In the bound (1) there is in fact a trade-off between the constant bound (i.e., $1/8$) and the bound depending on $t$ (i.e., $t \sin(\pi/8)$). The latter one could be replaced by any value strictly below $t \sin(\pi/4)$ by a sufficiently large reduction in the constant bound, which is certainly better for large $m$, since, as seen in the previous remark, $t$ may decrease as fast as $O(m^{-3/2})$.
## 2 Definitions and Submanifold Geometry

In this section, we make the following assumptions.

**Hypothesis 2.1** (Geometric assumptions) $M \subset \mathbb{R}^N$ is a connected $C^2$ $m$-dimensional submanifold of $\mathbb{R}^N$ with positive reach, rch $M > 0$, and $\mathcal{P} \subset M$ is a finite set of points. $\mathcal{A}$ is an $m$-dimensional simplicial complex whose vertex set $\mathcal{A}^0$ is identified with $\mathcal{P}$. Let $L$ and $t$ be positive real numbers such that for any $m$-simplex $\sigma \in \mathcal{A}$,

$$t \le t(\sigma) \quad \text{and} \quad L(\sigma) \le L.$$

We now recall the following five results. Lemma 2.2 is proven in [5, Cor. 2]. Lemma 2.3 is a variant of a result of Whitney [21, Sect. IV.15] proven in [2, Lem. 8.11]. Lemma 2.4 is proven in [5, Cor. 3], Lemma 2.5 is proven in [15, Thm. 4.8(7)], and Lemma 2.6 is proven in [2, Lem. 7.9].

**Lemma 2.2** (Tangent balls) For any $p \in M$, any open ball $B^\circ(c, r)$ that is tangent to $M$ at $p$ and whose radius $r$ satisfies $r \le \text{rch } M$ does not intersect $M$.

**Lemma 2.3** (Simplex-tangent space angle bounds) Under Hypothesis 2.1, if $\sigma \in \mathcal{A}$ and $p$ is a vertex of $\sigma$, then

$$\sin \angle(\sigma, T_p M) \le \frac{L}{t \text{rch } M}.$$

**Lemma 2.4** (Variation of tangent space) Under Hypothesis 2.1, if $p, q \in M$, then

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

**Lemma 2.5** (Distance to tangent space) Under Hypothesis 2.1, if $p, q \in M$, then

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

**Lemma 2.6** (Hausdorff distance between $M$ and $|\mathcal{A}|$) Under Hypothesis 2.1, if $x$ is in $|\mathcal{A}|$, then

$$\|\text{pr}_M(x) - x\| < \frac{2L^2}{\text{rch } M}.$$

Apart from the results we just recalled we will also use

**Lemma 2.7** (Hausdorff distance between a simplex and its vertices) For any compact set $C \subset \mathbb{R}^d$ with diameter $L$ (the largest distance between any two points in $C$) the following statement about the convex hull of $C$, hull $C$, holds: for every $x \in$ hull $C$ there exists $p \in C$ such that

$$\|x - p\| \le L \sqrt{\frac{d}{2(d+1)}} < \frac{L}{\sqrt{2}}.$$

<figure><img src="image_2.png" /></figure>
<figure><img src="image_3.png" /><figcaption>Fig. 1 The notation for Lemma 2.7</figcaption></figure>

In particular, for any simplex $\sigma$ with diameter $L$, if $x \in \sigma$ then there is a vertex $p$ of $\sigma$ such that

$$ \|x - p\| \le L \sqrt{\frac{d}{2(d+1)}} < \frac{L}{\sqrt{2}}. $$

**Proof** Jung’s Theorem [17] says that in the $d$-dimensional Euclidean space, the radius $r$ of the smallest ball enclosing a convex polyhedron is at most $L\sqrt{d/(2(d+1))}$. The compact set $C$ can be approximated arbitrarily well by a finite set $\tilde{C}$ in Hausdorff distance and Jung’s Theorem applies to the convex polyhedron hull $\tilde{C}$.

Since the map that sends a compact set to its convex hull: $C \mapsto$ hull $C$ is 1-Lipschitz for the Hausdorff distance, one can extend Jung’s Theorem by continuity to get the same bound for the smallest ball enclosing hull $C$. Note that $L\sqrt{d/(2(d+1))} \le L/\sqrt{2}$. Let $B(c, r)$ be the smallest ball enclosing $C$. The center $c$ of that ball belongs to hull $C$ since, otherwise, we would decrease the distance of $c$ to any point in $C$ by projecting $c$ to its closest point in hull $C$. We have that any $p \in C$ is at distance at most $r$ from $c$. Moreover, if $x \in$ hull $C \setminus \{c\}$, then there is $p \in C$ extremal in the direction $\tilde{c}x$, see Fig. 1 for an illustration. Let us write $y$ for the orthogonal projection of $p$ on the line $cx$, then the segment $cy$ contains $x$ and the distance to $p$ cannot increase when going from $c$ to $y$. Therefore $d(x, p) \le d(c, p) \le r$. □

## 3 Pseudo-Manifolds, Whitney’s Lemma, and Simplicial Complexes Without Boundary

**Definition 3.1 (Pure simplicial complex)** An $m$-dimensional simplicial complex is pure if any simplex has at least one coface of dimension $m$.
**Definition 3.2 (Pseudo-manifold)** An $m$-dimensional simplicial complex is called a *pseudo-manifold* if it is pure and if any $(m-1)$-simplex has *exactly two $m$-dimensional cofaces*.

**Definition 3.3 (Pseudo-manifold with boundary)** An $m$-dimensional simplicial complex is a *pseudo-manifold with boundary* if it is pure and if any $(m-1)$-simplex has *at most two $m$-dimensional cofaces*. The *boundary* $\partial\mathcal{B}$ of an $m$-dimensional pseudo-manifold simplicial complex $\mathcal{B}$ with boundary, is the $(m-1)$-simplicial complex made of the closure of all $(m-1)$-simplices with exactly one $m$-dimensional coface, that is the simplices and their faces.

**Remark 3.4** Usual definitions of pseudo-manifolds require moreover the complex to be *strongly connected*, which means that its dual graph, i.e., the graph with one vertex for each $m$-simplex and one edge for each pair of $m$-simplices sharing an $(m-1)$-simplex, is connected. In our context, this property is not required in the assumptions of the theorem. It is a consequence of the theorem as we prove a homeomorphism to a manifold.

Our main result (Theorem 1.6) does not require any global orientability for the manifold $M$ or the simplicial complex without boundary $\mathcal{A}$. It applies to non-orientable manifolds as well. However, in the proof of the theorem, we will need to orient locally a pseudo-submanifold of $\mathcal{A}$ with boundary. We first recall that an $m$-chain is the formal sum of $m$-simplices weighted by (integer) coefficients, see [18, p. 27] for a more precise definition or [16, p. 105].

**Definition 3.5 (Oriented pseudo-manifold)** An $m$-dimensional pseudo-manifold with boundary $\mathcal{B}$ is said to be *oriented* if each $m$-simplex is given an orientation such that, if $\Gamma$ is the $m$-chain over $\mathbb{Z}$ (or $\mathbb{R}$) with coefficient 1 on each $m$-simplex of $\mathcal{B}$ then the support of $\partial\Gamma$ is precisely $\partial\mathcal{B}$.

The concept of a pseudo-manifold can be further weakened to a simplicial complex without boundary:

**Definition 3.6 (Simplicial complex without boundary)** An $m$-dimensional simplicial complex is called a *simplicial complex without boundary* if it is pure and if any $(m-1)$-simplex has *at least two $m$-dimensional cofaces*.

**Remark 3.7** We stress that any pseudo-manifold (without boundary) is a simplicial complex without boundary but the converse is not true in general.

Theorem 1.6 actually holds for simplicial complexes without boundary (see Definition 3.6).

**Definition 3.8 (Simplexwise positive map)** Let $\mathcal{B}$ be an oriented $m$-dimensional pseudo-manifold with boundary. A piecewise linear map $F: \mathcal{B} \to \mathbb{R}^m$ is said to be *simplexwise positive* if the image $F(\sigma) = [F(v_0), \dots, F(v_m)]$ of each oriented $m$-simplex $\sigma = [v_0, \dots, v_m] \in \mathcal{B}$ is a non-degenerate $m$-simplex embedded in $\mathbb{R}^m$ and is positively oriented.
Having introduced these definitions, we are ready to state an adapted version of a topological result of Whitney [21, App. II, Sect. 15] which will be the main tool for the proof of Theorem 1.6.

In Lemma 3.9, the simplexwise positive map is piecewise linear instead of being merely assumed piecewise smooth as in Whitney’s original statement. Indeed, this makes the proof simpler and suffices in our context. Also our version states that the map is not only one-to-one but in fact a homeomorphism: this is an easy consequence of Whitney’s original proof as well. The proof given in [21, App. II, Sect. 15] is not very easy to follow, because some small steps are skipped. This is one of the reasons that we have included a detailed proof of the following lemma in the appendix. The other reason is that we altered Whitney’s original statement somewhat to fit the current context.

**Lemma 3.9** (after Whitney) Assume that the following conditions are satisfied:

(C1) $\mathcal{C}$ is an oriented finite m-pseudo-manifold with boundary and $F: |\mathcal{C}| \to \mathbb{R}^m$ is a simplexwise positive map.

(C2) $\mathbf{R} \subset \mathbb{R}^m$ is a connected open set such that $\mathbf{R} \cap F(|\partial \mathcal{C}|) = \emptyset$.

(C3) There exists a point $y \in \mathbf{R} \setminus F(|\mathcal{C}^{m-1}|)$ such that $F^{-1}(y)$ is a single point, where $\mathcal{C}^{m-1}$ denotes the $(m-1)$-skeleton of $\mathcal{C}$.

Then the restriction of $F$ to $F^{-1}(\mathbf{R})$ is a homeomorphism between $F^{-1}(\mathbf{R})$ and $\mathbf{R}$.

# 4 Proof of Theorem 1.6

The proof of Theorem 1.6 makes use of this classical observation:

**Theorem 4.1** (Triangulation of manifolds) Let $H$ be a continuous map from a non-empty $m$-dimensional finite simplicial complex $\mathcal{A}$ to a connected $m$-manifold without boundary $M$. If $H$ is injective and the underlying space $|\mathcal{A}|$ of $\mathcal{A}$ is a manifold without boundary, then $H$ is a homeomorphism.

*Proof* By the invariance of domain theorem [6], we have that $H$ is open and therefore an homeomorphism on its image. Since $\mathcal{A}$ is finite, it is compact and $H(|\mathcal{A}|)$ is the image of an open and compact set by an open and continuous map, and is therefore open and compact. Since $M$ is connected its only open and closed non-empty subset is $M$ itself, therefore $H(|\mathcal{A}|) = M$. $\square$

## 4.1 Overview of the Proof

We establish Theorem 1.6 by means of three primary observations. First, in Sect. 4.2 we show that the conditions of the theorem imply that $\mathcal{A}$ is a manifold (Lemma 4.3). This observation, together with the results obtained in demonstration of it, make it a relatively easy exercise in Sect. 4.3 to demonstrate that $\text{pr}_M|_{|\mathcal{A}|}$ is injective, and therefore, by Theorem 4.1, it is a homeomorphism (Proposition 4.11). Finally, in Sect. 4.4 we show that $|\mathcal{A}|$ and $M$ are ambient isotopic.
## Constants and Definitions

From Lemma 2.6, we have

$$ \|\mathrm{pr}_M(x) - x\| \le \frac{2L^2}{\mathrm{rch} M}, $$

which, together with condition (a) of the theorem, gives

$$ \|\mathrm{pr}_M(x) - x\| \le \eta := \frac{L}{4}. \qquad (2) $$

Here and throughout this section we will assume that $p \in \mathcal{P}$, and we will prove that $\mathcal{A}$ is a manifold in some neighborhood of $p$. For $\rho > 0$, we define $\mathcal{A}_{p,\rho}$ as the subcomplex of $\mathcal{A}$ consisting of all $m$-simplices entirely included in $B(p, \rho)$ together with all their faces:

$$ \mathcal{A}_{p,\rho} = \overline{\{\boldsymbol{\sigma} \in \mathcal{A} \mid \dim(\boldsymbol{\sigma}) = m, \iota(\boldsymbol{\sigma}) \subset B(p, \rho)\}}. $$

The proof relies on the properties of the continuous piecewise linear function

$$ F_p : |\mathcal{A}_{p,2.8L}| \to T_p M $$

defined as the restriction of $\mathrm{pr}_{T_p M}$ to $\iota(|\mathcal{A}_{p,2.8L}|)$. We will focus in particular on the restriction of $F_p$ to $W_p = F_p^{-1}(\mathbf{R}_p)$, where

$$ \mathbf{R}_p = T_p M \cap B^\circ \left( p, \frac{L}{\sqrt{2}} + 2\eta \right) = T_p M \cap B^\circ \left( p, L \left( \frac{1}{\sqrt{2}} + \frac{1}{2} \right) \right). $$

**Remark 4.2** The size of the set $\mathbf{R}_p$ is primarily motivated by convenience in establishing the injectivity of $\mathrm{pr}_M|_{\mathcal{A}}$ (see (13)). The set $\mathcal{A}_{p,2.8L}$ is chosen to be large enough to ensure that condition (C2) of Whitney’s lemma is satisfied for this choice (see (11)).

## 4.2 The Proof that $\mathcal{A}$ is a Manifold

**Lemma 4.3** (Manifold complex) If the conditions of Theorem 1.6 are met, then $\mathcal{A}$ is an $m$-manifold complex with $\{(W_p, F_p)\}_{p \in \mathcal{P}}$ an atlas for $|\mathcal{A}|$.

### Overview of the Proof

We first prove that the map $F_p$ and the set $\mathbf{R}_p$ meet the conditions of Whitney’s lemma, with $C = \mathcal{A}_{p,2.8L}$. Using a separate step for each of the three conditions (C1)–(C3), they are shown to be satisfied which gives a homeomorphism between $W_p$ and $\mathbf{R}_p$, and thus proves that $\mathcal{A}$ is a manifold.
Step 1: (C1) is Satisfied

**Claim 4.4** The *m*-simplices of $\mathcal{A}_{p,2.8L}$ can be oriented in such a way that:

- $\mathcal{A}_{p,2.8L}$ is an oriented pseudo-manifold with boundary,

- $F_p$ is simplexwise positive.

**Proof of Claim 4.4** In order to prove this claim, we need the angle between a simplex $\boldsymbol{\sigma} \in \mathcal{A}_{p,2.8L}$ and the tangent space $T_p M$ to be strictly less than $\pi/2$. If $\boldsymbol{\sigma} \in \mathcal{A}_{p,2.8L}$, consider a vertex $q$ of $\boldsymbol{\sigma}$.

We have from Lemma 2.3 that $\sin \angle(\boldsymbol{\sigma}, T_q M) \le L/(t \text{rch } M)$. From condition (a) of Theorem 1.6, one has $L/(t \text{rch } M) \le \sin(\pi/8)$ and therefore

$$ \angle(\boldsymbol{\sigma}, T_q M) \le \frac{\pi}{8}. \qquad (3) $$

Also, from Lemma 2.4, since $\|p - q\| \le 2.8L$ and using condition (a) of the theorem we have

$$ \sin \frac{\angle(T_p M, T_q M)}{2} \le \frac{\|p - q\|}{2 \text{rch } M} \le \frac{2.8 \times 1/8}{2} = 0.175 < \sin \frac{\pi}{8}. $$

It follows that

$$ \angle(T_p M, T_q M) < \frac{\pi}{4}, $$

which, together with (3) gives

$$ \angle(\boldsymbol{\sigma}, T_p M) < \frac{3\pi}{8}. \qquad (4) $$

Because this angle is less than $\pi/2$, the restriction of $\text{pr}_{T_p M}$ to each *m*-simplex in $\mathcal{A}_{p,2.8L}$ is injective.

For a given orientation of $T_p M$, each *m*-simplex $\boldsymbol{\sigma} \in \mathcal{A}_{p,2.8L}$ is oriented in such a way that $F_p(\boldsymbol{\sigma})$ has positive orientation in $T_p M$.

Consider two distinct simplices $\boldsymbol{\sigma}_1, \boldsymbol{\sigma}_2 \in \mathcal{A}_{p,2.8L}$ sharing a common $(m-1)$-face $\boldsymbol{\mu} = \boldsymbol{\sigma}_1 \cap \boldsymbol{\sigma}_2$. Since $F_p$ is non-degenerate on $\boldsymbol{\sigma}_1$, it is non-degenerate on $\boldsymbol{\mu}$ and $F_p(\boldsymbol{\mu})$ spans a hyperplane $\Pi$ in $T_p M$. Consider a point $o' = F_p(o)$ in the relative interior of $F_p(\boldsymbol{\mu})$ (see Fig. 2). If $V_1$ is a neighborhood of $o$ in $\boldsymbol{\sigma}_1$, then $F_p(V_1)$ covers a neighborhood of $o'$ in one of the half-spaces bounded by $\Pi$. The same holds for a neighborhood $V_2$ of $o$ in $\boldsymbol{\sigma}_2$ and then condition (b) of the theorem enforces these two half-spaces to be distinct.

Following the same argument, we see that $\boldsymbol{\mu}$ cannot have as a coface a third *m*-simplex $\boldsymbol{\sigma}_3$ as there is no room for three pairwise disjoint open half-spaces in $\mathbb{R}^m$ to share a same bounding hyperplane $\Pi$. Thus $\mathcal{A}_{p,2.8L}$ is a pseudo-manifold with boundary.

Now consider $F_p(\boldsymbol{\sigma}_1)$ and $F_p(\boldsymbol{\sigma}_2)$ as simplicial chains with coefficients in $\mathbb{Z}$ and choose any orientation of $F_p(\boldsymbol{\mu})$. It follows from the previous observation that the signs
<figure><img src="image_4.png" /><figcaption>Fig. 2 The notation for the proof of Claim 4.4</figcaption></figure>

of the coefficients of $F_p(\mu)$ in the respective expressions of $\partial F_p(\sigma_1)$ and $\partial F_p(\sigma_2)$ are opposite. It follows that the coefficient of $\mu$ in $\partial(\sigma_1 + \sigma_2)$ is zero. Thus $A_{p,2.8L}$ and $F_p$ meet the respective conditions in Definitions 3.5 and 3.8, and the claim is proven. □

Claim 4.4 yields

**Corollary 4.5** *A is a pseudo-manifold, not just a simplicial complex without boundary.*

**Step 2: (C2) is Satisfied**

In order to be able to apply Whitney’s lemma, we need a second claim. Recall the notation $\mathbf{R}_p = T_p M \cap B^\circ(p, L/\sqrt{2+2\eta})$ and that $F_p$ is the restriction of $\mathrm{pr}_{T_p M}$ to $\iota(|A_{p,2.8L}|)$.

**Claim 4.6** $\mathbf{R}_p \cap F_p(|\partial A_{p,2.8L}|) = \emptyset$.

**Proof of Claim 4.6** Let $x \in |\partial A_{p,2.8L}|$. Since $A$ is a pseudo-manifold without boundary, $x$ must belong to a simplex in $A_{p,2.8L}$ and also to a simplex in $A \setminus A_{p,2.8L}$. The latter condition together with the definition of $A_{p,2.8L}$ implies that

$$x \in B(p, 2.8L) \setminus B(p, 1.8L). \qquad (5)$$

Equations (2) and (5) give

$$\mathrm{pr}_M(x) \in B(p, 2.8L + \eta) \setminus B(p, 1.8L - \eta) = B(p, 3.05L) \setminus B(p, 1.55L).$$

We are now going to decompose $\mathrm{pr}_M(x) - p$ into vectors $\mathbf{u} \in T_p M$ and $\mathbf{v} \in N_p M$, where $N_p M$ denotes the normal space at $p$. One can write (see Fig. 3):

$$\mathrm{pr}_M(x) - p = \mathbf{u} + \mathbf{v}.$$

<figure><img src="image_5.png" /></figure>
<figure><img src="image_6.png" /><figcaption>Fig. 3 The notation for the proof of Claim 4.6</figcaption></figure>

We now bound $||\mathbf{u}||$ and distinguish whether $\mathbf{v} = 0$ or not. If $\mathbf{v} = 0$, i.e., if $\mathrm{pr}_M(x) \in T_pM$, then, since $\mathrm{pr}_M(x) \notin B(p, 1.55L)$, one has $||\mathbf{u}|| \ge 1.55L$. Let us assume now that $\mathbf{v} \ne 0$.

The open ball $B^\circ$ centered at $c = p + (\mathrm{rch} M/||\mathbf{v}||)\mathbf{v}$ with radius $\mathrm{rch} M$ is tangent to $M$ at $p$. Since $\mathrm{pr}_M(x) \in B(p, 3.05L) \setminus B(p, 1.55L)$ and since, from Lemma 2.2, $B^\circ$ has no intersection with $M$, one gets the following pair of inequalities:

$$ (1.55L)^2 < ||\mathbf{u}||^2 + ||\mathbf{v}||^2 \le (3.05L)^2, \quad (6) $$

$$ (\mathrm{rch} M - ||\mathbf{v}||)^2 + ||\mathbf{u}||^2 \ge (\mathrm{rch} M)^2. \quad (7) $$

We first use (7) and the fact that $\mathrm{rch} M \ge 8L$ (by condition (a) of Theorem 1.6) to get

$$ 16L||\mathbf{v}|| - ||\mathbf{v}||^2 \le ||\mathbf{u}||^2. $$

Combining with (6), we obtain

$$ \max \{16L||\mathbf{v}|| - ||\mathbf{v}||^2, (1.55L)^2 - ||\mathbf{v}||^2\} \le ||\mathbf{u}||^2. \quad (8) $$

Note that thanks to (6), $||\mathbf{v}|| < 3.05L$. The minimum of (8) is attained when both terms are equal which happens when $||\mathbf{v}|| = (1.55^2/16)L = 0.15015625L$. This gives us in particular

$$ ||\mathbf{u}|| > 1.54L. $$

Hence we have in both cases, $\mathbf{v} = 0$ and $\mathbf{v} \ne 0$,

$$ ||\mathbf{u}|| = ||\mathrm{pr}_{T_pM}(\mathrm{pr}_M(x)) - p|| > 1.54L. \quad (9) $$
Moreover, since $||x - \text{pr}_M(x)|| < \eta$, (2) reads

$$ \|\text{pr}_{T_p M}(x) - \text{pr}_{T_p M}(\text{pr}_M(x))\| < \eta = 0.25L, \quad (10) $$

since projection reduces length. By the triangle inequality, (9) and (10) give us

$$ \|\text{pr}_{T_p M}(x) - p\| > 1.54L - 0.25L = 1.29L. \quad (11) $$

Therefore, since $\mathbf{R}_p$ is defined as $\mathbf{R}_p = T_p M \cap B^\circ(p, (1/\sqrt{2} + 0.5)L)$, we have proven that $x \in \partial A_{p,2.8L}$ implies $\text{pr}_{T_p M}(x) \notin \mathbf{R}_p$. It follows that

$$ \mathbf{R}_p \cap F_p(|\partial A_{p,2.8L}|) = \emptyset, $$

which ends the proof of the claim.

□

### Step 3: (C3) is Satisfied

We now denote by $\mathcal{C}^{m-1} = \mathcal{A}_{p,2.8L}^{m-1}$ the $(m-1)$-skeleton of $\mathcal{A}_{p,2.8L}$, i.e., the simplicial complex made of simplices of $\mathcal{A}_{p,2.8L}$ of dimension at most $m-1$. Since $F_p(|\mathcal{C}^{m-1}|)$ is a finite union of $(m-1)$-dimensional simplices, it cannot cover the projection of an $m$-simplex. Therefore condition (b) of Theorem 1.6 shows that there is a $y \in \mathbf{R}_p \setminus F_p(|\mathcal{C}^{m-1}|)$ such that $F_p^{-1}(y)$ is a single point. All conditions (C1)–(C3) being satisfied, Whitney’s lemma applies, proving the following proposition:

**Proposition 4.7** For any $p \in \mathcal{P}$, the restriction of $F_p$ to $F_p^{-1}(\mathbf{R}_p)$ is a homeomorphism from $F_p^{-1}(\mathbf{R}_p)$ to $\mathbf{R}_p$.

### Step 4: Proof of Lemma 4.3

We start with an easy lemma.

**Lemma 4.8** For any $p \in \mathcal{P}$ one has

$$ \mathcal{A} \cap B(p, L) \subset F_p^{-1}(\mathbf{R}_p) \subset \mathcal{A} \cap B(p, 2.8L). $$

**Proof** Recall that $F_p$ is the restriction of $\text{pr}_{T_p M}$ to $|\mathcal{A}_{p,2.8L}|$. By definition of $\mathcal{A}_{p,2.8L}$, and since the diameter of any simplex is upper bounded by $L$, one has

$$ |\mathcal{A}| \cap B(p, 1.8L) \subset \mathcal{A}_{p,2.8L} \subset |\mathcal{A}| \cap B(p, 2.8L). \quad (12) $$

The second inclusion in the statement of the lemma follows from the second inclusion in (12) and the definition of $F_p$. If $x \in |\mathcal{A}| \cap B(p, L)$ then $x \in \mathcal{A}_{p,2.8L}$. Since $\text{pr}_{T_p M}(B(p, L)) \subset B(p, L)$,

$$ \text{pr}_{T_p M}(\mathcal{A} \cap B(p, L)) \subset T_p M \cap B(p, L) \subset \mathbf{R}_p. $$

This shows that $\mathcal{A} \cap B(p, L) \subset F_p^{-1}(\mathbf{R}_p)$. □

<figure><img src="image_7.png" /></figure>
**Claim 4.9** For any $p \in \mathcal{P} = \mathcal{A}^0$, the restriction of $F_p$ to $W_p = F_p^{-1}(\mathbf{R}_p)$ yields a homeomorphism onto $\mathbf{R}_p$. Thus $|\mathcal{A}|$ is a manifold, and $\{(W_p, F_p)\}_{p \in \mathcal{P}}$ is an atlas for $|\mathcal{A}|$.

*Proof* From Whitney's lemma, $F_p$ defines a homeomorphism from $W_p$ to $\mathbf{R}_p$. It follows that $W_p = F_p^{-1}(\mathbf{R}_p)$ is an open $m$-manifold that contains the star of $p$, since $F_p^{-1}(\mathbf{R}_p) \supset \mathcal{A} \cap B(p, L)$ (Lemma 4.8). Therefore, because any $y \in \mathcal{A}$ belongs to the star of some vertex $p$, we have that $|\mathcal{A}|$ is a manifold and $\{(W_p, F_p)\}_{p \in \mathcal{P}}$ is an atlas. □

This completes the proof of Lemma 4.3.

**Remark 4.10** In order to establish that $\mathcal{A}$ is a manifold, we need only consider sets $U_p$ that are large enough to ensure that $\{(U_p, F_p)\}_{p \in \mathcal{P}}$ is an atlas. The sets $W_p$ are larger than we need; by Lemma 2.7, it would be sufficient to take $U_p = B(p, L/\sqrt{2}) \cap \iota(|\mathcal{A}|)$. Notice that, since $\mathrm{pr}_{T_p M}$ does not increase distances, $F_p(U_p)$ is contained in the set $T_p M \cap B(p, L/\sqrt{2})$. We used larger sets for convenience in demonstrating below that $\mathrm{pr}_M|_{|\mathcal{A}|}$ is injective (Proposition 4.11).

Also, the existence of the manifold $M$ is not essential in the demonstration that $\mathcal{A}$ is manifold; it suffices to have a collection of hyperplanes $\{T_p\}_{p \in \mathcal{P}}$ such that $T_p$ makes a sufficiently small angle with all $m$-simplices that lie sufficiently close to the vertex $p$.

## 4.3 The Proof that $\mathrm{pr}_M|_{|\mathcal{A}|}$ is a Homeomorphism

**Proposition 4.11** ($\mathrm{pr}_M|_{|\mathcal{A}|}$ is a homeomorphism) Let $M \subset \mathbb{R}^N$ be a connected $C^2$ $m$-dimensional submanifold of $\mathbb{R}^N$ with reach $M > 0$, and $\mathcal{P} \subset M$ a finite set of points. Suppose that $\mathcal{A}$ is an $m$-dimensional manifold simplicial complex whose vertex set, $\mathcal{A}^0$, is identified with $\mathcal{P}$. Let $L, t > 0$ be such that for any $m$-simplex $\sigma \in \mathcal{A}$ one has $t \le t(\sigma)$ and $L(\sigma) \le L$. If

(a) all simplices are small with respect to the reach, and with respect to their quality:

$$ \frac{L}{\mathrm{rch} M} \le \min \left( \frac{1}{8}, t \sin \frac{\pi}{8} \right); $$

(b) $\{(W_p, F_p)\}_{p \in \mathcal{P}}$ is an atlas for $|\mathcal{A}|$;

then

(i) The closest-point projection map $\mathrm{pr}_M|_{|\mathcal{A}|}$ is a homeomorphism $|\mathcal{A}| \to M$.

(ii) The inclusion $\iota: |\mathcal{A}| \to \mathbb{R}^N$ is an embedding.

*Proof* Let $x, y \in \mathcal{A}$. For convenience, we will write $x' = \mathrm{pr}_M(x)$, $x'' = \mathrm{pr}_{T_p M}(x)$ and similarly for $y, y'$, and $y''$ (see Fig. 4). Assume that $\|x - y\| \ge 2\eta$. From Lemma 2.6, we have $\|x' - x\| < \eta$ and $\|y' - y\| < \eta$. The triangle inequality then shows that $\|x' - y'\| > 0$ and therefore $x' \neq y'$.
<figure><img src="image_8.png" /><figcaption>Fig. 4 For the definition of x', x'', y', y''</figcaption></figure>

Assume now that $x, y \in A$ with $x \neq y$ and $\|x - y\| < 2\eta$, and let us prove that $x' \neq y'$. From Lemma 2.7, we know that there is $p \in P$ such that $\|x - p\| < L/\sqrt{2}$ and therefore one has

$$x, y \in B \left( p, \frac{L}{\sqrt{2}} + 2\eta \right). \qquad (13)$$

It follows that $x'', y'' \in T_p M \cap B(p, L/\sqrt{2} + 2\eta)$ and, with the notations of Whitney's lemma applied in a neighborhood of $p$, this translates to $F_p(x), F_p(y) \in \mathbf{R}_p$ and $x, y \in F_p^{-1}(\mathbf{R}_p)$.

Since $F_p$ is a homeomorphism from $F_p^{-1}(\mathbf{R}_p)$ to $\mathbf{R}_p$ (Claim 4.9), it has a continuous inverse $F_p^{-1}: \mathbf{R}_p \to F_p^{-1}(\mathbf{R}_p)$ and the set $F_p^{-1}(\mathbf{R}_p)$, considered as a subset of $\mathbb{R}^N$, can then be seen as the graph of a continuous map $\phi$:

$$\phi: \mathbf{R}_p \to N_p M, \quad z \mapsto F_p^{-1}(z) - z,$$

where $N_p M$ denotes the normal space at $p$. Let $\sigma$ be a simplex in $A$ with a non-empty intersection with $F_p^{-1}(\mathbf{R}_p)$. Since $F_p^{-1}(\mathbf{R}_p) \subset A_{p,2.8L}$ (Lemma 4.8), we have that $\sigma \in A_{p,2.8L}$. By (4),

$$\angle(\sigma, T_p M) < \frac{3\pi}{8}.$$

Since the graph of $\phi$ restricted to $\mathbf{R}_p$ is made of a (finite) number of simplices whose angles with $T_p M$ are less than $3\pi/8$, $\phi$ is Lipschitz with constant tan($3\pi/8$). It follows that, with $x$ and $y$ as in (13),

$$\|\phi(y'') - \phi(x'')\| \le \tan \frac{3\pi}{8} \cdot \|y'' - x''\|,$$

and then

$$\angle(T_p M, y - x) < \frac{3\pi}{8}. \qquad (14)$$

On the other hand, since $x \in B(p, L/\sqrt{2} + 2\eta)$ and $\|x - x'\| < \eta$ we have

$$x' \in B \left( p, \frac{L}{\sqrt{2}} + 3\eta \right), \qquad (15)$$

<figure><img src="image_9.png" /></figure>
and, since $\eta = 0.25L$,

$$x' \in B(p, 1.46L). \qquad (16)$$

Equation (15) together with Lemma 2.4 and $L/\text{rch } M \le 1/8$ (condition (a) of Theorem 1.6) gives

$$\sin \frac{\angle(T_p M, T_{x'} M)}{2} \le \frac{1.46L}{2 \text{rch } M} \le 0.09125 < \sin \frac{\pi}{16}.$$

It follows that

$$\angle(T_p M, T_{x'} M) < \frac{\pi}{8}.$$

Therefore, if we assume for a contradiction that $x' = y'$, we have that $x - y$ is orthogonal to $T_{x'} M$, that is $\angle(T_{x'}, y - x) = \pi/2$, and one gets

$$\angle(T_p M, y - x) > \frac{\pi}{2} - \frac{\pi}{8} = \frac{3\pi}{8},$$

a contradiction with (14). This concludes the proof that $\text{pr}_M|_{|A|}$ is injective. We now can apply Theorem 4.1 which completes the proof of the first claim of the proposition.

Since $\text{pr}_M|_{|A|}$ is defined as $\text{pr}_M \circ \iota$, the fact that it is a homeomorphism implies the second claim of the proposition: $\iota$ is an embedding. Proposition 4.12 below applies and we get the required ambient isotopy. □

## 4.4 Ambient Isotopy

**Proposition 4.12** Let $M$ be an $m$-dimensional submanifold of Euclidean space $\mathbb{R}^N$ with reach $\text{rch } M > 0$ and $|A|$ a subset of $\mathbb{R}^N$ such that:

(i) $\sup_{x \in |A|} \inf_{y \in M} d(x, y) < \text{rch } M$;

(ii) the restriction of $\text{pr}_M$, the closest map projection on $M$ to $|A|$, is an homeomorphism.

Then $|A|$ and $M$ are ambient isotopic.

One can observe that by definition of $\text{rch } M$, condition (i) ensures that the definition of $\text{pr}_M$ in (ii) is unambiguous.

**Proof** By the conditions of the lemma, there are real numbers $a$ and $b$ such that

$$\sup_{x \in |A|} d(x, \text{pr}_M(x)) < a < b < \text{rch } M.$$

We define a map $\Psi: [0, 1] \times \mathbb{R}^N \to \mathbb{R}^N$ as follows. Denote by $M^{\oplus b}$ the $b$-offset of $M$, that is, the set of all points in the ambient space at most a distance $b$ from the set $M$.
For $x \in M^{\oplus b}$ we know that $x \mapsto \text{pr}_M(x) \in M$ and

$$x \mapsto \alpha(x) = \text{pr}_M|_{\mathcal{A}}^{-1}(\text{pr}_M(x)) \in \mathcal{A}$$

are continuous. For $x \in M^{\oplus b}$, $x$ and $\alpha(x)$ are in the ball $B$ centered at $\text{pr}_M(x)$ with radius $b$ in the normal space to $M$ at $\text{pr}_M(x)$. One has $x \in |\mathcal{A}|$ iff $x = \alpha(x)$, and if $x \neq \alpha(x)$ one defines $\beta(x)$ to be the intersection point of the boundary of $B$ with the half-line starting at $\alpha(x)$ and going through $x$.

Define also the real valued function

$$x \mapsto \lambda(x) = \frac{\|x - \alpha(x)\|}{\|\beta(x) - \alpha(x)\|}.$$

Observe that if $x \neq \alpha(x)$ one has by the definition of $\lambda$ that $x = (1 - \lambda(x))\alpha(x) + \lambda(x)\beta(x)$. Also, since $|\lambda(x)| \le \|x - \alpha(x)\|/(b - a)$, we can check that the map

$$x \mapsto \begin{cases} (1 - \lambda(x))\text{pr}_M(x) + \lambda(x)\beta(x) & \text{if } x \neq \alpha(x), \\ \text{pr}_M(x) & \text{if } x = \alpha(x), \end{cases}$$

is continuous. We can now give an explicit expression for the ambient isotopy $\Psi$:

$$\Psi(t, x) = \begin{cases} x & \text{if } x \notin M^{\oplus b}, \\ (1-t)x + t\text{pr}_M(x) & \text{if } x = \alpha(x), \\ (1-t)x + t((1-\lambda(x))\text{pr}_M(x) + \lambda(x)\beta(x)) & \text{if } x \in M^{\oplus b} \setminus \{\alpha(x)\}. \end{cases}$$

The map $\Psi$ is illustrated in Fig. 5. It is a simple exercise to check that $\Psi$ is continuous both in $t$ and $x$. $\square$

**Acknowledgements** Open access funding provided by the Institute of Science and Technology (IST Austria). Arijit Ghosh is supported by the Ramanujan Fellowship (No. SB/S2/RJN-064/2015), India.

**Open Access** This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.

## Appendix A: Proof of the (Adapted) Whitney Lemma

In this appendix we prove our variation of Whitney’s lemma (Lemma 3.9). The proof consists of five claims.

**Claim A.1** The restriction $F|_{\text{star } \sigma^{m-1}}$ of $F$ to the star star $\sigma^{m-1}$ of some $(m-1)$-simplex $\sigma^{m-1}$ of $C$, with $\sigma^{m-1} \notin \partial C$, is injective and open.
<figure><img src="image_10.png" /><figcaption>Fig. 5 An illustration of the map $\Psi$ for $t = 0$ (red) and $t = 1$ (black) in the normal space of a single point</figcaption></figure>

**Proof** For a simplex $\sigma$, let us denote its relative interior by $\text{int} \, \sigma$. By definition of pseudo-manifolds, $\sigma^{m-1} \notin \partial C$ implies that star $\sigma^{m-1}$ is the union of the relative interior $\text{int} \, \sigma_1^m$ and $\text{int} \, \sigma_2^m$ of exactly two proper cofaces ($\sigma_1$ and $\sigma_2$) and the relative interior $\text{int} \, \sigma^{m-1}$ of $\sigma^{m-1}$ itself.

For $x \in \text{int} \, \sigma_i^m$, $i = 1, 2$, the restriction of $F$ to $|\sigma_i^m|$ being a non-degenerate linear map, $F$ is locally open at $x$. Consider now the case where $x \in \text{int} \, \sigma^{m-1}$. $F(x)$ belongs to the boundary of $F(|\sigma_1^m|)$. Moreover, $F(\text{int} \, \sigma^{m-1})$ spans a hyperplane $\Pi$ in $\mathbb{R}^m$ that separates the space into two closed half spaces $H^-$ and $H^+$ with $H^- \cap H^+ = \Pi$.

Then the fact that $C$ is oriented and that $F$ is simplexwise positive implies that $F(|\sigma^{m-1}|)$ appears with opposite orientations in the respective boundaries of $F(|\sigma_1^m|$) and $F(|\sigma_2^m|)$. We assume without loss of generality that $F(|\sigma_1^m|) \subset H^-$: it follows that $F(|\sigma_2^m|) \subset H^+$. Taking $\rho > 0$ smaller than the distance between $F(x)$ and the image of the boundary of the closed star $F(\partial \text{star } \sigma^{m-1})$ we have that

$$B(x, \rho) \subset F(\text{star } \sigma^{m-1}),$$

and we have proven that $F|_{\text{star } \sigma^{m-1}}$ is open.

From the definition of simplexwise positiveness, the restriction of $F$ to any simplex is injective. Because $C$ is a pseudo-manifold star $\sigma^{m-1} \subset |\sigma_1^m| \cup |\sigma_2^m|$. Now suppose there is a pair $x, y \in \text{star } \sigma^{m-1}$ with $x \neq y$ and $F(x) = F(y)$. Let us assume without loss of generality that $x \in |\sigma_1^m|$. Then we must have $y \in |\sigma_2^m|$. But since $F(|\sigma_1^m|) \subset H^-$, $F(|\sigma_2^m|) \subset H^+$ it follows that $F(x) = F(y) \in H^- \cap H^+ = \Pi$.
Then $x, y \in |\sigma^{m-1}|$, but again, since $F$ is one-to-one on each simplex, we get $x = y$. $\square$

**Claim A.2** Suppose that $x, y \in |C \setminus \partial C|$ are such that $x \neq y$ and $F(x) = F(y)$. If $x \in \text{int } \sigma_x$ and $y \in \text{int } \sigma_y$, then $\text{star } \sigma_x \cap \text{star } \sigma_y = \emptyset$.

*Proof* Indeed, otherwise there would be a simplex $\sigma \in \text{star } \sigma_x \cap \text{star } \sigma_y$ such that $x, y \in \sigma$, but we have $x \neq y$ and $F(x) = F(y)$ which contradicts the fact that the restriction of $F$ to $\sigma$ is injective. $\square$

**Claim A.3** $x, y \in \mathbf{R} \setminus F(|C^{m-1}|)$ implies $\# F^{-1}(x) = \# F^{-1}(y)$, where $\# E$ denotes the cardinality of a set $E$.

*Proof* Since $F(|C^{m-2}|)$ is a finite union of simplices of codimension 2, it cannot disconnect the open set $\mathbf{R}$. In other words, $\mathbf{R} \setminus F(|C^{m-2}|)$ is path connected.

Consider $x$ and $y$ as in the claim. Since $\mathbf{R} \setminus F(|C^{m-1}|) \subset \mathbf{R} \setminus F(|C^{m-2}|)$, there exists a path $\gamma: [0, 1] \to \mathbf{R} \setminus F(|C^{m-2}|)$ such that $\gamma(0) = x$ and $\gamma(1) = y$. Assume for a contradiction that for example $\# F^{-1}(x) > \# F^{-1}(y)$ and consider $t_0 = \sup\{t \mid \# F^{-1}(\gamma(t)) \ge \# F^{-1}(x)\}$. Since $\gamma(t_0) \in \mathbf{R} \setminus F(|C^{m-2}|)$, any point $p \in F^{-1}(\gamma(t_0))$ belongs to the relative interior of a simplex $\sigma$ of dimension $m$ or $m-1$. In both cases, thanks to Claim A.1, the restriction of $F$ to the star of $\sigma$ is open and injective. It follows that there are $\# F^{-1}(\gamma(t_0))$ distinct such stars of simplices whose images cover $\gamma(t_0)$. Two such stars star $\sigma_1$ and star $\sigma_2$ are disjoint by Claim A.2. But since the restriction of $F$ to each of these stars of simplices is open, there is an open neighborhood of $\gamma(t_0)$ which is covered at least $\# F^{-1}(\gamma(t_0))$ times, a contradiction with the definition of $x$, $y$, and $t_0$. $\square$

**Claim A.4** The restriction of $F$ to $C \setminus \partial C$ is open.

*Proof* Consider a $k$-simplex $\sigma^k$, $0 \le k \le m$, of $C$ which is not in $\partial C$: $\sigma^k \in C \setminus \partial C$. Take $p \in \text{int } \sigma^k$, where $\text{int } \sigma^k$ is the relative interior of $\sigma^k$. We denote by $L = \text{star } \sigma^k$ the simplicial complex closure of the star of $\sigma_k$. Since $L$ is a subcomplex of $C$, it inherits from $C$ its property to be an oriented pseudo-manifold on which $F$ is simplexwise positive. Also, since $\sigma^k \notin \partial C$ we have $\sigma^k \notin \partial L$. The restriction of $F$ to any $m$-simplex is injective and since any $x \in \partial L$ belongs to some $m$-simplex containing also $p$, we have that $F(p) \notin F(\partial L)$. Since $F(\partial L)$ is compact, there exists an open neighborhood $U \ni q = F(p)$ such that $U \cap F(\partial L) = \emptyset$. We can then apply Claim A.3 to the complex $L$ with $U$ playing the role of $\mathbf{R}$: the number of inverse images in $U \setminus F(L^{m-1})$ is constant. But since the image of any $m$-simplex in $L$, being a non-degenerate full-dimensional simplex containing $q$, intersects $U$, this number is at least one. It follows that $F(L) \supset U \setminus F(L^{m-1})$. $F(L)$ is compact, because $L$ is compact, and therefore $F(L) \supset U \setminus F(L^{m-1}) \supset U$. Since $U \cap F(\partial L) = \emptyset$ we have proven that $U \subset F(L \setminus \partial L)$.

Given a set $A$, a point $p$, and $\epsilon > 0$, denote by $\mathcal{H}_{p,\epsilon}(A) = \{p + \epsilon(a - p) \mid a \in A\}$ the image of $A$ by the homothety with center $p$ and ratio $\epsilon$. Since $F$ is piecewise linear, for any $\epsilon > 0$, one has

$$F(\mathcal{H}_{p,\epsilon}(|L \setminus \partial L|)) = \mathcal{H}_{F(p),\epsilon}(F(|L \setminus \partial L|)) \supset \mathcal{H}_{F(p),\epsilon}(U).$$

<figure><img src="image_11.png" /></figure>
It follows that the image of an arbitrary small neighborhood of $p$ covers an open neighborhood of $q = F(p)$. We have shown that $F$ is open at $p$. But since any point $p \in C \setminus \partial C$ belongs to the relative interior of some simplex in $C \setminus \partial C$, this result applies to any $p \in C \setminus \partial C$. We have thus shown that the restriction of $F$ to $C \setminus \partial C$ is open and the claim is proven. Notice that, since star $\sigma^k$ is open, we get as a consequence of the claim that the image by $F$ of the star of any $k$-simplex $\sigma^k \in C \setminus \partial C$, $0 \le k \le m$, is open. Hence

$$ \sigma^k \in C \setminus \partial C \Rightarrow F(\text{star } \sigma^k) \text{ is open.} \qquad (17) $$

Our last claim will end the proof of the lemma:

**Claim A.5** If there is $q \in \mathbf{R} \setminus F(|C^{m-1}|)$ such that $F^{-1}(q)$ is a single point then the restriction of $F$ to $F^{-1}(\mathbf{R})$ is injective.

*Proof* For a contradiction, assume there are $x, y \in |C \setminus \partial C|$ such that $x \neq y$ and $F(x) = F(y)$. There are two simplices $\sigma_x, \sigma_y \in C \setminus \partial C$ such that $x \in \text{int } \sigma_x$ and $y \in \text{int } \sigma_y$.

It follows from (17) that there are two open sets $U_x$ and $U_y$, respective open neighborhoods of $F(x) = F(y)$, covered respectively by $F(\text{star } \sigma_x)$ and $F(\text{star } \sigma_y)$. Since, from Claim A.2, star $\sigma_x \cap \text{star } \sigma_y = \emptyset$ it follows that the points in $U = U_x \cap U_y$ are covered twice. But since there is $q \in \mathbf{R} \setminus F(|C^{m-1}|)$ such that $F^{-1}(q)$ is a single point, we get from Claim A.3 that any point in $\mathbf{R} \setminus F(|C^{m-1}|)$ is covered once, a contradiction since $U \cap (\mathbf{R} \setminus F(|C^{m-1}|)) \neq \emptyset$. □

So, to conclude, we have proven that under the conditions of the lemma, the restriction of $F$ to $F^{-1}(\mathbf{R})$ is injective (Claim A.5) and open (Claim A.4). Being a one-to-one continuous and open map, the restriction of $F$ to $F^{-1}(\mathbf{R})$ is an homeomorphism on its image $\mathbf{R}$.

## References

1. Amenta, N., Bern, M.: Surface reconstruction by Voronoi filtering. Discrete Comput. Geom. 22(4), 481–504 (1999)

2. Boissonnat, J.-D., Chazal, F., Yvinec, M.: Geometric and Topological Inference. Cambridge Texts in Applied Mathematics. Cambridge University Press, Cambridge (2018)

3. Boissonnat, J.-D., Dyer, R., Ghosh, A., Wintraecken, M.: Local criteria for triangulation of manifolds. In: 34th International Symposium on Computational Geometry. Leibniz International Proceedings in Informatics, vol. 99, # 9. Leibniz-Zent. Inform., Wadern (2018)

4. Boissonnat, J.-D., Ghosh, A.: Manifold reconstruction using tangential Delaunay complexes. Discrete Comput. Geom. 51(1), 221–267 (2014)

5. Boissonnat, J.-D., Lieutier, A., Wintraecken, M.: The reach, metric distortion, geodesic convexity and the variation of tangent spaces. J. Appl. Comput. Topol. 3(1–2), 29–58 (2019)

6. Brouwer, L.E.J.: Beweis der Invarianz des n-dimensionalen Gebiets. Math. Ann. 71(3), 305–313 (1911)

7. Cairns, S.S.: On the triangulation of regular loci. Ann. Math. 35(3), 579–587 (1934)

8. Cheng, S.-W., Dey, T.K., Ramos, E.A.: Manifold reconstruction from point samples. In: 16th Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1018–1027. ACM, New York (2005)

9. Choudhary, A., Kachanovich, S., Wintraecken, M.: Coxeter triangulations have good quality. Math. Comput. Sci. 14(1), 141–176 (2020)
10. Cohen-Steiner, D., Lieutier, A., Vuillamy, J.: Lexicographic optimal chains and manifold triangulations (2019). https://hal.archives-ouvertes.fr/hal-02391190

11. Dey, T.K.: Curve and Surface Reconstruction: Algorithms with Mathematical Analysis. Cambridge Monographs on Applied and Computational Mathematics, vol. 23. Cambridge University Press, Cambridge (2007)

12. Dyer, R., Vegter, G., Wintraecken, M.: Riemannian simplices and triangulations. Geom. Dedicata **179**, 91–138 (2015)

13. Edelsbunner, H., Harer, J.L.: Computational Topology. An Introduction. American Mathematical Society, Providence (2010)

14. Edelsbunner, H., Shah, N.R.: Triangulating topological spaces. Int. J. Comput. Geom. Appl. **7**(4), 365–378 (1997)

15. Federer, H.: Curvature measures. Trans. Am. Math. Soc. **93**, 418–491 (1959)

16. Hatcher, A.: Algebraic Topology. Cambridge University Press, Cambridge (2002)

17. Jung, H.: Ueber die kleinste Kugel, die eine räumliche Figur einschliesst. J. Reine Angew. Math. **123**, 241–257 (1901)

18. Munkres, J.R.: Elements of Algebraic Topology. Addison-Wesley, Menlo Park (1984)

19. Rourke, C.P., Sanderson, B.J.: Introduction to Piecewise-Linear Topology. Springer, Berlin (1982)

20. Shewchuk, J.R.: Lecture Notes on Delaunay Mesh Generation. University of California at Berkeley (2012). https://people.eecs.berkeley.edu/~jrs/meshpapers/delnotes.pdf

21. Whitney, H.: Geometric Integration Theory. Princeton University Press, Princeton (1957)

**Publisher's Note** Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

## Affiliations

Jean-Daniel Boissonnat¹ · Ramsay Dyer¹ · Arijit Ghosh² · Andre Lieutier³ · Mathijs Wintraecken⁴

Jean-Daniel Boissonnat
jean-daniel.boissonnat@inria.fr

Ramsay Dyer
yasmar@gmail.com

Arijit Ghosh
arjitiitkgpster@gmail.com

Andre Lieutier
Andre.LIEUTIER@3ds.com

Mathijs Wintraecken
m.h.m.j.wintraecken@gmail.com

1 Université Côte d'Azur, INRIA Sophia-Antipolis, Nice, France

2 Indian Statistical Institute, Kolkata, India

3 Dassault Systèmes Provence, Aix-en-Provence, France

4 IST Austria, Klosterneuburg, Austria