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

Dominique Attali, André Lieutier

► To cite this version:

Dominique Attali, André Lieutier. Delaunay-like Triangulation of Smooth Orientable Submanifolds by L1-Norm Minimization. SoCG 2022 - 38th International Symposium on Computational Geometry, Jun 2022, Berlin, Germany. pp.8:1-8:16, 10.4230/LIPIcs.SoCG.2022.8 . hal-03844142

HAL Id: hal-03844142

https://hal.science/hal-03844142

Submitted on 8 Nov 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_1.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 ☐

Univ. Grenoble Alpes, CNRS, Grenoble INP, GIPSA-lab, Grenoble, France

André Lieutier ☐

Dassault systèmes, Aix-en-Provence, France

## 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 [3]. Since the objective is a weighted $\ell_1$-norm and the constraints are linear, the triangulation process can thus be implemented by linear programming.

2012 ACM Subject Classification Theory of computation → Computational geometry

**Keywords and phrases** manifold reconstruction, Delaunay complex, triangulation, sampling conditions, optimization, $\ell_1$-norm minimization, simplicial complex, chain, fundamental class

Digital Object Identifier 10.4230/LIPIcs.SoCG.2022.8

Related Version Full Version: https://arxiv.org/abs/2203.06008

**Acknowledgements** We are grateful to the anonymous referees for carefully reading the paper and many helpful suggestions.

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

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

© Dominique Attali and André Lieutier; licensed under Creative Commons License CC-BY 4.0

38th International Symposium on Computational Geometry (SoCG 2022).

Editors: Xavier Goaoc and Michael Kerber; Article No. 8; pp. 8:1–8:16

Leibniz International Proceedings in Informatics

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

LIPICS Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany

<figure><img src="image_4.png" /></figure>
## 8:2 Delaunay-Like Triangulation of Submanifolds by Minimization

the paraboloid $\mathcal{P}$. This variational formulation has been successfully exploited in [1, 14, 17] for 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 [25], 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 [18, 31].

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 *Delloc 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 [3] we show that the Delloc 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 Delloc complex coincides with the *flat Delaunay complex* introduced in our companion paper [3] and is akin to the *tangential Delaunay complex* introduced and studied in [5, 6]. 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 Delloc 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, [13, 9, 19, 10, 20], 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

<footnote n="1">¹ Or relative $d$-cycles when the considered domain has a boundary.</footnote>
manifold, one could – in theory – take either the Čech complex or the Vietoris-Rips complex as the 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 $M$ [12, 11, 4, 29, 24]. Recall that, when $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 $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 $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 $M$ is known. In the full version [2], 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.

The missing proofs may be found in the full version [2].

# 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, $M$ designates a compact connected orientable $C^2$ $d$-dimensional submanifold of $\mathbb{R}^N$ for $d < N$. For any point $m \in M$, the tangent plane to $m$ at $M$ is denoted as $T_m M$. Because $M$ is $C^2$ and therefore $C^{1,1}$, the reach of $M$ is positive [23]. We let $\mathcal{R}$ be a fixed finite constant such that $0 < \mathcal{R} \le \text{reach } M$.
## 2.2 Simplicial complexes

In this section, we review some background notation on simplicial complexes [27]. 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) $\text{dim}(\sigma) = \text{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 = \text{dim} \sigma = \text{dim 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 = \text{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 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 conv $\hat{\sigma}$ is contained in the lower convex hull of $\hat{Q}$ [22].

## 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 conv $Q$. It is well-known that the Delaunay complex of $Q$ optimizes many functionals over the set of triangulations of $Q$ [8, 30, 28], one of them being the Delaunay energy that we shall now define [15]. Let $d = \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 [28, 16].

## 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 [21]. Hence, if $d = \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 [14]. Writing $\text{vol}(\alpha)$ for the $d$-dimensional volume of $\text{conv } \alpha$, we have:

**Lemma 6 ([14]).** 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].$$
8:6 Delaunay-Like Triangulation of Submanifolds by Minimization

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” Σ of d-simplices living in R N by setting E(Σ) = ∑ σ ∈ Σ ω(σ). It is
then tempting to ask what would happen if one minimizes this energy when the vertices of Σ
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 Supp $\gamma$.

3 Delloc 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 Delloc complex of $P$ at scale $\rho$. First, we define the property for a simplex to be delloc.

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

We now state a theorem which establishes conditions under which the Delloc 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 [3]. 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 [7, 6].

**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 $\epsilon, \delta, \rho, \theta \ge 0$ and set $A = 4\delta\theta + 4\rho\theta^2$. Assume that $\theta \le \frac{\pi}{6}, \delta \le \epsilon$ and $16\epsilon \le \rho < \frac{R}{4}$. Suppose that $P$ is a $\delta$-accurate $\epsilon$-dense sample of $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{Dalloc}_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{Dalloc}_d(P, \rho)$ coincides $\text{FlatDel}_M(P, \rho)$, the complex introduced and studied in the companion paper [3]. Since all the results in this paper are based on the delloc property, we find it more enlightening to formulate the results of this paper using the Delloc 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 [3].

**Remark 11.** It is easy to see that if $2R(\sigma) \le \rho$, then a delloc 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 delloc simplex $\sigma$ is a Delaunay simplex of $P$. Hence, under the assumptions of Theorem 10, we have the inclusion $\text{Dalloc}_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}_{M}(\alpha) = \begin{cases} 1 & \text{if the orientation of } \alpha \text{ is consistent with that of } M, \\ -1 & \text{otherwise.} \end{cases} $$

We refer the reader to the full version [2] 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}_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{Dalloc}_d(P, \rho)$ under the assumptions of Theorem 10.
8:8 Delaunay-Like Triangulation of Submanifolds by Minimization

**Least ℓ₁-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 $\mathcal{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, \hfill (\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 $\mathcal{M}$ seems to be required as well for expressing the normalization constraint. What we call a *realistic* algorithm is an algorithm that takes only the point set $P$ as input. In the full version [2], 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 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 “approximates” $\mathcal{M}$ near $p_0$ and $\Sigma$ are simplices of $K$ “close” to $p_0$.

**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 $\mathcal{M}$ that satisfies the following safety conditions:

<footnote>$^2$ Generic in the sense that it is not in the projection on $\mathcal{M}$ of the convex hull of any $(d-1)$-simplex of $K$.</footnote>
1. $\Theta(P, \rho) \le \theta - 2 \arcsin\left(\frac{\rho+\delta}{R}\right)$.

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)^{-\frac{(d+2)(d-1)!}{4}} (\zeta^2 + \zeta \text{ separation}(P)) \Omega(\Delta_d)$.

Suppose that Delloc<sub>d</sub>(P, ρ) ⊆ K and that the d-simplices of K are ρ-small. Then Problem (⋆) has a unique solution which is γ<sub>Delloc<sub>d</sub>(P,ρ)</sub>. The support of that solution together with all its faces coincides with Delloc<sub>d</sub>(P, ρ) 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 ε-dense and δ-accurate seems realistic enough (perhaps after filtering outliers), the safety conditions seem less likely to be satisfied by natural data. In the full version [2], we show how to apply Moser Tardos Algorithm ([26] and [6, 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 Delloc$_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 Delloc$_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, Delloc$_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}$.
8:10 Delaunay-Like Triangulation of Submanifolds by Minimization

**Proof.** We write $\bar{\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_{D} f = \|\gamma_{\min}\|_{1,W_{\min}} = \|\gamma_{\min}\|_{1,W}, \quad (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}_{\bar{\alpha}}(x) = 1$ almost everywhere in $D$. We use this to write that:

$$ \|\gamma\|_{1,W_{\min}} \ge \sum_{\alpha} \gamma(\alpha) \int_{\bar{\alpha}} f = \sum_{\alpha} \gamma(\alpha) \int_{D} f \mathbf{1}_{\bar{\alpha}} = \int_{D} f \sum_{\alpha} \gamma(\alpha) \mathbf{1}_{\bar{\alpha}} = \int_{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_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}_{\bar{\alpha}}(x) = 1$ for almost all $x \in D$ and coefficients of $\gamma_{\min}$ are either 0 or 1, it follows that for almost all $x \in 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 $D$. Since $\sum_{\alpha} \gamma(\alpha) \mathbf{1}_{\bar{\alpha}}(x) = 1$ for almost all $x \in D$, the simplices in $\text{Supp } \gamma$ must also cover $D$ while using only a subset of simplices in $\text{Supp } \gamma_{\min}$. The only possibility is that $\gamma = \gamma_{\min}$, yielding a contradiction. ▲

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{Delloc}_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:

**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{Delloc}_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$

$$ \mathrm{Power}_{\alpha}(x) = \|x - z\|^2 - \sum_{a \in \alpha} \lambda_a \|a - z\|^2. $$

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

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

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

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

$$ \begin{aligned} (R(\alpha) + \zeta)^2 &< \|\pi_{\mathrm{aff}}(\alpha)(b) - Z(\alpha)\|^2, & \text{for all } b \in \beta \setminus \alpha, \\ R(\alpha)^2 &= \|\pi_{\mathrm{aff}}(\alpha)(b) - Z(\alpha)\|^2, & \text{for all } b \in \beta \cap \alpha. \end{aligned} $$

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_{\mathrm{aff}}(\alpha)(b) - Z(\alpha)\|^2. \quad (5) $$

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

$$ \mathrm{Power}_{\beta'}(y') = \|y' - Z(\alpha)\|^2 - \sum_{b \in \beta} \mu_b \|\pi_{\mathrm{aff}}(\alpha)(b) - Z(\alpha)\|^2. $$
8:12 Delaunay-Like Triangulation of Submanifolds by Minimization

Subtracting $||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.

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

**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$.

7 Proving the main result

Suppose that $K$ is a simplicial complex with vertex set $P$. Write $D = \text{Dalloc}_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: \mathcal{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: \mathcal{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} \left( [\pi_{\text{conv}\,\sigma \to M}]^{-1} \circ \pi_{M}(x) \right) \right), \quad (6) $$

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 (7) $$
► 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.

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

► 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 in [2] 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_b^\beta(\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_b^\beta(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_b^\beta(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)$ 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_b^\beta(y) dy,$$
8:14 Delaunay-Like Triangulation of Submanifolds by Minimization

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 (8)$$

Using a change of variable, it is not too difficult to show that $\Omega(\beta) = d! \operatorname{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! \operatorname{vol}(\beta)\Omega(\Delta_d)$ on the right side of (8), and the expression of $W(\beta) = \omega(\beta)$ given by Lemma 6 on the left side of (8), and recalling that $\beta$ is $\rho$-small, we find that condition (8) is implied by the following condition:

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

which we have assumed to hold.

**Proof of Theorem 13.** We start with pointing out that Problem $(\star)$ 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, $\operatorname{sign}_M(\alpha) = 1$ for all $\alpha \in K^{[d]}$. Let $D = \operatorname{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 \mathcal{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(\operatorname{conv} \alpha)}(x) = \sum_{\alpha \in D^{[d]}} \mathbf{1}_{\operatorname{conv} \alpha}(x) = 1$ for almost all $x \in \mathcal{D}$. Recalling that $W = \omega$ and therefore $\|\gamma\|_{1, W} = \operatorname{E}_{\operatorname{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}} & \operatorname{E}_{\operatorname{del}}(\gamma) \\ \text{subject to} & \sum_{\alpha \in K^{[d]}} \gamma(\alpha) \operatorname{sign}_M(\alpha) \mathbf{1}_{\varphi(\operatorname{conv} \alpha)}(x) = 1, \text{ for almost all } x \in \mathcal{D} \quad (\star\star) \end{array}$$

One can see that Problem $(\star\star)$ remains unchanged if one replaces the constraint with

$$\sum_{\alpha \in K^{[d]}} \gamma(\alpha) \operatorname{sign}_M(\alpha) \mathbf{1}_{\pi_M(\operatorname{conv} \alpha)}(m) = 1, \quad \text{for almost all } m \in M. \qquad (9)$$

Let $m_0$ be the arbitrary generic point of $M$, as in Problem $(\star)$. By Lemma 48 in [2], 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) \operatorname{sign}_M(\alpha) \mathbf{1}_{\pi_M(\operatorname{conv} \alpha)}(m_0) = 1. \end{array} \right.$$

We deduce that Problem $(\star)$ and Problem $(\star\star)$ are equivalent, and we get the result.

<figure><img src="image_8.png" /></figure>
References

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

2 D. Attali and A. Lieutier. Delaunay-like triangulation of smooth orientable submanifolds by $ℓ_1$-norm minimization, 2022. arXiv:2203.06008.

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

4 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.

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

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

7 Jean-Daniel Boissonnat, Ramsay Dyer, and Arijit Ghosh. The stability of delaunay triangulations. *International Journal of Computational Geometry & Applications*, 23(04n05):303–333, August 2013. doi:10.1142/s0218195913600078.

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

9 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.

10 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.

11 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.

12 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.

13 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.

14 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.

15 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.

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

17 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.

18 David Cohen-Steiner, André Lieutier, and Julien Vuillamy. Regular triangulations as lexicographic optimal chains. *Preprint HAL*, 2019. URL: https://hal.archives-ouvertes.fr/hal-02391285.
8:16 Delaunay-Like Triangulation of Submanifolds by Minimization

19 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.

20 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.

21 H. Edelsbrunner. *Geometry and topology for mesh generation*. Cambridge Univ Pr, 2001.

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

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

24 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*, 2019. arXiv:1903.06955.

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

26 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.

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

28 Oleg R Musin. Properties of the delaunay triangulation. In *Proceedings of the thirteenth annual symposium on Computational geometry*, pages 424–426, 1997.

29 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.

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

31 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.