David Cohen-Steiner

André Lieutier

Julien Vuillamy

Lexicographic optimal chains and manifold triangulations

Given a simplicial complex K, we consider the problem of finding a simplicial d-chain minimal in a given homology class. This is sometimes referred to as the Optimal Homologous Chain Problem (OHCP).

We consider here simplicial chains with coefficients in Z/2Z and the particular situation where, given a total order on d-simplices σ 1 < . . . < σ n , the weight of simplex i is 2 i . In this case, the comparison of chains is a lexicographic ordering. Similarly, we consider the problem of finding a minimal chain for a prescribed boundary. We show that, for both problems, the same matrix reduction algorithm used for the computation of homological persistence diagrams, applied to the filtration induced by the order on p-simplices, allows a O(n 3 ) worst case time complexity algorithm.

Second, we consider OHCP in the particular case where K is a (d + 1)-pseudo-manifold, for example when it triangulates a (d + 1)-sphere. In this case, there is a O(n log n) algorithm which can be seen, by duality, as a lexicographic minimum cut in the dual graph of K.

Third, we introduce a total order on n-simplices for which, when the points lie in the n-Euclidean space, the support of the lexicographic-minimal chain with the convex hull boundary as boundary constraint is precisely the n-dimensional Delaunay triangulation, or in a more general setting, the regular triangulation of a set of weighted points.

Fourth, we apply the lexicographic min-cut on the dual graph of the 3-dimensional Delaunay complex of a points cloud in R 3 . This gives in practice an efficient algorithm providing minimal solutions that, while inheriting the optimality for 2-dimensional Delaunay triangulations, reveals to create pertinent and convincing meshes for surface reconstruction, in particular in the case of noisy point clouds with non uniform densities and outliers, such as those produced by physical captures or Structure From Motion algorithms.

Last, it is known that a Čech complex with the right parameter over a point cloud sampling a compact connected C 2 manifold embedded in Euclidean space, if the sampling density is high enough with respect to the manifold reach, captures the homotopy type of the manifold and in particular its fundamental class. In the particular case of 2-manifolds, we show that, under good sampling conditions, the lexicographic minimal chain representative of the image of the fundamental class in the Čech complex provides a triangulation of the manifold.

Chapter 1 Introduction

Given a point cloud sampling a subset of Euclidean space, shape reconstruction consists in retrieving a shape that is both geometrically and topologically close to the sampled subset. It has been shown that, when the given point cloud satisfies specific sampling conditions related to some regularity measure on the subset, simplicial complexes such as alpha shape [START_REF] Edelsbrunner | Three-dimensional alpha shapes[END_REF], Čech or Rips complexes built on the point cloud share the homotopy type of the set [START_REF] Chazal | A sampling theory for compact sets in euclidean space[END_REF][START_REF] Attali | Vietoris-rips complexes also provide topologically correct reconstructions of sampled shapes[END_REF].

In this work, beyond creating a simplicial complex sharing the homotopy type, we aim to compute, when the object is a smooth manifold, a homeomorphic simplicial complex, in other words a manifold triangulation.

Motivation: minimal chain as manifold triangulation Indeed when the unknown shape is assumed to be a connected, compact d-manifold without boundary (respectively with a given, known boundary) it has a unique d-homology class (respectively relative d-homology class), called the fundamental class. In this case, the support of a minimal chain representative of this d-cycle in a simplicial complex that reproduces the homology of the shape (Čech, Rips, or alpha-shape) is a reasonable candidate for a manifold triangulation. We show indeed in Section 9 that this is the case for smooth 2-manifolds embedded in n-dimensional Euclidean space.

The L 1 norm on simplicial d-chains is defined by the weight assigned to each p-simplex and, when coefficients are taken in Z 2 = Z/2Z, the norm of the chain is just the sum of the weights of the simplices in the chain.

Delaunay weights and Delaunay lexicographic order

For this purpose, we use a family of weights, called here Delaunay Energy, motivated by the lifted paraboloid construction for Delaunay triangulation. Such weights have been introduced first in [START_REF] Chen | Optimal delaunay triangulations[END_REF] and then further used to optimize triangulations [START_REF] Alliez | Variational tetrahedral meshing[END_REF][START_REF] Chen | Efficient mesh optimization schemes based on optimal delaunay triangulations[END_REF]. In fact the same weights can be used to optimize directly in the affine space of homologous chains. Indeed, it has been observed ( [4] and Lemma 6.13) that given a point cloud in the Euclidean space R n , in the complete n-dimensional simplicial complex, i.e. the complex containing as n-simplices all the (n + 1)-tuples of points, the support of the n-chain minimal for the norm induced by these weights, with the cloud convex hull boundary as boundary constraint, coincides with Delaunay triangulations.

A particular choice of these weights makes the L 1 minimization of chains over coefficients in Z 2 equivalent to a minimization along a lexicographic order on chains induced by a given order on simplices. Indeed, if there is an order on simplices such that the weight of each simplex σ is greater than the sum of weights of all simplices smaller than σ (for example when simplex i has weight 2 i ), then comparing the respective L 1 norms of two chains is equivalent to comparing these two chains in lexicographic order (Section 8).

Minimal homology generators

The computation of minimal simplicial homology generators has been a wide subject of interest for its numerous applications related to shape analysis, computer graphics or computer-aided design. Coined in [START_REF] Tamal K Dey | Optimal homologous cycles, total unimodularity, and linear programming[END_REF], we recall the Optimal Homologous Chain Problem (OHCP): Problem 1.1 (OHCP). Given a p-chain A in a simplicial complex K and a set of weights given by a diagonal matrix W of appropriate dimension, find the 1-norm minimal chain Γ min homologous to A:

Γ min = min Γ,B ||W • Γ|| 1 such that Γ = A + ∂ d+1 B and Γ ∈ C p (K) , B ∈ C p+1 (K)
It has been shown that OHCP is NP-hard in the general case when using coefficients in Z 2 [START_REF] Chen | Hardness results for homology localization[END_REF][START_REF] Chambers | Minimum cuts and shortest homologous cycles[END_REF].

Contributions Sections 3, 4 and 5 consider a specialization of OHCP: the Lexicographic Optimal Homologous Chain Problem (Lex-OHCP). Using coefficients in Z 2 , minimality is meant according to a lexicographic order on chains induced by a total order on simplices. Formulated in the context of OHCP, this would require ordering the simplices using a total order and taking a weight matrix W with generic term W ii = 2 i , allowing the L 1 -norm minimization to be equivalent to a minimization along the lexicographic order. We first show how an algorithm based on the matrix reduction algorithm used for the computation of persistent homology [START_REF] Edelsbrunner | Computational topology: an introduction[END_REF] allows to solve this particular instance of OHCP in O(n 3 ) worst case complexity (Section 3). Using a very similar process, we then show that the problem of finding a minimal d-chain bounding a given (d -1)-cycle admits a similar algorithm with the same algorithmic complexity (Section 4). Finally, Section 5 considers Lex-OHCP in the case where the simplicial complex K is a strongly connected (d + 1)-pseudomanifold. By formulating it as a Lexicographic Minimum Cut (LMC) dual problem, the algorithm can be improved to a quasilinear complexity.

In Section 6, we introduce a total order on triangles for which the support of the minimal chain is precisely the regular triangulation, a generalization of Delaunay triangulation, in the case of a point cloud in euclidean space. Section 7 explores the particular case of 2-chains and state some properties of lexicographic minimal 2-chains immersed in n-Euclidean space.

Equipped with this Delaunay order, Section 8 provides an application of the developed Lex-OHCP algorithms to point cloud triangulation. We describe an open surface algorithm given an input boundary as well as a watertight surface reconstruction algorithm given an interior and exterior information based on a lexicographic minimum cut on the dual graph of a 3-dimensional Delaunay complex.

Section 9 studies C 2 2-manifolds embedded in n-dimensional Euclidean space and proves, under good sampling condition with respect to the manifold reach, that both the lexicographicminimal chain and a certain L 1 norm-minimal chain (Remark 9.2) realize a triangulation of the manifold (Theorem 9.1). The proof of Theorem 9.1 is given for completeness, as it supports our initial motivation of using a lexicographic order for manifold triangulation. However, the reader should considered it as work in progress, as current works are considering simpler arguments as well as an extension to higher dimensions, assuming a "protection" on the sampling set (Section 5.4 in [START_REF] Boissonnat | Geometric and topological inference[END_REF]). The proof of Theorem 9.1 makes use of [START_REF] Boissonnat | Local conditions for triangulating submanifolds of euclidean space[END_REF] for its final global argument, which relies heavily on the Whitney Lemma. Although we consider this argument to be the most natural, an alternative argument to the Whitney Lemma is given in Appendix F.

Related work

Several authors have studied algorithm complexities for the computation of L 1 -norm optimal cycles in homology classes [START_REF] Erickson | Greedy optimal homotopy and homology generators[END_REF][START_REF] Chen | Quantifying homology classes[END_REF][START_REF] Chambers | Minimum cuts and shortest homologous cycles[END_REF][START_REF] Chen | Measuring and computing natural generators for homology groups[END_REF][START_REF] Tamal K Dey | Approximating loops in a shortest homology basis from point data[END_REF][START_REF] Chen | Hardness results for homology localization[END_REF][START_REF] Tamal K Dey | Optimal homologous cycles, total unimodularity, and linear programming[END_REF][START_REF] Tamal K Dey | Computing minimal persistent cycles: Polynomial and hard cases[END_REF]. However, to the best of our knowledge, considering lexicographic-minimal chains in their homology classes is a new idea. When minimal cycles are of codimension 1 in a pseudo-manifold, the idea of considering the minimal cut problem on the dual graph has been previously studied. In particular, Chambers et al. [START_REF] Chambers | Minimum cuts and shortest homologous cycles[END_REF] have considered graph duality to derive complexity results for the computation of optimal homologous cycles on 2-manifolds. Chen et al. [START_REF] Chen | Hardness results for homology localization[END_REF] also use a reduction to a minimum cut problem on a dual graph to compute minimal non-null homologous cycles on n-complexes embedded in R n . Their polynomial algorithm (Theorem 5.2.3 in [START_REF] Chen | Hardness results for homology localization[END_REF]) for computing a homology class representative of minimal radius is reminiscent of our algorithm for computing lexicographic minimal representatives (Algorithm 4). In a recent work [START_REF] Tamal K Dey | Computing minimal persistent cycles: Polynomial and hard cases[END_REF], Dey et al. consider the dual graph of pseudo-manifolds in order to obtain polynomial time algorithms for computing minimal persistent cycles. Since they consider arbitrary weights, they obtain the O(n 2 ) complexity of best known minimum cut/maximum flow algorithms [START_REF] James B Orlin | Max flows in o (nm) time, or better[END_REF]. The lexicographic order introduced in our work can be derived from the idea of a variational formulation of the Delaunay triangulation, first introduced in [START_REF] Chen | Optimal delaunay triangulations[END_REF] and further studied in [START_REF] Alliez | Variational tetrahedral meshing[END_REF][START_REF] Chen | Efficient mesh optimization schemes based on optimal delaunay triangulations[END_REF].

Many authors have designed practical algorithms for the triangulation of point set in R 3 sampling an embedded 2-manifold. We review a few of them in section 8.1.

Chapter 2

Definitions

Simplicial complexes Consider an independent family A = (a 0 , ..., a d ) of (d + 1)-points of R N . We call a d-simplex σ spanned by A the set of all points x = d i=0 t i a i where ∀i ∈ [0, d], t i ≥ 0 and d i=0 t i = 1. Any simplex spanned by a subset of A is called a face of σ. A simplicial complex K is a collection of simplices such that:

1. Every face of a simplex of K is in K.

2. The intersection of two simplices of K is either empty or a face of both simplices. Simplicial chains. Let K be a simplicial complex of dimension at least d. The notion of chains can be defined with coefficients in any ring but we restrict here the definition to coefficients in the field Z 2 = Z/2Z. A d-chain A with coefficients in Z 2 is a formal sum of d-simplices :

A = i x i σ i , with x i ∈ Z 2 and σ i ∈ K (2.1)
Interpreting the coefficient x i ∈ Z 2 = {0, 1} in front of simplex σ i as indicating the existing of σ i in the chain A, we can view the d-chain A as a set of simplices : for a d-simplex σ and a d-chain A, we write that σ ∈ A if the coefficient for σ in A is 1. With this convention, the sum of two chains corresponds, when chains are seen as set of simplices, to their symmetric difference. We denote C d (K) the vector space over the field Z 2 of d-chains in the complex K.

Boundary operator. For a d-simplex σ = [a 0 , ...a d ], the boundary operator is defined as the operator: In what follows, a d-simplex σ can also be interpreted as the d-chain containing only the dsimplex σ.

∂ d : C d (K) → C d-1 (K) ∂ d σ = def.
Lexicographic order. We assume now a total order on the d-simplices of K, σ 1 < ... < σ n , where n = dim C d (K). From this order, we define a lexicographic total order on d-chains: Recall that wih coefficients in Z 2 one has

C 1 + C 2 = C 1 -C 2 .
Definition 2.1 (Lexicographic total order). For C 1 , C 2 ∈ C d (K):

C 1 lex C 2 ⇐⇒ def.        C 1 + C 2 = 0 or σ max = max {σ ∈ C 1 + C 2 } ∈ C 2
This total order naturally extends to a strict total order lex on C d (K):

C 1 lex C 2 ⇐⇒ def.        C 1 + C 2 = 0 and σ max = max {σ ∈ C 1 + C 2 } ∈ C 2
Chapter 3

Homologous lexicographic-minimal chains

In this section, we construct an algorithmic solution to the following problem:

Problem 3.1 (Homologous Lexicographic-Minimal Chain Problem). Given a simplicial complex K with a total order on the d-simplices and a d-chain A ∈ C d (K), find the unique chain Γ min defined by :

Γ min = min lex {Γ ∈ C d (K) | ∃B ∈ C d+1 (K) , Γ -A = ∂ d+1 B}
This problem is a particular instance of OHCP (Optimal Homologous Chain Problem) [START_REF] Tamal K Dey | Optimal homologous cycles, total unimodularity, and linear programming[END_REF] when the weight of i th d-simplex is 2 i . We first introduce the notions of reduction and total reduction to reformulate Problem 3.1. We then recall the matrix reduction algorithm for persistence homology presented in [START_REF] Edelsbrunner | Computational topology: an introduction[END_REF] (page 153), slightly modified for the purpose of this section.

Γ lex A and Γ -A = ∂ d+1 B

If this property cannot be verified, the d-chain A is said irreducible.

If A is reducible, we call total reduction of A the unique irreducible reduction of A. If A is irreducible, A is said its own total reduction. Problem 3.1 can be reformulated as finding the total reduction of A. With m = dim C d (K) and n = dim C d+1 (K), we now consider the m-by-n boundary matrix ∂ d+1 with entries in Z 2 . We enforce that rows of the matrix are ordered according to the strict total order on d-simplices: σ 1 < σ 2 < • • • < σ m , where the d-simplex σ i is the basis element corresponding to the i th row of the boundary matrix. The order of columns, corresponding to an order on (d + 1)-simplices, is not relevant for this section and can be chosen arbitrarily. The index of the lowest non-zero coefficient of a column R j of matrix R is denoted by low(j). This index is not defined for a column whose coefficients are all zero.

Algorithm 1 is a slightly modified version of the boundary reduction algorithm presented in [START_REF] Edelsbrunner | Computational topology: an introduction[END_REF]. Indeed, for our purpose, we do not need the whole square boundary matrix ∂ : j C j (K) → j C j (K) storing all the simplices of all dimensions and we apply the algorithm to the sub-matrix ∂ d+1 : C d+1 (K) → C d (K).

One checks easily that Algorithm 1 has O(mn 2 ) time complexity. We allow ourselves to consider each column R j of matrix R, formally an element of Z m 2 , as the corresponding d-chain in the basis (σ 1 , . . . , σ m ).

Algorithm 1: Reduction algorithm for the ∂ d+1 matrix R = ∂ d+1 for j ← 1 to n do while R j = 0 and ∃j 0 < j with low(j 0 ) = low(j) do R j ← R j + R j 0 end end

We now introduce a few lemmas useful for deriving an algorithm solving Problem 3.1. Lemma 3.2. After matrix reduction, a non-zero column R j = 0 can be described as:

R j = σ low(j) + Γ,
where Γ is a reduction for σ low(j) .

Proof. As all matrix operations performed on R by the reduction algorithm are linear, each non-zero column R j of R is in the image of ∂ d+1 . Therefore, there exist a (d + 1)-chain B such that :

R j = σ low(j) + Γ = ∂ d+1 B which, in Z 2 , is equivalent to Γ -σ low(j) = ∂ d+1 B
By definition of the low of a column, we have immediately:

Γ lex σ low(j)
We have thus shown that for each non-zero column, the largest simplex is reducible and the other d-simplices of the column are a reduction for it.

Lemma 3.3. After the matrix reduction algorithm, there is a one-to-one correspondence between the reducible d-simplices and non-zero columns of R:

σ i ∈ C d (K) is reducible ⇐⇒ ∃j ∈ [1, n], R j = 0 and low(j) = i
Proof. Lemma 3.2 shows immediately that the simplex corresponding to the lowest index of a non-zero column is reducible. Suppose now that a d-simplex σ is reducible and let Γ be a reduction of it:

σ + Γ = ∂B and Γ lex σ Algorithm 1 realizes the matrix factorization R = ∂ d+1 • V , where matrix V is invertible [START_REF] Edelsbrunner | Computational topology: an introduction[END_REF].

It follows that Im R = Im ∂ d+1 . Therefore the non-zero columns of R span Im ∂ d+1 and since σ + Γ = ∂B ∈ Im ∂ d+1 , there is a family (R j ) j∈J = (σ low(j) , Γ j ) j∈J of columns of R such that :

σ + Γ = j∈J σ low(j) + Γ j
Every σ low(j) represents the largest simplex of a column, and Γ j a reduction chain for σ low(j) .

As observed in section VII.1 of [START_REF] Edelsbrunner | Computational topology: an introduction[END_REF], one can check that the low indexes in R are unique after the reduction algorithm. Therefore, there is a j max ∈ J such that: ∀j ∈ J \ {j max }, low(j) < low(j max )

σ jmax = max{σ ∈ j∈J σ low(j) + Γ j } = max σ ∈ σ + Γ = σ
We have shown that for the reducible simplex σ, there is a non-zero column R jmax with σ = σ low(jmax) as its largest simplex.

Lemma 3.4. A d-chain A is reducible if and only if at least one of its d-simplices is reducible.

Proof. If there is a reducible d-simplex σ ∈ A, A is reducible by the d-chain A = A-σ+Red(σ), where Red(σ) is a reduction for σ.

We suppose A to be reducible. Let Γ lex A be a reduction for A and B the (d + 1)-chain such that Γ -A = ∂B. We denote σ max = max {σ ∈ A -Γ}. We show that σ max is homologous to

Γ -A + σ max : Γ -A = ∂B =⇒ (Γ -A + σ max ) -σ max = ∂B
The chain Γ -A + σ max only contains simplices smaller than σ max , by definition of the lexicographic order (Definition 2.1). We have thus shown that if A is reducible, it contains at least one simplex that is reducible.

Combining the three previous lemma give the intuition on how to construct the total reduction solving Problem 3.1: Lemma 3.4 allows to consider each simplex individually, Lemma 3.3 characterizes a reducible nature of a simplex using the reduced boundary matrix and Lemma 3.3 describes a column of the reduction boundary matrix as a simplex and its reduction. We now present Algorithm 2, referred to as the total reduction algorithm. For a d-chain Γ, Γ[i] ∈ Z 2 denotes the coefficient of the i th simplex in the chain Γ. Proof. In Algorithm 2, we denote by Γ i-1 the value of variable Γ after iteration i. Since iteration counter i is decreasing from m to 1, the input and output of the algorithm are respectively Γ m and Γ 0 . At each iteration, Γ i-1 are either equal to Γ i or Γ i + R j . Since R j ∈ Im ∂ d+1 , Γ i-1 is in both cases homologous to Γ i . Therefore, Γ 0 is homologous to Γ m . We are left to show that Γ 0 is irreducible. From Lemma 3.4, it is enough to check that it does not contain any reducible simplex. Let σ i be a reducible simplex and let us show that σ i / ∈ Γ 0 . Two possibilities may occur:

-if σ i ∈ Γ i , then Γ i-1 = Γ i + R j . Since low(j) = i, we have σ i ∈ R j and therefore σ i / ∈ Γ i-1 . -if σ i / ∈ Γ i , then Γ i-1 = Γ i and again σ i / ∈ Γ i-1 .
Furthermore, from iterations i -1 to 1, the added columns R j contain only simplices smaller than σ i and therefore

σ i / ∈ Γ i-1 ⇒ σ i / ∈ Γ 0 .
Observe that using an auxiliary array allows to compute the correspondence low(j) → i in time O [START_REF] Alliez | Variational tetrahedral meshing[END_REF]. The column addition nested inside the loop lead to a O(m 2 ) time complexity for Algorithm 2.

It follows that Problem 3.1 can be solved in O(mn 2 ) time complexity, by applying successively algorithms 1 and 2, i.e. O(N 3 ) if N is the size of the simplicial complex.

The theoretical complexity required to solve Problem 3.1 might seem prohibitive. Recall, however, that we are dealing with a specialization of the OHCP problem that has been shown to be NP-Hard in general [START_REF] Tamal K Dey | Optimal homologous cycles, total unimodularity, and linear programming[END_REF].

Chapter 4

Lexicographic-minimal chains under imposed boundary

This section will construct the algorithmic solution to the two following problems: Problem 4.1. Given a simplicial complex K with a total order on the d-simplices and a d-chain

Γ 0 ∈ C d (K), find : Γ min = min lex {Γ ∈ C d (K) | ∂ d Γ = ∂ d Γ 0 } Problem 4.2.
Given a simplicial complex K with a total order on the d-simplices and a (d-1)cycle A, find out if A is a boundary, i.e. if:

B A = def. {Γ ∈ C d (K) | ∂ d Γ = A} = ∅
If it is the case, find the minimal d-chain Γ bounded by A:

Γ min = min lex B A Problem 4.
-chain Γ min such that ∂ d Γ min = ∂ d Γ 0 = A.
This section is still strongly linked to the matrix reduction algorithm introduced in Section 3. Note that, unlike previous section that used the ∂ d+1 boundary operator, we are now considering ∂ d , meaning the given total order on d-simplices applies to the greater dimension of the matrix. An arbitrary order can be taken for the (d -1)-simplices to build the matrix reduction of ∂ d . Indeed, as indicated in [START_REF] Edelsbrunner | Computational topology: an introduction[END_REF], the performed reduction can be written in matrix notation as R = ∂ d • V and the minimization steps in this section will be performed on the matrix V , whose rows do follow the given simplicial ordering.

The number of zero columns of R is the dimension of Z d = Ker ∂ d [START_REF] Edelsbrunner | Computational topology: an introduction[END_REF]. Let's denote n Z = dim(Z d ). By selecting all columns in V corresponding to zero columns in R, we obtain the matrix Z, whose columns Z 1 , . . . , Z n Z form a basis of Z d . We first show a useful property on the matrix Z.

Lemma 4.1. Indexes { low(Z i ) } i∈[1,n Z ] are unique: i = j ⇒ low(Z i ) = low(Z j ) and if A ∈ Ker ∂ d \ {0}
, there exists a unique column Z max of Z with:

low(Z max ) = low(A)
Proof. In the reduction algorithm, the initial matrix V is the identity: the low indexes are therefore unique. During iterations of the algorithm, the matrix V is right-multiplied by an column-adding elementary matrix L j 0 ,j , adding column j 0 to j with j 0 < j.

L j 0 ,j = j                     1 1 1 j 0 . . . 1 . . . 1
Therefore, the indexes {low(V i ), V i ∈ V } stay on the diagonal during the reduction algorithm: low(V i ) = i. They are therefore unique. The restriction of V to Z does not change this property.

If A ∈ Ker ∂ d \ {0}, A can be written as a non-zero linear combination of non-zero columns (Z i ) i∈I of Z. As the lows of (Z i ) i∈I are unique, there is a unique column Z imax such that:

low(A) = low(Z imax ) = max i∈I low(Z i )
We apply a similar total reduction algorithm as previously introduced in Section 3 but using the matrix Z. In the following algorithm, m = dim C d (K). Proof. The proof is similar to the one of Lemma ??.

In Algorithm 3, we denote by Γ i-1 the value of variable Γ after iteration i. Since iteration counter i is decreasing from m to 1 the input and output of the algorithm are respectively is Γ m and Γ 0 . Since V Ker j ∈ Ker ∂ d , at each iteration ∂Γ i-1 = ∂Γ i therefore ∂Γ 0 = ∂Γ m . We are left to show the algorithm's result is the minimal solution.

Suppose there is Γ such that ∂ d Γ = ∂Γ and Γ lex Γ 0 . Let's consider the difference Γ 0 -Γ , and its largest element index low(Γ 0 -Γ ) = i, with σ i ∈ Γ 0 and σ i / ∈ Γ by definition 2.1 of the lexicographic order. As Γ 0 -Γ ∈ Ker ∂ d , there has to be a column V Ker j in V Ker where low V Ker j = i, from Lemma 4.1. Two possibilities may occur at iteration i:

-if σ i ∈ Γ i , then Γ i-1 = Γ i + V Ker j . Since i = low(j), we have σ i ∈ V Ker j and therefore σ i / ∈ Γ i-1 . -if σ i / ∈ Γ i , then Γ i-1 = Γ i and again σ i / ∈ Γ i-1 .
However, from iterations i -1 to 1, the added columns V Ker j contains only simplices with indices smaller than i and therefore we obtain

σ i / ∈ Γ i-1 ⇒ σ i / ∈ Γ 0 , a contradiction to the definition of σ i as largest element of Γ -Γ 0 .
As previously mentioned, solving Problem 4.2 requires deciding if the set B A is empty and, in case it is not empty, finding an element of the set B A . Algorithm 3 can then be used to minimize this element under imposed boundary.

In the following algorithm, m = dim C d-1 (K) and n = dim C d (K).

Algorithm 4: Finding a representative

Inputs : A (d -1)-chain A, a boundary matrix R reduced by V Γ 0 ← ∅ A 0 ← A for i ← m to 1 do if A 0 [i] = 0 then if ∃j ∈ [1, n] with low(j) = i in R then A 0 ← A 0 + R j Γ 0 ← Γ 0 + V j else
The set B A is empty. end end end Proposition 4.3. Algorithm 4 decides if the set B A is non-empty, and in that case, finds a representative Γ 0 such that ∂Γ 0 = A in O(m 2 ) time complexity.

Proof. We start by two trivial observations following from the definition of a reduction. First, A is a boundary if and only if its total reduction is the null chain. Second, if a non-null chain is a boundary, then its greatest simplex is reducible. If, at iteration i, A 0 [i] = 0, then σ i is the greatest simplex in A 0 . In the case R has no column R j such that low(j) = i, σ i is not reducible by Lemma 3.3 and therefore A 0 is not a boundary. Since A and A 0 differ by a boundary (added columns of R), A is not a boundary either. This means the set B A is empty. The main difference with the previous chain reduction is we keep track of the column operations in Γ 0 . If the total reduction of A is null, we have found a linear combination (R j ) j∈J such that A = j∈J R j . By computing Γ 0 as the sum of the corresponding columns in V :

Γ 0 = j∈J V j We can verify, as R = ∂ d • V : ∂ d Γ 0 = ∂ d   j∈J V j   = j∈J R j = A Chapter 5

Efficient algorithm in codimension 1

In this section we focus on Problem 5.1, a specialization of Problem 3.1, namely when K is a subcomplex of a (d + 1)-pseudomanifold. For simplicity we remain in the context of simplicial complexes but this section could be adapted to the more general context of CW complexes: roughly speaking, we could replace d-simplices by d-dimensional topological disks.

Dual graph of a pseudomanifold

Recall that a d-dimensional simplicial complex is said pure if it is of dimension d and any simplex has at least one coface of dimension d.

Γ min = min lex {Γ ∈ C p (M) | ∃B ∈ C d+1 (M \ {τ 1 , τ 2 }) , Γ -∂τ 1 = ∂B} Definition 5.4 (Coboundary 1 operator ∂ 0 ).
Seeing a graph G as a 1-dimensional simplicial complex, we define the coboundary operator ∂ 0 : C 0 (G) → C 1 (G) as the linear operator defined by the transpose of the matrix of the boundary operator

∂ 1 : C 1 (G) → C 0 (G) in the canonical basis of simplices.
For a given graph G = (V, E), V and E respectively denote its vertex and edge sets. We easily see that:

Observation 5.5. For a set of vertices V 0 ⊂ V, ∂ 0 V 0 is exactly the set of edges in G that connect vertices in V 0 with vertices in V \ V 0 .
For a d-chain α ∈ C d (M) and a (d+1)-chain β ∈ C d+1 (M), α and β denote their respective dual 1-chain and dual 0-chain in G(M). With this convention, one has also:

Observation 5.6. Let M be a (d + 1)-pseudomanifold. If α ∈ C d (M) and β ∈ C d+1 (M) , then: α = ∂ 0 β ⇐⇒ α = ∂ d+1 β

Codimension 1 and Lexicographic Min Cut (LMC)

The order on d-simplices of a (d + 1)-pseudomanifold M naturally defines a corresponding order on the edges of the dual graph: τ 1 < τ 2 ⇐⇒ τ1 < τ2 . This order extends similarly to a lexicographic order lex on sets of edges (or, equivalently, 1-chains) in the graph.

In the following, we say a set of edges Γ disconnects τ1 and τ2 in the graph (V, E) if τ1 and τ2 are not in the same connected component of the graph (V, E \ Γ).

Given a graph with weighted edges and two vertices, the min-cut/max-flow problem [START_REF] Edmonds | Theoretical improvements in algorithmic efficiency for network flow problems[END_REF][START_REF] James B Orlin | Max flows in o (nm) time, or better[END_REF] typically consists in finding the minimum cut (i.e. set of edges) disconnecting the two vertices, where minimum is meant as minimal sum of weights of cut edges. We consider a similar problem where the minimum is meant in term of lexicographic order, or equivalently when weight of edge i is 2 i . Problem 5.2 (Lexicographic Min Cut (LMC)). Given a connected graph G = (V, E) with a total order on E and two vertices τ1 , τ2 ∈ V, find the set ΓLMC ⊂ E minimal for the lexicographic order lex , that disconnects τ1 and τ2 in G. Proof. Problem 5.1 can be equivalently formulated as:

Γ min = min lex {∂ d+1 (τ 1 + B) | B ∈ C d+1 (M \ {τ 1 , τ 2 })} (5.1)
Using Observation 5.6 we see that Γ min is the minimum in Equation (5.1) if and only if its dual 1-chain Γmin satisfies:

Γmin = min lex ∂ 0 (τ 1 + B) | B ⊂ V \ {τ 1 , τ2 } (5.2)
Denoting ΓLMC the minimum of Problem 5.2, we need to show that ΓLMC = Γmin . As ΓLMC disconnects τ1 and τ2 in (V, E), τ2 is not in the connected component of τ1 in (V, E \ ΓLMC ). We define B such that

{τ 1 } / ∈ B and {τ 1 } ∪ B is the connected component of τ1 in (V, E \ ΓLMC ). We have that B ⊂ V \ {τ 1 , τ2 }. Consider an edge e ∈ ∂ 0 (τ 1 + B). From Observation 5.5, e connects a vertex v a ∈ {τ 1 } ∪ B with a vertex v b / ∈ {τ 1 } ∪ B.
From the definition of B, ΓLMC disconnects v a and v b in G, which in turn implies e ∈ ΓLMC . We have therefore shown that ∂ 0 (τ 1 + B) ⊂ ΓLMC . Using Equation (5.2) we get:

Γmin lex ∂ 0 (τ 1 + B) lex ΓLMC (5.3)
Now we claim that if there is a B ⊂ V \ {τ 1 , τ2 } with Γ = ∂ 0 (τ 1 + B), then Γ disconnects τ1 and τ2 in (V, E). For that consider a path in G from τ1 to τ2 . Let v a be the last vertex of the path that belongs to {τ 1 } ∪ B and v b the next vertex on the path (which exists since the τ2 is not in {τ 1 } ∪ B). From Observation 5.5, we see that the edge (v a , v b ) must belong to Γ = ∂ 0 (τ 1 + B).

We have shown that any path in G connecting τ1 and τ2 has to contain an edge in Γ and the claim is proved.

In particular, the minimum Γmin disconnects τ1 and τ2 in (V, E). As ΓLMC denotes the minimum of Problem 5.2, ΓLMC lex Γmin which, together with (5.3) gives us ΓLMC = Γmin . We have therefore shown the minimum defined by equation (5.2) coincides with the minimum defined in Problem 5.2.

Lexicographic Min Cut in O(nα(n)) time complexity

In this section, we will study an algorithm solving Problem 5.2. As we will only consider the dual graph for this section, we leave behind the dual chain notation: vertices τ1 and τ2 are replaced by α 1 and α 2 , and the solution to the problem is simply noted Γ LMC .

The following lemma exposes a property about the solution that helps constructing it iteratively.

Lemma 5.8. Consider Γ LMC solution of Problem 5.2 for the graph G = (V, E) and α 1 , α 2 ∈ V.

Let e 0 be an edge in V × V such that e 0 < min{e ∈ E}. Then:

1. The solution for (V, E ∪ {e 0 }) is either Γ LMC or Γ LMC ∪ {e 0 }. 2. Γ LMC ∪ {e 0 } is solution for (V, E ∪ {e 0 }) if and only if α 1 and α 2 are connected in (V, E ∪ {e 0 } \ Γ LMC ).
Proof. Let's call Γ LMC the solution for (V, E ∪ {e 0 }). Since Γ LMC ∩ E disconnects α 1 , α 2 in (V, E), one has:

Γ LMC lex Γ LMC Since Γ LMC ∪ {e 0 } disconnects (V, E ∪ {e 0 }), we have: Γ LMC lex Γ LMC ∪ {e 0 } Therefore, Γ LMC lex Γ LMC lex Γ LMC ∪ {e 0 }.
As e 0 < min{e ∈ E}, there is no set in E ∪ {e 0 } strictly between Γ LMC and Γ LMC ∪ {e 0 } for the lexicographic order. It follows that Γ LMC is either equal to Γ LMC or Γ LMC ∪ {e 0 }. The choice for Γ LMC is therefore ruled by the property that it should disconnect α 1 and α 2 : if α 1 and α 2 are connected in (V, E ∪ {e 0 } \ Γ LMC ), Γ LMC does not disconnect (V, E ∪ {e 0 }) and Γ LMC ∪ {e 0 } has to be the solution for (V, E ∪ {e 0 }). On the other hand, if α 1 and

α 2 are not connected in (V, E ∪ {e 0 } \ Γ LMC ), then both Γ LMC and Γ LMC ∪ {e 0 } disconnects (V, E ∪ {e 0 }), but as Γ LMC < lex Γ LMC ∪ {e 0 }, Γ LMC ∪ {e 0 } is not the solution for (V, E ∪ {e 0 }).
Building an algorithm from Lemma 5.8 suggest a data structure able to check if vertices α 1 and α 2 are connected in the graph: the disjoint-set data structure, introduced for finding connected components [START_REF] Bernard | An improved equivalence algorithm[END_REF], does exactly that. In this structure, each set of elements has a different root value, called representative. Calling the operation MakeSet on an element creates a new set containing this element. The FindSet operation, given an element of a set, returns the representative of the set. For all elements of the same set, FindSet will of course return the same representative. Finally, the structure allows merging two sets, by using the UnionSet operation. After this operation, elements of both sets will have the same representative.

We now describe Algorithm 5. The algorithm supposes that the set of edges is sorted in decreasing order according to the lexicographic order.

Algorithm 5: Lexicographic Min Cut

Inputs : G = (V, E) and α 1 , α 2 ∈ V, with E = {e i , i = 1, n} sorted in decreasing order Output:

Γ LMC Γ LMC ← ∅ for v ∈ V do MakeSet(v) end for e ∈ E in decreasing order do e = (v 1 , v 2 ) ∈ V × V r 1 ← FindSet(v 1 ), r 2 ← FindSet(v 2 ) c 1 ← FindSet(α 1 ), c 2 ← FindSet(α 2 ) if {r 1 , r 2 } = {c 1 , c 2 } then Γ LMC ← Γ LMC ∪ e end else
UnionSet(r 1 , r 2 ) end end Proposition 5.9. Algorithm 5 computes the solution of Problem 5.2 for a given graph (V, E) and two vertices α 1 , α 2 ∈ V. Assuming the input set of edges E are sorted, the algorithm has O(nα(n)) time complexity, where n is the cardinal of E and α the inverse Ackermann function.

Proof. We denote by e i the i th edge along the decreasing order and Γ i LMC the value of the variable Γ LMC of the algorithm after iteration i. The algorithm works by incrementally adding edges in decreasing order and tracking the growing connected components of the set associated with α 1 and α 2 in (V, {e ∈ E, e ≥ e i } \ Γ i LMC ), for i = 1, . . . , n. At the beginning, no edges are inserted, and Γ 0 LMC = ∅ is indeed solution for (V, ∅). With Lemma 5.8, we are guaranteed at each iteration i to find the solution for (V, {e ∈ E, e ≥ e i } \ Γ i LMC ) by only adding to the solution the current edge e i if α 1 and α 2 are connected in {e ∈ E, e ≥ e i } \ Γ i LMC , which is done in the if-statement. If the edge is not added, we update the connectivity of the graph (V, {e ∈ E, e ≥ e i } \ Γ i LMC ) by merging the two sets represented by r 1 and r 2 . At each iteration, Γ i LMC is solution for (V, {e ∈ E, e ≥ e i }) and when all edges are processed, Γ n LMC is solution for (V, E).

The complexity of the MakeSet, FindSet and UnionSet operations have been shown to be respectively O(1), O(α(v)) and O(α(v)), where α(v) is the inverse Ackermann function on the cardinal of the vertex set [START_REF] Robert | Worst-case analysis of set union algorithms[END_REF]. Assuming sorted edges as input of the algorithm -which can be performed in O(n ln(n)), the algorithm runs in O(nα(n)) time complexity.

Chapter 6

Regular triangulations as lexicographic minimal chains

Conventions and notations

We recall here some conventions in order to make this section more self contained.

A k-simplex σ being a set of k + 1 vertices in ambient space R n , we allow ourself to use set theoretic operators on simplices. For example τ ⊂ σ means that τ is a face of σ and σ 1 ∪ σ 2 is the join of σ 1 and σ 2 . |σ| denote the underlying space of the simplex σ, i.e. the convex hull of its vertices, which thanks to our generic condition are affinely independent.

Homology coefficients are implicitly in Z 2 = Z/2Z, i.e. the integer numbers modulo 2 so that -1 = 1 and the vector space of k-chains over K is denoted

C k (K) in place of C k (K, Z 2 ).
In this context we can allow ourself to see chains as sets of simplices. For example if Γ ∈ C k (K) and σ is a k-simplex in K, we allow ourself to write indifferently σ ∈ Γ or Γ(σ) = 1. Similarly, if Γ 1 , Γ 2 ∈ C k (K), we allow ourself to use indifferently vector or set theoretic operators:

Γ 1 + Γ 2 = Γ 1 -Γ 2 = (Γ 1 ∪ Γ 2 ) \ (Γ 1 ∩ Γ 2 ).
If Γ is a chain in C k (K), we denote by |Γ| the support of Γ which is the sub-complex of K made of all k-simplices in Γ together with all their faces.

We recall the definition of a lexicographic order on k-chains with coefficients in Z 2 induced by a total order on k-simplices: Definition 6.1 (Lexicographic Order on chains). Assume there is a total order ≤ on the set of k-simplices of K, defining the max on sets of k-simplices.

For Γ 1 , Γ 2 ∈ C k (K): Γ 1 lex Γ 2 ⇐⇒ def.        Γ 1 + Γ 2 = 0 or max {σ ∈ Γ 1 + Γ 2 } ∈ Γ 2

Main result of the section

We consider both cases of a set P = {(P 1 , µ 1 ), . . . , (P N , µ N )} ⊂ R n × R of weighted points as well as a the case of a set P = {P 1 , . . . , P N } ⊂ R n of points, the later case being equivalent to a particular configuration of the first case for which the weights are zero: ∀i, µ i = 0. In both cases, CH(P) denote the convex hull of the set of points in R n , that is:

CH(P) = CH ({P 1 , . . . , P N })
The n-dimensional full complex over P, denoted K P , is the simplicial complex made of all possible simplices up to dimension n with vertices in P.

The aim of this section is to prove the following: Theorem 6.2. Let P = {(P 1 , µ 1 ), . . . , (P N , µ N )} ⊂ R n × R, with N ≥ n + 1 be in general position and let K P be the n-dimensional full complex over P. Denote by β P ∈ C n-1 (K P ) the (n -1)-chain made of simplices belonging to the boundary of CH(P). If:

Γ min = min lex {Γ ∈ C n (K P ), ∂Γ = β P }
then the simplicial complex |Γ min | support of Γ min is the regular triangulation of P.

When all the weights are zero: ∀i, µ i = 0 this gives: Corollary 6.3. Let P = {P 1 , . . . , P N } ⊂ R n with N ≥ n + 1 be in general position and let K P be the n-dimensional full complex over P.

Denote by β P ∈ C n-1 (K P ) the (n -1)-chain made of simplices belonging to the boundary of CH(P). Then if:

Γ min = min lex {Γ ∈ C n (K P ), ∂Γ = β P }
then the simplicial complex |Γ min | support of Γ min is the Delaunay triangulation of P.

The relation lex among n-chains is the lexicographic order defined according to Definition 6.1 where the total order on n-simplices is given at the end of section 6.4. The general position assumption is a generic condition formalized in condition 6.2 for the general formulation of Theorem 6.2. The definition of regular triangulations is recalled in Definition 6.11 of section 6.5.

Obviously, replacing in Theorem 6.2 the full complex K P by a complex containing the regular triangulation (or Delaunay in case of zero weights) would give again this triangulation as a minimum.

One option would have been to explain the proof ideas in the particular case of Delaunay triangulations (i.e. zero weights). However, the framework of regular triangulations is required anyway in the proof construction so that eventually the general framework reveals to be more natural for the proof exposition.

Outline of the proof. The global argument of the proof is given in section 6.10. Theorem 6.2 is proven for points with non positive weights which, thanks to observation 6.8, is enough to have it true for any weights. The proof starts with Proposition 6.13, a consequence of the well known equivalence between regular triangulations and convex hulls of lifted points.

Statement of Proposition 6.13 is the same as Theorem 6.2 but for the order along which the minimum is taken. In Proposition 6.13 the minimization is meant for the order p induced by the weighted L 1 norm • (p) on chains. All the proof consists then in showing that, while the two orders differ, they share the same minimum under the theorem constraints. The bounding weight of a simplex is a generalization, for weighted points, of the radius of the smallest ball enclosing the simplex. It the dominant quantity in the definition of the order on simplices which induces the lexicographic order lex on chains.

The proof then proceeds in 3 main steps: 1) For p large enough, the weight w p (σ) p of any single simplex σ in the • (p) norm is larger than the sum of all weights of all simplices with smaller bounding weight (bounding radius) than σ (Lemma 6.15). This fact allows to focus on the link of a single bounding weight, the largest bounding weight for which some simplices in the minimum of lex and p would differ (Lemma 6.15 and section 6.10).

2) Then we introduce an extension of the classical lifted paraboloid construction that allows to see the simplicial structure of the link of a simplex τ in the Delaunay triangulation as a convex cone. In this representation, we study the subcomplex of this link corresponding to cofaces of τ with same bounding radius as τ . We show that this subcomplex is isomorphic to the set of bounded and visible faces of a convex polytope. It is therefore a simplicial ball (Lemma 6.23 and section 6.8).

3) Then, by induction on the dimension of convex cones and convex polytopes, one show that this bounded subcomplex of the boundary of a convex polytope visible from the origin can be expressed as a the minimum under boundary constraint ( Lemma 6.27 and section 6.9) for another lexicographic order.

This lexicographic order corresponds, on a the subset of the link of τ corresponding to simplices with same bounding weight, to the lexicographic order of corresponding full dimensional simplices in the star of τ (Lemmas 6.28 and 6.29).

Weighted points and weighted distances

We briefly recall the notions associated to weighted points and distances required to introduce the generalization of Delaunay triangulations, called regular triangulation or sometimes weighted Delaunay. We follow the terminology, notations and conventions of section 4.4 in [START_REF] Boissonnat | Geometric and topological inference[END_REF].

We consider a set of weighted points P = {(P 1 , µ 1 ), . . . , (P N , µ N )} ⊂ R n ×R with N ≥ n+1. A weighted point (P, 0) is seen as the usual point P ∈ R n , while, when µ > 0 it is associated to the sphere centered at P with radius r = √ µ.

When µ < 0 weighted points may be seen as spheres with imaginary radius r = √ µ. We allow ourself to speak about spheres in this later case but we prefer in general to consider weights over radius since we rely on the natural order on real number valued (possibly negative) weights µ: translating this order on complex numbers r = √ µ is not natural when µ < 0.

Weighted distance between weighted points Definition 6.4 (Section 4.4 in [START_REF] Boissonnat | Geometric and topological inference[END_REF]). Given two weighted points (P 1 , µ 1 ), (P 2 , µ 2 ) ∈ R n × R their weighted distance is defined as: D ((P 1 , µ 1 ), (P 2 , µ 2 )) = def.

(P

1 -P 2 ) 2 -µ 1 -µ 2
we say that (P

µ C (σ) = def. min {µ ∈ R, ∃P ∈ R n , ∀(P i , µ i ) ∈ σ, D ((P, µ), (P i , µ i )) = 0} (6.1) µ B (σ) = def.
min {µ ∈ R, ∃P ∈ R n , ∀(P i , µ i ) ∈ σ, D ((P, µ), (P i , µ i )) ≤ 0} (6.2) P C (σ) and P B (σ) are respectively the unique points P that realize the minimum in Equations (6.1) and (6.2). The weights µ C (σ) and µ B (σ) are called respectively "circumweight" and bounding weight of σ.

The set {(P, µ), ∀(P i , µ i ) ∈ σ, D ((P, µ), (P i , µ i )) = 0}, on which the first arg min is taken, is not empty, thanks to the generic condition 6.1.

When k = n there is in fact (generically) a single weighted point (P C , µ C ) such that ∀(P i , µ i ) ∈ σ, D ((P, µ), (P i , µ i )) = 0. If k < n the arg min is required to get what would be the minimal circumsphere in the case of zero weights. Observation 6.6. Observe that if the weight of all points in P are assumed non positive, then one has always µ C (τ ) ≥ 0 and µ B (τ ) ≥ 0 and if moreover τ has positive dimension, then µ C (τ ) > 0 and µ B (τ ) > 0.

In the particular case with zero weights, corresponding to Delaunay triangulations, then:

µ C (τ ) = R C (τ ) 2 and µ B (τ ) = R B (τ ) 2
where R C (τ ) is the circumradius of τ and R B (τ ) is the radius of the smallest enclosing ball SEB(τ ) of τ .

Observation 6.7. Let ψ λ : R n × R → R n × R, be the transformation that shifts the weight by λ: ψ λ (P, µ) = (P, µ + λ)

Let σ ∈ K P be a simplex, from definitions 6.5 and 6.4 we have:

P C (ψ λ (σ)) = P C (σ) and µ C (ψ λ (σ)) = µ C (σ) -λ P B (ψ λ (σ)) = P B (σ) and µ B (ψ λ (σ)) = µ B (σ) -λ
It follows that a global shift by a constant value λ results in an opposite shift on the weights of generalized circumcenters. It therefore preserves the relative order between simplices weights µ C and µ B :

µ C (σ 1 ) ≤ µ C (σ 2 ) ⇐⇒ µ C (ψ λ (σ 1 )) ≤ µ C (ψ λ (σ 2 ))
and the same relation holds for µ B . Since the order ≤ between simplices (6.9) defined in section 6.4 relies entirely on comparisons on µ C and µ B , this total order is preserved by a global weight translation.

It follows that: Observation 6.8. Both the order between simplices (see observation 6.7) and regular triangulations are invariant under a global translation ψ λ (τ ) of the weights. Therefore proving Theorem 6.2 for non positive weights is enough to extend it to any weights.

We will need the following easy lemma: Lemma 6.9. For any k-simplex σ ∈ K P , one has:

P B (σ) ∈ |σ| (6.3)
Proof. If σ = {(P 0 , µ 0 ), . . . , (P k , µ k )}, |σ| is the convex hull of {P 0 , . . . , P k }.

If P / ∈ |σ| the projection of P on |σ| decreases the weighted distance from P to all the vertices of σ, which shows that (P, µ) cannot realize the arg min in (6.2).

Second generic condition.

Condition 6.2. We say that P = {(P 1 , µ 1 ), . . . , Proof. In (6.2), denote by τ ⊂ σ the set of vertex (P i , µ i ) ∈ σ for which: D ((P, µ),

(P N , µ N )} ⊂ R n × R
(P i , µ i )) = 0
This set cannot be empty as, if all inequalities in (6.2) where strict, a strictly smaller value of µ would still match the inequality, which would contradict with the arg min in (6.2). One has then τ = ∅ and:

∀(P i , µ i ) ∈ τ, D ((P, µ), (P i , µ i )) = 0 (6.5)
and of course:

∀(P i , µ i ) ∈ τ, D ((P, µ), (P i , µ i )) ≤ 0 (6.6)
No other (P, µ) with a smaller value of µ can satisfies (6.5) nor (6.6) as it would again similarly contradict the arg min in (6.2). It follows that:

(P B , µ B )(σ) = (P B , µ B )(τ ) = (P C , µ C )(τ )

Regular triangulation order on simplices

Notation For a n-simplex σ one defines Θ k (σ), the (k + dim(Θ(σ)))-dimensional face of σ defined by (6.7) and (6.8) below: Θ 0 (σ) = Θ(σ) (

where Θ(σ) is defined in Lemma 6.10 and depicted on figure 6.1 in the case of zero weights.

For k > 0, Θ k (σ) is the (dim(Θ k-1 (σ)) + 1)-dimensional coface of Θ k-1 (σ) with minimal circumradius: Θ k (σ) = arg min Θ k-1 (σ)⊂τ ⊂σ dim(τ )=dim(Θ k-1 (σ))+1
µ C (τ ) (6.8) and: Order on n-simplices. Observethat, thanks to generic condition 6.2 and Lemma 6.10, when P is in general position, one has, for two n-simplices σ 1 , σ 2 :

µ k (σ) = µ C (Θ k (σ)) In particular µ 0 (σ) = µ B (σ) and if k = dim(σ) -dim(Θ(σ)) then µ k (σ) = µ C (σ).
µ B (σ 1 ) = µ B (σ 2 ) ⇒ Θ(σ 1 ) = Θ(σ 2 )
and therefore, if µ B (σ 1 ) = µ B (σ 2 ), µ k (σ 1 ) and µ k (σ 2 ) are defined for the same range of values of k.

We define the following relations (recall that µ 0 (σ) = µ B (σ)):

σ 1 < σ 2 ⇐⇒ def.              µ 0 (σ 1 ) < µ 0 (σ 2 ) or ∃k ≥ 1, µ k (σ 1 ) > µ k (σ 2 )
and ∀j, 0 ≤ j < k, µ j (σ 1 ) = µ j (σ 2 ) (6.9) and:

σ 1 ≤ σ 2 ⇐⇒ def.        σ 1 = σ 2 or σ 1 < σ 2 (6.10)
For example, when n = 2 and the weights are zero, this order on triangles consists in first comparing the radii of the smallest circles enclosing the triangles T i , i = 1, 2, whose squares are R B (T i ) 2 = µ B (T i ) = µ 0 (T i ) (Observation 6.6). This is generically enough for acute triangles, but not for obtuse triangles that could generically share the longest edge. In this case the tie is broken by comparing in reverse order the circumradii, whose squares are R

C (T i ) 2 = µ C (T i ) = µ 1 (T i ).
As shown in section 7, this order is equivalent to the order ≤ ∞ (Lemma 7.6).

Lexicographic order on n-chains. One can check that when P is in general position, the relation ≤ among n-simplices is antisymmetric and a total order. Following definition 6.1 the order ≤ on simplices induces a lexicographic order lex on the n-chains of K P . From now on we assume that P is in general position i.e. it satisfies condition 6.2.

Regular triangulations of weighted points

We recall now the definition of a regular triangulation over a set of weighted points using a generalization of the empty sphere property of Delaunay triangulations. Definition 6.11 (Lemma 4.5 in [START_REF] Boissonnat | Geometric and topological inference[END_REF]). A regular triangulation T of the set of weighted points

P = {(P 1 , µ 1 ), . . . , (P N , µ N )} ⊂ R n × R, N ≥ n + 1, is a triangulation of the convex hull of {P 1 , . . . , P N } taking its vertices in {P 1 , . . . , P N } such that for any simplex σ ∈ T , if (P C (σ), µ C (σ))
is the generalized circumsphere of σ, then:

(P i , µ i ) ∈ P \ σ ⇒ D ((P C (σ), µ C (σ)), (P i , µ i )) > 0
Under generic condition 6.2 there exists a unique regular triangulation of P = {(P 1 , µ 1 ), . . . , (P N , µ N )}. However, with variable weights, some points with low weights in P may not be vertices of the triangulation.

Lift of weighted points and p-norms

Lift of weighted points. Given a weighted point (P, µ) ∈ R n × R its lift with respect to an implicit origin O ∈ R n , denoted lift(P, µ), is a point in R n × R given as:

lift(P, µ) = def. ((P -O), (P -O) 2 -µ)
Similarly to Delaunay triangulations, it is a well known fact (and not difficult to check afterward) that simplices of the regular triangulation of P are in one-to-one correspondence with the lower convex hull of lift(P): Proposition 6.12. A simplex σ is in the regular triangulation of P if and only if lift(σ) is a simplex on the lower convex hull of lift(P).

The lifted paraboloid construction had led some authors to imagine a variational formulation for Delaunay triangulations introduced for the first time in [START_REF] Chen | Optimal delaunay triangulations[END_REF]. This idea has been exploited further in order to optimize triangulations in [START_REF] Chen | Efficient mesh optimization schemes based on optimal delaunay triangulations[END_REF][START_REF] Alliez | Variational tetrahedral meshing[END_REF]. We follow here the same idea but the variational formulation, while using the same criterion, is applied on the linear space of chains, which can be seen as a superset of the space of triangulations. This point of view allows to revisit Delaunay and regular triangulations in a linear programming setting, as for example in Proposition 6. [START_REF] Boissonnat | Manifold reconstruction using tangential delaunay complexes[END_REF].

We define a function on the convex hull of a k-simplex f σ : |σ| → R where σ = {(P 0 , µ 0 ), . . . , (P k , µ k )} as the difference between the linear interpolation of the height of the lifted vertices and the fonc-

tion x → (x -O) 2 .
More precisely, for a point x ∈ |σ| with barycentric coordinates λ i ≥ 0, i λ i = 1 we have x = i λ i P i and:

f σ : x → f σ (x) = def. i λ i ((P i -O) 2 -µ i ) -(x -O) 2 (6.11)
A short computation shows that the function f σ , expressed in terms of barycentric coordinates, is invariant by applying an isometry such as a translation or rotation or symmetry on σ. In particular f σ (x) does not depend on the origin O of the lift.

It follows from Proposition 6.12 that if σ x is a simplex in the regular triangulation of P such that x ∈ |σ x | and if σ is another simplex with its vertices in P with x ∈ |σ x | ∩ |σ | then:

f σx (x) ≤ f σ (x) (6.12)
In the particular case where all weights are non positive, that is ∀i, µ i ≤ 0, the convexity of x → x 2 says that the expression of f σ (x) in (6.11) is never negative and in this case (6.12) implies that defining the weight w p of a n-simplex σ as:

w p (σ) = def. f σ p = |σ| f σ (x) p dx 1 p (6.13)
allows to characterize the regular triangulation as the one induced by the chain Γ reg that, among all chains with boundary β P , minimizes:

Γ → Γ (p) = def. σ |Γ(σ)|w p (σ) p (6.14)
In this last equation, the notation

|Γ(σ)| instead of Γ(σ) is there since Γ(σ) ∈ Z 2 and the sum is in R: Γ(σ) → |Γ(σ)| convert coefficients in Z 2 into binary real numbers in {0, 1}.
The parenthesis around the parameter p indexing the norm in Γ (p) are there to avoid the confusion with a L p norm (as the one appearing in (6.13)), which is meaningless for coefficients in Z 2 , but rather a weighted L 1 norm where the weights w p (σ) p are parametrized by p. Formally, we have the following Proposition 6.13, whose proof is given in appendix A. Proposition 6.13. Let P = {(P 1 , µ 1 ), . . . , (P N , µ N )} ⊂ R n × R, with N ≥ n + 1 be in general position with with non positive weights: ∀i, µ i ≤ 0, and let K P be the n-dimensional full complex over P.

Denote by β

P ∈ C n-1 (K P ) the (n -1)

-chain made of simplices belonging to the boundary of CH(P). Then for any

p ∈ [1, ∞), if: Γ reg = arg min Γ∈Cn(K P ) ∂Γ=β P Γ (p)
then the simplicial complex |Γ reg | support of Γ reg is the regular triangulation of P. Lemma 6.14. One has:

sup x∈|σ| f σ (x) = µ B (σ) (6.15)
Proof. Since the expression (6.11) does not depend on the origin O, let us choose this origin to be O = P B (σ). With barycentric coordinates based on the vertices P i , i = 0, k of σ, i.e. λ i ≥ 0,

i λ i = 1 such that x = i λ i P i , the expression of f σ is: f σ (x) = i λ i (P i -P B (σ)) 2 -µ i -(x -P B (σ)) 2 one has (P i -P B (σ)) 2 -µ i -µ B (σ) = D ((P B (σ), µ B (σ)), (P i , µ i )) ≤ 0 so that (P i -P B (σ)) 2 -µ i ≤ µ B (σ) and it follows that: ∀x, f σ (x) ≤ µ B (σ) -(x -P B (σ)) 2 (6.16)
We have from Lemma 6.9 that P B (σ) ∈ |Θ(σ)| ⊂ |σ| so that, in the expression of P B (σ) as a barycenter of vertices of σ, only coefficients λ i corresponding to vertices of Θ(σ) ⊂ σ are non zero:

P B (σ) = (P i ,µ i )∈Θ(σ) λ i P i
One has by definition of (P C , µ C ):

(P i , µ i ) ∈ Θ(σ) ⇒ (P i -P C (Θ(σ))) 2 -µ i = µ C (Θ(σ))
and since we know from Lemma 6.10 that:

(P B , µ B )(σ) = (P B , µ B )(Θ(σ)) = (P C , µ C )(Θ(σ))
one gets:

(P i , µ i ) ∈ Θ(σ) ⇒ (P i -P B (σ)) 2 -µ i = µ B (σ)
and:

f σ (P B (σ)) =   (P i ,µ i )∈Θ(σ) λ i ((P i -P B (σ)) 2 -µ i )   -0 2 = µ B (σ)
This with (6.16) ends the proof.

Since f σ is continuous, it follows from Lemma 6.14 that:

lim p→∞ w p (σ) = w ∞ (σ) = f σ ∞ = sup x∈|σ| f σ (x) = µ B (σ) (6.17)
We then have the following: Lemma 6.15. Let be P = {(P 1 , µ 1 ), . . . , (P N , µ N )} ⊂ R n × R, with N ≥ n + 1 in general position and with non positive weights: ∀i, µ i ≤ 0. Let K P be the corresponding n-dimensional full complex. For p large enough, the weight w p (σ) p of any n-simplex σ ∈ K P , is larger than the sum of alls n-simplices in K P with smaller "bounding weight" µ B . In other words, if

K [n] P is the set of n-simplices in K P : ∃p , ∀p ≥ p , ∀σ ∈ K [n] P , w p (σ) p > τ ∈K [n] P ,µ B (τ )<µ B (σ) w p (τ ) p
Proof. Consider the smallest ratio between two bounding of n-simplices in K P :

ι = inf σ 1 ,σ 2 ∈K [n] P µ B (σ 1 )<µ B (σ 2 ) µ B (σ 2 ) µ B (σ 1 )
From the finiteness of simplices, one has ι > 1 and since for a finite number of n-simplices σ ∈ K

[n] P we have from (6.17): lim

p→∞ w p (σ) = µ B (σ)
It follows that there is some p 0 large enough such that for any p > p 0 one has:

∀σ 1 , σ 2 ∈ K [n] P , µ B (σ 1 ) < µ B (σ 2 ) ⇒ µ B (σ 2 ) µ B (σ 1 ) > 1 + ι 2
Let N be total number of n-simplices in K P . Taking:

p = max p 0 , log N log 1+ι 2
realizes the statement of the lemma.

As explained in the proof of the main theorem of section 6.10, Lemma 6.15 allows us to focus on the link of a single simplex τ . However, before that, we need to introduce geometrical constructions that give an explicit representation of this link. These geometrical constructions and associated properties will take next two sections 6.7 and 6.8. Moreover Section 6.9 is required to establish Lemma 6.27 , a key ingredient of the proof of main Theorem.

Projection on the bisector of a simplex

In this section we establishes a condition for a simplex τ to belong to the regular triangulation, and when it is the case, we give a characterization of its link in the regular triangulation.

We denote by bis τ the (n -k)-dimensional affine space bisector of τ formally defined as:

bis τ = def. {x ∈ R n , ∀v 1 , v 2 ∈ τ, D ((x, 0), v 1 ) = D ((x, 0), v 2 )} (6.18)
In the particular case where dim(τ ) = 0, one has bis τ = R n . Let x → π bisτ (x) and x → d(x, bis τ ) = d(x, π bisτ (x)) denote respectively the orthogonal projection on and the minimal distance to bis τ . We define a projection π τ : P → bis τ × R as follows:

π τ (P, µ) = def.
π bisτ (P ), µ -d(P, bis τ ) 2 (6.19) Figure 6.2 illustrates π τ for ambient dimension 3 and dim(τ ) = 1.

Let

o τ = P C (τ ) ∈ bis τ denote the (generalized) circumcenter of τ . If (P i , µ i ) ∈ τ , then D ((o τ , µ C (τ )), (P i , µ i )) = 0. Since o τ = π bisτ (P i ) that gives (P i -o τ ) 2 -µ i -µ C (τ ) = d(P, bis τ ) 2 -µ i -µ C (τ ) = 0. It follows that if we denote µ(π τ (P i , µ i )) the weight of π τ (P i , µ i ) , one has µ(π τ (P i , µ i )) = µ i -d(P, bis τ ) 2 = -µ C (τ ).
We have shown therefore that π τ sends all vertices of τ to a single weighted point:

(P i , µ i ) ∈ τ ⇒ π τ (P i , µ i ) = (o τ , -µ C (τ )) (6.20)
We have then the following lemma: Lemma 6.16. Let P be in general position, τ ∈ K P a k-simplex and σ ∈ K P a coface of τ . Then σ is in the regular triangulation of P if and only if π τ (σ) is a coface of the vertex

{(o τ , -µ C (τ ))} = π τ (τ )
in the regular triangulation of π τ (P).

Proof of Lemma 6.16. Under generic condition, σ is in the regular triangulation of P if and only if there is a weighted point (P C (σ), µ C (σ)) such that:

∀(P i , µ i ) ∈ σ, D ((P C (σ), µ C (σ)), (P i , µ i )) = 0 (6.21) ∀(P i , µ i ) ∈ P \ σ, D ((P C (σ), µ C (σ)), (P i , µ i )) > 0 (6.22)
Observe that, since τ ⊂ σ, (6.21) implies:

∀(P i , µ i ) ∈ τ, D ((P C (σ), 0), (P i , µ i )) = µ C (σ)
This and the definition (6.18) of bisector show that P C (σ) must be on the bisector of τ :

P C (σ) ∈ bis τ (6.23)
We get, for (P i , µ i ) ∈ P: In the last two lines, the weighted distance is denoted D bisτ instead of D in order to stress that, thanks to (6.23) , it occurs on weighted point of bis τ × R rather than R n × R. It results that (6.21) and (6.22) are equivalent to:

D ((P C (σ), µ C (σ)), (P i , µ i )) = (P C (σ) -P i ) 2 -µ C (σ) -µ i = (π bisτ (P i ) -P C (σ)) 2 + d(P i , bis τ ) 2 -µ C (σ) -µ i = D bisτ (P C (σ), µ C (σ)), (π bisτ (P i ), µ i -d(P i , bis τ ) 2 ) = D bisτ ((P C (σ), µ C (σ)), π τ (P i , µ i )) (6.24)
∀(P i , µ i ) ∈ σ, D bisτ ((P C (σ), µ C (σ)), π τ (P i , µ i )) = 0 ∀(P i , µ i ) ∈ P \ σ, D bisτ ((P C (σ), µ C (σ)), π τ (P i , µ i )) > 0 which precisely means that π τ (σ) is a coface of the vertex π τ (τ ) = {(o τ , -µ C (τ ))} in the regular triangulation of π τ (P).
Looking at the definition 6.5 in the light of (6.24) in the proof of Lemma 6.16 we get that:

σ ⊃ τ ⇒ µ C (σ) = µ C (π τ (σ)) and P C (σ) = P C (π τ (σ)) (6.25)
An immediate consequence of Lemma 6.16 is:

Corollary 6.17. The projection π τ preserves the structure of the regular triangulation around τ , more precisely:

1. the simplex τ is in the regular triangulation of P if and only if the vertex π τ (τ ) is in the regular triangulation of π τ (P),

if τ is in the regular triangulation of P, the link of τ in the regular triangulation of

P is isomorphic to the link of vertex π τ (τ ) = {(o τ , -µ C (τ ))} in the regular triangulation of π τ (P).
Proof. The first item results from Lemma 6.16 if we consider the special case σ = τ while the second item result from the same lemma when considering σ as a proper coface of τ .

Polytope and shadow associated to a link in a regular triangulation

In this section we are interested in characterizing k-simplices τ ∈ K P such that, following Lemma 6.10, τ = Θ(σ) where σ is a n-simplex of the regular triangulation. In the case of Delaunay triangulation, one has always 1 ≤ k = dim(τ ). In the more general case of a regular triangulation a n-simplex can be "included" in the sphere associated to a single of its vertices v with τ = {v}, in which case k = 0. We know from Lemma 6.10 that in this case one has Θ(τ ) = τ . In case of Delaunay this means that the circumsphere and the smallest enclosing ball coincide for the simplex τ . In the general case it says that:

(P B , µ B )(τ ) = (P C , µ C )(τ ) (6.26)
So we restrict ourself in this section to k-simplices τ that satisfy (6.26) and we study again the link of τ in the regular triangulation of P or equivalently (Lemma 6.16) the link of the vertex π τ (τ ) = {(o τ , -µ C (τ ))} in the regular triangulation of π τ (P).

We know then from Proposition 6.12 that the link of τ in the regular triangulation is isomorphic to the link of lift(π τ (τ )) on the boundary of the lower convex hull of lift(π τ (P)). We consider the lift with the origin at o τ , in other words, the image of a vertex (P, µ) ∈ P is:

Φ τ (P, µ) = def. lift (π τ (P, µ)) = π bisτ (P ) -o τ , (π bisτ (P ) -o τ ) 2 -µ + d(P, bis τ ) 2
Observe that, from (6.20):

Φ τ (τ ) = {(0, µ C (τ )}
Call P τ the set of weighted points in (P i , µ i ) ∈ P such that τ ∪ (P i , µ i ) has same bounding weight than τ . In the case of the Delaunay triangulation, P τ corresponding to the set of points in P inside the bounding ball of τ . Formally, using the assumption (6.26):

P τ = def. {(P i , µ i ) ∈ P \ τ, D ((P C (τ ), µ C (τ )), (P i , µ i )) < 0} (6.27)
Denote by K τ the (n -k -1)-dimensional simplicial complex made of all up to dimension (n -k -1) simplices over vertices in P τ . K τ can alternatively be defined as the link of τ in the complete n-complex (i.e. containing all possible simplices up to dimension n) over the set of vertices τ ∪ P τ .

Observe that:

D ((P C (τ ), µ C (τ )), (P i , µ i )) < 0 ⇐⇒ (π bisτ (P i ) -o τ ) 2 -µ i + d (P i , bis τ ) 2 < µ C (τ ) (6.28)
Recall than from observation 6.6, one has, under the assumption of non positive weight in P, that µ C (τ ) ≥ 0. Denote by Height(lift((P, µ)) the height of the lift of a point (P, µ), defined as the last coordinate of the lift, so that:

Height(Φ τ (P, µ)) = (π bisτ (P ) -o τ ) 2 -µ + d(P, bis τ ) 2 (6.29)
Since under our generic conditions we have π bisτ (P )-o τ = 0, (6.27), (6.28) and (6.29) imply that:

∃v ∈ P τ ⇒ Height(Φ τ (v, µ)) > 0 (6.30)
And (6.28) and (6.30) can be rephrased as: Observation 6.18. A vertex belongs to P τ if and only if the height of its image by Φ τ is strictly less than µ C (τ ) > 0:

v ∈ P τ ⇐⇒ 0 < Height(Φ τ (v)) < µ C (τ )
It follows from the observation that we are allowed to define the following: Definition 6.19 (Shadow). Let v be a vertex in P τ . The shadow Sh τ (v) of v is a point in the (n -k)-dimensional Euclidean space bis τ defined as the intersection of the half-line starting at (0, µ C (τ )) and going through Φ τ (v) with the space bis τ .

Sh τ (P, µ) = def. µ C (τ ) µ C (τ ) -Height(Φ τ (P, µ)) (π bisτ (P ) -o τ )
This induces (in general position) an embedding of simplices: the shadow of a simplex σ ∈ K τ is a simplex in bis τ whose vertices are the shadows of vertices of σ. This in turn induces "immersions" of the chains defined on K τ into chains immersed in bis τ .

Let Γ reg be the n-chain containing the n-simplices of the regular triangulation of P and |Γ reg | the corresponding simplicial complex. Denote by X(τ )

∈ C n-k-1 (K τ ) the (n -k -1)-chain made of simplices σ ∈ K τ such that τ ∪ σ ∈ |Γ reg |: X(τ ) = def. {σ ∈ K τ , dim(σ) = n -k -1, τ ∪ σ ∈ Γ reg } (6.31)
In the following, we call polytope a finite intersection of closed half spaces ∩ i H i . The convex cone of a polytope at a point p is the intersection of all such H i whose boundary contain p. It is indeed a convex cone with apex p. Definition 6.20 (Polytope facet visible from the point 0). We say that a facet f of a polytope is visible from the point 0, or visible for short, if the closed half-space H containing the polytope and whose boundary is the supporting plane of f does not contains 0. Observe that the shadow polytope is indeed a polytope since for each lower half-space H j with boundary going through (0, µ C (τ )) and contributing to the convex cone of Φ τ (P) at (0, µ C (τ )), the intersection H j ∩ bis τ is a (n -k)-dimensional half-space in bis τ . The shadow polytope is precisely the intersection of all such half-spaces H j ∩ bis τ . Since each H j is a lower half-space and since by observation 6.18 one has µ C (τ ) > 0, H j does not contains (0, 0), which implies that H j ∩ bis τ does not contain the point o τ in bis τ . It follows hat: Observation 6.22. All facets of the shadow polytope are visible from 0. Lemma 6.23. Let P be in general position with non positive weights. We have the following:

1. τ is in the regular triangulation of P if and only if Φ τ (τ ) = (0, µ C (τ )) is an extremal point of the convex hull of Φ τ (P).

2. When τ is in the regular triangulation of P, its link is isomorphic to the link of the vertex Φ τ (τ ) = (0, µ C (τ )) in the simplicial complex corresponding to the boundary of the lower convex hull of Φ τ (P).

3. When τ is in the regular triangulation of P, Sh τ induces a simplicial isomorphism between | X(τ )| and the set of bounded faces of the boundary of the shadow polytope.

Proof. 1. follows from Corollary 6.17 item 1. together with Proposition 6.12. 2. follows from Corollary 6.17 item 2. together with Proposition 6.12. For 3. consider a simplex σ ∈ X(τ ). Φ τ (σ) is a simplex in the link of Φ τ (τ ) in the lower convex hull of Φ τ (P) and therefore the convex cone CC σ with apex Φ τ (τ ) and going through Φ τ (|σ|) is on the boundary of the convex cone CC P with apex Φ τ (τ ) and going through the convex hull of Φ τ (P).

Therefore Sh τ (σ), intersection of CC σ with bis τ is on the boundary of the shadow polytope, intersection of CC P with bis τ .

Sh τ (σ) is bounded as being the convex hull of the shadow of its vertices. Thanks to observation 6.22, it is a facets of the boundary of the shadow polytope visible from 0. In the reverse direction, a bounded facet of the boundary of the shadow polytope is precisely the shadow of a simplex Φ τ (σ) in the link of Φ τ (τ ) in the lower convex hull of Φ τ (P) with all its vertices in P τ . Therefore σ ∈ X(τ ). This bijection extends to lower-dimensional faces of | X(τ )| and is a simplical map.

Convex cone as lexicographic minimal chain

We start this section by giving the two lemmas 6.25 and 6.26, instrumental in the proof of 6.27.

Trace of a chain in a link

Definition 6.24 (Trace of a chain in a link). Given a k-simplex τ in a simplical complex K and a n-chain on K for n > k, we call trace of Γ on the link of τ the (n -k -1)-chain Tr τ (Γ) defined in the link of τ defined by:

Tr τ (Γ)(σ) = Γ(τ ∪ σ)
Next lemma is used twice in what follows. Lemma 6.25. Given a k-simplex τ in a simplical complex K and a n-chain Γ on K for n > k, one has:

∂ Tr τ (Γ) = Tr τ (∂Γ)
Proof. We need to prove that for any simplex σ in the link of τ , one has:

∂ Tr τ (Γ)(σ) = Tr τ (∂Γ)(σ)
We have by definition that a (n Proof. Assume for a contradiction that x is in the relative interior of X, that is there is some ρ > 0 such that B(x, ρ) ∩ X = B(x, ρ) ∩ ∂C. Then all facets containing x are visible from O. if x is not a vertex pf C, it belongs then to the relative interior of a convex face f in ∂C with dim f ≥ 1. Then we have a contradiction since the function y → d(P, y) is convex on f and cannot have an interior local maximum at x. We assume now that x is a vertex of C.

-k -2)-simplex σ is in Tr τ (∂Γ)(σ) if and only if τ ∩ σ = ∅ and τ ∪ σ is in ∂Γ. In
Following for example [START_REF] Federer | Curvature measures[END_REF][START_REF] Tyrrell | Convex analysis[END_REF], denote by Tan x C and Nor x C respectively the Tangent and Normal cone to C at x. In case of a closed polytope they can be expressed as:

Tan x C = ρ>0 {λ(c -x), λ ≥ 0, c ∈ B(x, ρ)} and Nor x C = (Tan x C) ⊥ = def. {u, ∀v ∈ Tan x C, u, v ≤ 0} (6.32)
Since C is a convex polytope, Tan x C is a convex closed cone and one has [START_REF] Tyrrell | Convex analysis[END_REF]:

Tan x C = (Nor x C) ⊥ = def. {v, ∀u ∈ Nor x C, u, v ≤ 0} (6.33)
Each facet F i of C containing x is supported by a half-space H i = {y, y -x, n i ≤ 0} and one has:

Nor x C = i λ i n i , ∀i, λ i ≥ 0 (6.34) ∀i, O -x, n i > 0
This with (6.34) gives: ∀u ∈ Nor x C, O -x, u > 0 (6.35) using (6.33) we get that O -x is in the interior of -Tan x C i.e.:

x

-O ∈ (Tan x C) • (6.36)
Since x is a vertex of C, Tan x C is the convex hull of Tan x ∂C, therefore (6.36) implies at there are t 1 , . . . t n+1 ∈ Tan x ∂C and λ 1 , . . . λ n+1 ≥ 0 such that:

x -O = i λ i t i which gives: 0 < x -O, x -O = x -O, i λ i t i = i λ i x -O, t i
Since all the λ i are not negative, there must be at least one i for which:

x -O, t i > 0
This precisely means that y → d(P, y) is increasing in the direction t i in a neighborhood of x in X, a contradiction since x is assumed to be a local maximum of y → d(P, y) in X.

lexicographic order on shadows

We define now another order on simplices together with its induced order on chains, respectively denoted ≤ Sh and Sh . We add the . Sh suffix because these orders are meant to be applied to shadow simplices and chains. However, this section is self-contained and does not relies on previous construction. Lemma 6.27 is a result in itself: convex hulls can be defined as minimal lexicographic chains. Applying it to a translation (to match the visibility from 0 requirement) of the lift polytope could give directly a lexicographic order whose minimum is a regular triangulation, at the price of the lost of invariance by isometry of the order on simplices.

We associate to a (n -1)-simplex σ in R n that does not contain 0 a dimension increasing sequence of faces ∅ = τ -1 (σ) ⊂ τ 0 (σ) ⊂ . . . ⊂ τ n-1 (σ) = σ with dim(τ i ) = i. Under a simple generic condition (unicity of the max in (6.37)), it is defined as follows.

τ -1 (σ) = ∅ and τ 0 (σ) is the vertex of σ farthest from 0. More generally, define the distance from a flat (an affine space) F to 0 as d 0 (F ) = inf p∈F d(p, 0). In other words, d 0 (F ) is the distance from 0 to the orthogonal projection of 0 on

F . If ζ is a non degenerate i-simplex for i ≥ 0, defines d 0 (ζ) = d 0 (F (ζ)) where F (ζ) is the i-dimensional flat support of ζ. For i ≥ 0, τ i (σ) is the coface of dimension i of τ i-1 (σ) whose supporting i-flat is farthest from 0: τ i (σ) = def.
arg max

ζ⊃τ i-1 (σ) dim(ζ)=i d 0 (ζ) (6.37)
For i = 0, . . . , n -1 we set δ i (σ) = d 0 (τ i (σ)) and the comparison < Sh between two (n -1)simplices σ 1 and σ 2 is a lexicographic order on the sequences (δ i (σ 1 )) i=0,...n-1 and (δ i (σ 2 )) i=0,...n-1 :

σ 1 < Sh σ 2 ⇐⇒ def. ∃k ≥ 0, δ k (σ 1 ) < δ k (σ 2 ) and ∀j, 0 ≤ j < k, δ j (σ 1 ) = δ j (σ 2 ) (6.38)
which defines an order relation: The following generic condition says that the sequence of δ i (σ) does not coincide for two different simplices.

σ 1 ≤ Sh σ 2 ⇐⇒ def. σ 1 = σ 2 or σ 1 < Sh σ 2 (6.
Condition 6.3. Let K be a (n -1)-dimensional simplicial complex. For any pair of simplices

σ 1 , σ 2 ∈ K: dim(σ 1 ) = dim(σ 2 ) = k and d 0 (σ 1 ) = d 0 (σ 2 ) ⇒ σ 1 = σ 2
Observe that, under condition 6.3, ≤ Sh is a total order on simplices. As for the lexicographic order lex , following definition 6.1 the order ≤ Sh on simplices induces a lexicographic order Sh on k-chains of K. Lemma 6.27. Let P be a set of points in R n such that 0 ∈ R n is not in the convex hull of P . Let K be the complete (n-1)-dimensional simplicial complex over P , i.e. the simplicial complex made of all (n -1)-simplices whose vertices are points in P with all their faces. Assume that K satisfies the generic condition 6.3.

Let X be a (n -1)-chain in K whose (n -1)-simplices are in convex position, i.e. contribute to the boundary of the convex hull of P , and are all visible from 0 ∈ R n .

Then:

X = min Sh {Γ ∈ C n-1 (K), ∂Γ = ∂X} (6.40)
where when n = 1 the boundary operator in (6.40) is meant as the boundary operator of reduced homology, i.e the linear operator ∂0 : C n-1 (K) → Z 2 that counts the parity.

Proof. We first claim that the lemma holds for n = 1. In this case the fact that 0 is not in the convex hull of P means that the 1-dimensional points in P are either all positive, either all negative. The single simplex in the convex hull boundary visible from 0 is the point in P closest to 0, i.e. the one with the smallest absolute value, which corresponds to the minimum chain with odd parity in the Sh order, which proves the claim.

We assume then the theorem to be true for the dimension n -1 and proceed by induction. This recursion is illustrated on figure 6.5 for n = 2 and figure 6.6 for n = 3.

Consider the minimum: We need to prove that Γ min = X.

Γ min = min Sh {Γ ∈ C n-1 (K), ∂Γ = ∂X} (6.41)
Let v be the (unique) vertex in the simplices of ∂X which is farthest from 0. Since v is a vertex in at least one simplex in ∂X = ∂Γ min , it must be a vertex in some simplex in Γ min .

We claim that v is also the vertex in the simplices of X which is farthest from 0. Indeed, X is made of visible facets of the boundary of CH(P ), the convex hull of P . Thanks to Lemma 6.26, if x is a local maximum in X of the distance to 0 one has x ∈ ∂X and the claim follows.

Since v is the vertex in X farthest from 0 and since by definition Γ min Sh X, we know that Γ min does not contain any vertex farther from the origin than v, therefore v is also the vertex in the simplices of Γ min farthest from 0.

Since ∂Γ min = ∂X, Lemma 6.25 implies that:

∂ Tr v (Γ min ) = Tr v (∂Γ min ) = Tr v (∂X) (6.42)
In order to define a lexicographic order on chains on the link of v in K, we use a transformation very similar to the shadow of definition 6.19. Specifically, we consider the hyperplane Π containing 0 and orthogonal to the line 0v. We associate to any (n -2)-simplex η ∈ Lk K (v) the (n -2) simplex π vΠ (η) conical projection of η on Π with center v. In other words, if u is a vertex of η:

{π vΠ (u)} = Π ∩ uv
where uv denote the line going through u and v. π vΠ is a conical projection on vertices but it extends to a bijection on simplices and an isomorphism on chains that trivially commutes with the boundary operator. By definition of the lexicographic order Sh , the comparison of two chains whose farthest vertex is v starts by comparing their restrictions to the star of v. Therefore, since v is the farthest vertex in Γ min , the restriction of Γ min to the star of v must be minimum under the constraint ∂Γ = ∂X. The constraint ∂Γ = ∂X for the restriction of Γ min to the star of v is equivalent to the constraint given by equation (6.42) or equivalently by:

∂π vΠ (Tr v (Γ min )) = π vΠ (Tr v (∂X))
and the minimization on the restriction of the (n-1)-chain Γ min to the star of v can equivalently be expressed as the minimization of the (n-2)-chain γ min = π vΠ (Tr v (Γ min )) under the constraint ∂γ min = π vΠ (Tr v (∂X)), we have then:

γ min = π vΠ (Tr v (Γ min )) = π vΠ Tr v min Sh {Γ ∈ C n-1 (K), ∂Γ = ∂X} (6.43) = min Sh {γ ∈ C n-2 (π vΠ (Lk K (v))) , ∂γ = π vΠ (Tr v (∂X))} = min Sh {γ ∈ C n-2 (π vΠ (Lk K (v))) , ∂γ = ∂π vΠ (Tr v (X))}
In the third equality of (6.43) we have used the fact that the orders on (n -1)-simplices in the star of v in K and the order on corresponding (n -2)-simplices in the image by π vΠ of the link of v are compatible.

Indeed, if F is a k-flat in R n going through v, we have (see figure 6.7):

d 0 (π vΠ (F )) = d 0 (F ∩ Π) = d 0 (F ) v -0 (v -0) 2 -d 0 (F ) 2 (6.44)
with the convention d 0 (π vΠ (F )) = +∞ in the non generic case where F ∩ Π = ∅ (the denominator vanishes in this case while since v ∈ F one has

F ∩ Π = ∅ ⇒ d 0 (F ) < v -0 ).
As seen on (6.44) d 0 (F ) → d 0 (π vΠ (F )) is an increasing function and the orders are therefore consistent along the induction.

We claim that the minimization problem in the last member of (6.43) satisfies the condition of the theorem for n = n -1 which is assumed true by induction.

Recursion:

The hyperplane Π corresponds to R n with n = n -1.

• n ← n -1

• P ← π vΠ (P \ {v}) • K ← π vΠ (Lk K (v)) • X ← π vΠ (Tr v (X))
Since (n -1)-simplices in X are in convex positions, hyperplanes supporting these simplices, in particular the simplices in the star of v, separate all points of P from 0. It follows that the intersection of theses hyperplanes with the horizontal hyperplane, i.e. the images by π vΠ of the hyperplanes, separates P = π vΠ (P \ {v}) from 0.

It follows that the (n -1)-simplices in X = π vΠ (Tr v (X)) are in convex position and are visible from 0.

Therefore one can apply our lemma recursively, which gives us, using (6.43):

γ min = π vΠ (Tr v (Γ min )) = π vΠ (Tr v (X))
It follows that the faces in the star of v corresponding to Tr v (Γ min ) belong to X. Call Y the (n-1)-chain made of these simplices in the star of v. We have both Y ⊂ X and Y ⊂ Γ min . Since v is the vertex farthest from 0 in both X and in Γ min one has by definition of the lexicographic order:

Γ min = min lex {Γ ∈ C n-1 (K), ∂Γ = ∂X} = Y + min lex {Γ ∈ C n-1 (K), ∂Γ = ∂(X -Y )}
So, by considering the new problem X ← (X -Y ) and iterating as long as X is not empty, we get our final result Γ min = X.

Proof of Theorem 6.2

Equivalence between Sh and lex restricted to simplices with same bounding weight In order to establish the connexion between the orders lex and Sh we first need the following (K τ is defined just after (6.27)): Lemma 6.28. For σ 1 , σ 2 ∈ K τ , one has:

µ C (τ ∪ σ 1 ) ≥ µ C (τ ∪ σ 2 ) ⇐⇒ d 0 (Sh τ (σ 1 )) ≤ d 0 (Sh τ (σ 2 )) (6.45)
Proof. Using the definition 6.5, one has:

(P C , µ C ) (π τ (τ ) ∪ π τ (σ)) = arg min
(P,µ)∈R n ×R ∀(P i ,µ i )∈πτ (τ )∪πτ (σ),D((P,µ),(P i ,µ i ))=0 µ (6.46)

Since both terms of (6.45) are invariant by a global translation, we can assume without loss of generality and in order to make the computations simpler that o τ = 0.

In this case, as seen in (6.20) the coordinates of π τ (τ ) are (0, -µ C (π τ (τ )) = (0, -µ C (τ )) by (6.25). So that D ((P, µ), π τ (τ )) = 0 gives us:

µ = P 2 + µ C (τ ) (6.47)
It follows that among the weighted points (P, µ) that satisfy D ((P, µ), π τ (τ )) = 0, minimizing µ is equivalent to minimizing P 2 and one can reformulate the characterization (6.46) of

(P C , µ C ) (π τ (τ ∪ σ)) = (P C , µ C ) (π τ (τ ) ∪ π τ (σ)) as: (P C , µ C ) (π τ (τ ) ∪ π τ (σ)) = arg min (P,µ)∈R n ×R ∀(P i ,µ i )∈πτ (τ )∪πτ (σ),D((P,µ),(P i ,µ i ))=0 P 2
(6.48)

For (P, µ) ∈ R n-k × R, define the hyperplane Π (P,µ) in R n-k × R as: (X, z) ∈ Π (P,µ) ⇐⇒ def.
z = (µ -P 2 ) + 2 P, X (6.49)

Observe that: D ((P, µ),

(P i , µ i )) = 0 ⇐⇒ lift(P i , µ i ) ∈ Π (P,µ)
So that the definition of (P C , µ C ) (π τ (τ ) ∪ π τ (σ)) given in (6.48) can be equivalently formulated as Π (P C ,µ C ) being the hyperplane in R n-k × R that minimizes P 2 C among all hyperplanes containing both lift(π τ (τ )) and all the points in lift(π τ (σ)).

But, as seen on (6.49), 2 P C is the slope of the hyperplane Π (P C ,µ C ) so that Π (P,µ) is the hyperplane with minimal slope going through Φ τ (τ ) = lift(π τ (τ )) and all the points in Φ τ (σ) = lift(π τ (σ)). This slope 2 P C is also the slope of the unique (dim(σ) + 1)-dimensional affine space F going through Φ τ (τ ) = lift(π τ (τ )) = (0, µ C (τ )) and all the points in Φ τ (σ) = lift(π τ (σ)). Since F ∩ R n-k × {0} is the affine space supporting Sh τ (σ), one has:

d 0 (Sh τ (σ)) = µ C (τ ) 2 P C (π τ (τ ) ∪ π τ (σ))
so that, using (6.25) for the second equality:

d 0 (Sh τ (σ)) = µ C (τ ) 2 µ C (π τ (τ ) ∪ π τ (σ)) -µ C (τ ) = µ C (τ ) 2 µ C (τ ∪ σ) -µ C (τ ))
It follows that the map:

µ C (τ ∪ σ) → d 0 (Sh τ (σ))
is decreasing.

For a n-chain Γ denote by ↓ ρ Γ the chain obtained by removing from Γ all simplices with bounding weight strictly greater than ρ.

↓ ρ Γ = def. {σ ∈ Γ, µ B (σ) ≤ ρ} (6.50)
By definition of lex , since in (6.9) one has always µ 0 (τ ∪ σ 1 ) = µ 0 (τ ∪ σ 2 ) = µ = B , it goes like this:

σ 1 < σ 2 ⇐⇒ def. ∃k ≥ 1, µ k (τ ∪ σ 1 ) > µ k (τ ∪ σ 2 ) and ∀j, 0 ≤ j < k, µ j (τ ∪ σ 1 ) = µ j (τ ∪ σ 2 ) (6.52)
Observe that this expression is similar to (6.38). For a 0-simplex {v} ∈ K P , the circumweight µ C (τ ∪ {v}) is, according to Lemma 6.28, a decreasing function of the distance d 0 (Sh τ (η)) between its shadow and the origin. It follows that for a (n-k -1)-simplex σ ∈ K P , the vertex v for which the circumweight µ C (τ ∪{v}) is minimal has its shadow Sh τ (v) maximizing the distance to the origin. This minimal circumweight is µ 1 (τ ∪ {v}) while this maximal distance is δ 0 (σ).

More generally, looking at (6.37) and (6.8), Lemma 6.28 allows to check that the simplex Θ k (σ) of (6.8) in the star of τ in K P corresponds to the simplex τ k-1 (σ) in (6.37) in the link of τ :

Θ k (σ) = τ ∪ τ k-1 (σ)
So that for σ 1 , σ 2 ∈ K P referring to (6.38) and (6.52):

µ k (τ ∪ σ 1 ) ≤ µ k (τ ∪ σ 2 ) ⇐⇒ δ k-1 (σ 1 ) ≥ δ k-1 (σ 2 ) It follows that, for Γ 1 , Γ 2 ∈ C n (K P ) and τ = τ µ = B : → µ = B Γ 1 lex → µ = B Γ 2 ⇐⇒        Sh τ Tr τ µ = B ↓ µ = B Γ 1 Sh Sh τ µ = B Tr τ µ = B ↓ µ = B Γ 2
which, with claim (6.51), ends the proof.

Proof of main Theorem

Proof of Theorem 6.2. We prove Theorem 6.2 in the case of non positive weights which then extends to any weights thanks to observations 6.8 and 6.7.

As in Proposition 6.13, denote by Γ reg the chain that defines the regular triangulation of CH(P). As in Theorem 6.2 denote by β P ∈ C n-1 (K P ) the (n -1)-chain made of simplices belonging to the boundary of CH(P).

According to Proposition 6.13 Γ reg minimizes Γ → Γ (p) among the chains with boundary β for any p ≥ 1. In particular Γ reg minimizes Γ → Γ p for the value p of Lemma 6.15. Proposition 6.13 and Theorem 6.2 consider a minimum with respect to the same boundary condition while their objective differ.

In order to prove Theorem 6.2 we have to show that both minimum agree. For a contradiction, we assume now that they differ, which means that, Γ min = Γ reg , or equivalently that Γ min + Γ reg = 0 where Γ min is the minimal chain of Theorem 6.2.

Consider µ = B to be the largest bounding weight for which some simplex in Γ min and Γ reg differ:

µ = B = def. max{µ B (σ), σ ∈ Γ min + Γ reg }
There must be at least one simplex with bounding weight µ = B in Γ reg as, otherwise, by definition of µ = B there would be a simplex with radius µ = B in Γ min and this would give Γ reg lex Γ min with Γ reg = Γ min and since ∂Γ reg = ∂Γ min = β P this contradicts the definition of Γ min .

Similarly, it follows from Lemma 6.15 that if there was no simplex with bounding weight µ = B in Γ min , one would have Γ min p < Γ reg p and ∂Γ reg = ∂Γ min : a contradiction with the minimality of Γ reg for norm • p (Proposition 6.13).

We have shown that if they differ, both Γ reg and Γ min must contain at least one simplex with bounding weight µ = B . We know from the generic conditions that the set of simplices with bounding weigth µ = B are all cofaces of some unique dimension minimal simplex τ µ = For a n-chain Γ ↓ ρ Γ is defined by (6.50). By definition of µ = B one has:

↓ µ = B Γ reg -↓ µ = B Γ min = Γ reg -Γ min (6.53)
In order to spare our eyes, we allow ourselves to replace for the rest of the section:

↓ µ = B by ↓ τ µ = B by τ
It follows from (6.53) that:

∂ (↓ Γ reg -↓ Γ min ) = ∂Γ reg -∂Γ min = β P -β P = 0
It follows that ↓ Γ reg and ↓ Γ min have same boundary and Lemma 6.25 says that their trace have also same boundary:

∂ Tr τ (↓ Γ min ) = ∂ Tr τ (↓ Γ reg ) (6.54)
Observe that Tr τ (↓ Γ reg ) coincide with the definition of X(τ ) in (6.31). We know then from Lemma 6.23 that the shadows of simplices in X(τ ) = Tr τ (↓ Γ reg ), that is Sh τ (X(τ )) = Sh τ (Tr τ (↓ Γ reg )) is a chain in Sh τ (K τ ) made of the faces of the convex hull of Sh τ (P τ ) visible from the origin 0, where P τ and K τ are as defined in (6.27) and following lines.

In the remaining of this proof we use a lexicographic order Sh on shadows of (n -k -1)chains in K τ , defined at the beginning of section 6.9. This order is equivalent to the order lex on corresponding n-chains restricted to the set of simplices with bounding weight µ = B (Lemmas 6.28 and 6.29).

This correspondance allows to conclude the proof by applying Lemma 6.27 that says that the chain defined by visible faces of a polytope minimises the lexicographic order Sh among chains with same boundary.

More formally, thanks to Lemma 6.29 we have:

↓ Γ 1 lex ↓ Γ 2 ⇒ Sh τ (Tr τ (↓ Γ 1 )) Sh Sh τ (Tr τ (↓ Γ 2 ))
It follows that Sh τ (Tr τ (↓ Γ min )) is, among all chain in the complex Sh τ (K τ ), the one that minimises Sh under the constraint (6.54), or equivalently:

∂ Sh τ (Tr τ (↓ Γ min )) = ∂ Sh τ (Tr τ (↓ Γ reg ))
Lemma 6.27 applied with:

n ← n -k X ← Sh τ (Tr τ (↓ Γ reg )) = Sh τ (X(τ )) P ← Sh τ (P τ ) K ← Sh τ (K τ ) implies: Sh τ (Tr τ (↓ Γ min )) = Sh τ (Tr τ (↓ Γ reg ))
In other words, Γ min and Γ reg coincide on simplices with bounding weight µ = B , a contradiction with the definition of µ = B .

Chapter 7

Particular case of 2-chains

We focus now on the case of 2-simplices and 2-chains in Euclidean space R n , with n ≥ 2. We consider the Delaunay case, i.e. the weights are zero. Indeed, when d = 2, Lemma 7.3 gives us an explicit expressions of the asymptotic behavior of w p (σ) as p → ∞ that allows a finer analysis.

≤ ∞ , ∞ and lex preorders

The weights of simplices σ → w p (σ) and the norm of chains Γ → Γ 1 (p) have been respectively defined in (6.13) and (6.14) in section 6.6 in the general case. In this section we consider the same definition but we are in the particular case where the weights of points are zero and we focus on the case where the dimension of simplices and chains is 2.

We now introduce the binary relation ≤ ∞ on the set of d-simplices of K.

Definition 7.1 (Preorder ≤ ∞ on d-simplices of K). σ 1 ≤ ∞ σ 2 ⇐⇒ def. ∃p ∈ [1, ∞[, ∀p ∈ [p, ∞[, w p (σ 1 ) ≤ w p (σ 2 )
It is straightforward to check that ≤ ∞ is reflexive and transitive, and therefore a preorder. We show below that, at least for d = 2, by assuming a generic condition on the point sample P, it becomes a total order. We also introduce the binary relation ∞ on the set of d-chains of K:

Definition 7.2 ( ∞ order on chains). For Γ 1 , Γ 2 ∈ C d (K): Γ 1 ∞ Γ 2 ⇐⇒ def. ∃p ∈ [1, ∞), ∀p ∈ [p, ∞), Γ 1 (p ) ≤ Γ 2 (p )
∞ is also a preorder on C d (K). When ≤ ∞ is a total order on simplices it induces, according to definition 2.1, a total order on chains lex on d-chains. We see below that this occurs generically when d = 2.

Limit of Delaunay energy and ≤ ∞ order

Limit of Delaunay energy as p → ∞ We say that a triangle σ = abc is non-degenerate if it spans a 2-dimensional affine space. For a compact set of points S, SEB(S) denotes the Smallest Enclosing Ball of S, i.e. the unique closed Euclidean ball with minimal radius containing S. For triangle abc denote R C (abc) and R B (abc) respectively the circumradius and the radius of the minimal enclosing circle SEB(abc). Observe that R C (abc) and R B (abc) coincide if and only if triangle abc is acute or right.

Following lemma gives an explicit expression of the asymptotic behavior of w p (σ) as p → ∞ . The proof consists of computations and is reported to Appendix B. -if abc is strictly acute:

w p (abc) p = π 1 p R B (abc) 2+2p ω abc (p)
-if abc is right:

w p (abc) p = π 2 1 p R B (abc) 2+2p ω abc (p)
-if abc is obtuse:

w p (abc) p = 1 h 2 1 p 2 R B (abc) 2+2p ω abc (p)
with:

h 2 = R C (abc) 2 -R B (abc) 2 R B (abc) 2
As seen before, the binary relation ≤ ∞ introduced in definition 7.1 is reflexive and transitive, in other words it is a preorder. We show now that when d = 2, and by assuming a generic condition on the point set, it becomes a total order.

We say that a triangle σ = abc is non-degenerate if it spans a 2-dimensional affine space. Since lim p→∞ w p (σ) = w ∞ (σ), one has:

w ∞ (σ 1 ) < w ∞ (σ 2 ) ⇒ σ 1 ≤ ∞ σ 2 (7.1) and σ 1 ≤ ∞ σ 2 ⇒ w ∞ (σ 1 ) ≤ w ∞ (σ 2 (7.2)
However one can check on the example given below of two obtuse triangles with a same longest edge that the relation σ 1 ≤ ∞ σ 2 is finer than w ∞ (σ 1 ) ≤ w ∞ (σ 2 ): the converse of (7.2) does not hold.

Recall that a property P on sample sets is generic if the set of samples with N points, S ∈ R nN , verifying P is a dense open subset of R nN . We may also require its complement to be of zero Lebesgue measure.

For two obtuse triangles abc and abd sharing the same longest edge ab we have:

w ∞ (abc) = R B (abc) 2 = ((a -b)/2) 2 = R B (abd) 2 = w ∞ (abd)
Since the property of being obtuse and sharing the same longest edge is stable under infinitesimal perturbations of {a, b, c, d}, there is no generic property enforcing the binary relation w ∞ (σ 1 ) ≤ w ∞ (σ 2 ) to be antisymmetric. In contrast, as shown by Lemmas 7.4 and 7.6 below, ≤ ∞ can be made antisymmetric, and therefore a total order, under generic condition 7.1 below.

Next lemma, easy consequence of Lemma 7.3, describes sufficient geometric implications of ≤ ∞ . Lemma 7.4. If σ 1 and σ 2 are non degenerate triangles, then:

σ 1 ≤ ∞ σ 2 ⇒        R B (σ 1 ) < R B (σ 2 ) or R B (σ 1 ) = R B (σ 2 ) and R C (σ 1 ) ≥ R C (σ 2 )
and:

σ 1 ≤ ∞ σ 2 ⇐        R B (σ 1 ) < R B (σ 2 ) or R B (σ 1 ) = R B (σ 2 ) and R C (σ 1 ) > R C (σ 2 ) proof of Lemma 7.4. If R B (σ 1 ) = R B (σ 2 ) equation (7.2) gives σ 1 ≤ ∞ σ 2 ⇐⇒ R B (σ 1 ) < R B (σ 2 )
. Therefore one just has to consider the case when R B (σ

1 ) = R B (σ 2 ). We assume then R B (σ 1 ) = R B (σ 2 ): if R C (σ 1 ) < R C (σ 2 )
, both triangles are obtuse and Lemma 7.3 shows that one cannot have

σ 1 ≤ ∞ σ 2 , while if R C (σ 1 ) > R C (σ 2 ), the same lemma gives σ 1 ≤ ∞ σ 2 .
Lemma 7.4 suggests the following generic property: Condition 7.1. Generic condition:

1. Any triangle in K is non-degenerate, 2. for any two triangles σ 1 and σ 2 in K, one has:

SEB(σ 1 ) = SEB(σ 2 ) ⇒ R B (σ 1 ) = R B (σ 2 )
3. for any two triangles σ 1 and σ 2 , one has: Proof. Since the intersection of a finite number of dense open sets is a dense open set, it is enough, in order to show that Condition 7.1 is generic, to prove that it is the conjonction of a finite set of generic conditions.

       σ 1 = σ 2 and S = SEB(σ 1 ) = SEB(σ 2 ) ⇒        R C (σ 1 ) = R C (σ 2 ) and ∃ab = σ 1 ∩ σ 2 , S =
The condition for 3 points to span a 2 space, i.e. to not lie on a same line, is clearly generic since it can be expressed as saying that c does not lie on line ab.

For the second condition, we say that a vertex a of σ contributes to SEB(σ) if it belongs to the boundary of SEB(σ). The condition SEB(σ 1 ) = SEB(σ 2 ) is open and it says that at least either a vertex a 2 of σ 2 which is not a vertex of σ 1 contributes to SEB(σ 2 ), either a vertex a 1 of σ 1 which is not a vertex of σ 2 contributes to SEB(σ 1 ). In both cases the set of position of vertex a 2 or a 1 that enforces R B (σ 1 ) = R B (σ 2 ) is open and dense.

For the third condition, let's consider two triangles σ 1 , σ 2 verifying σ 1 = σ 2 and S = SEB(σ 1 ) = SEB(σ 2 ). We consider the number of points contributing to S. As a smallest enclosing ball of a triangle requires at least two contributing points and having four (or more) points on a sphere is not a generic condition, we have two cases to consider:

-If two points contribute to S, both triangles are obtuse and share this longest edge.

-If three points contribute to S, as σ 1 = σ 2 , both triangles cannot be acute and therefore one triangle is obtuse and shares its longest edge with the other triangle.

In both case, at least one vertex of the triangles is not on the sphere S and the set of its coordinates satisfying R C (σ 1 ) = R C (σ 2 ) is open and dense.

Lemma 7.6. If Condition 7.1 holds, ≤ ∞ is a total order on the set of 2-simplices of K with:

σ 1 ≤ ∞ σ 2 ⇐⇒        R B (σ 1 ) < R B (σ 2 ) or R B (σ 1 ) = R B (σ 2 ) and R C (σ 1 ) ≥ R C (σ 2 ) (7.3)
Proof. To get the equivalence property from Lemma 7.4, see that under Condition 7.1.2:

R B (σ 1 ) = R B (σ 2 ) and R C (σ 1 ) = R C (σ 2 ) ⇒ SEB(σ 1 ) = SEB(σ 2 )
which in turn implies

σ 1 = σ 2 from Condition 7.1.3.
The preorder ≤ ∞ is immediately total using this equivalence property (i.e. σ 1 ≤ ∞ σ 2 or σ 2 ≤ ∞ σ 1 always holds true). We can now easily show its antisymmetry property from Equation 7.3 rendering ≤ ∞ a total order:

σ 1 ≤ ∞ σ 2 and σ 2 ≤ ∞ σ 1 (7.4) ⇒ R B (σ 1 ) = R B (σ 2 ) and R C (σ 1 ) = R C (σ 2 ) ⇒ σ 1 = σ 2 (7.5)
In the sequel of the section, we assume generic Condition 7.1. ≤ ∞ is a total order and we can define naturally the corresponding increasing and decreasing strict orders < ∞ and > ∞ .

Delaunay ∞ and lex orders

Thanks to Lemma 7.6, under generic condition 7.1, ≤ ∞ is a total order on triangles that induces, according to definition 2.1, a total order lex on 2-chains.

We compare now lex with the binary relation ∞ introduced in Definition 7.2.

lex and ∞ differ: Even under generic condition 7.1, relations ∞ and lex are not equivalent in general. Indeed, if σ 1 , σ 2 , σ 3 are obtuse triangles sharing a same longest edge (which happens generically) such that w ∞ (σ 1 ) = w ∞ (σ 2 ) = w ∞ (σ 3 ) with:

h 2 i = R C (σ i ) 2 -R B (σ i ) 2 R B (σ i ) 2 such that h 1 < h 2 , h 3 but 1 h 2 1 < 1 h 2 2 + 1 h 2 3
Lemma 7.3 gives us:

σ 1 ∞ σ 2 + σ 3 and ¬ (σ 2 + σ 3 ∞ σ 1 ) while since h 1 < h 2 , h 3 ⇒ σ 2 , σ 3 < ∞ σ 1 one has: σ 2 + σ 3 lex σ 1
However as it will be seen, minima of ∞ can coincide with minima of lex , at least in Čech and Rips complexes.

When ∞ and lex have same minima

The aim of this section is to show that for d = 2, under generic condition 7.1, ∞ and lex in Čech and Rips complexes have same minima under boundary or homology constraints.

Čech and Rips complexes

Recall that, given a finite set of points P ⊂ R n , the Čech complex with parameter λ is the simplicial complex made of all simplices σ such that the radius of SEB(σ) is less or equal to λ. The proximity graph G(P, λ) is the graph whose vertices are in bijection with points in P and with one edge for each pair {a, b} ∈ P whose length is not greater than λ. The corresponding Vietoris-Rips complex is the flag complex of the proximity graph G(P, λ), i.e the simplicial complex made of all cliques in G(P, λ). Lemma 7.7. Let P ⊂ R n be a finite set of points satisfying generic condition 7.1 and let K be a Čech or Vietoris-Rips complex over P. Let D ⊂ C 2 (K) be a set of chains in either of these forms:

D = {Γ ∈ C 2 (K) | ∃B ∈ C 3 (K) , Γ -A = ∂B} or, D = {Γ ∈ C 2 (K) | ∂Γ = β} for some A ∈ C 2 (K) or for some 1-cycle β ∈ Z 1 (K).
If Γ ∈ C 2 (K) is a minimum in D for one of the orders ∞ or lex , then Γ cannot contain two obtuse triangles sharing the same longest edge.

Proof. Consider two obtuse triangles abc, abd ∈ K with same longest edge ab.

If K is Cech complex with parameter λ we must have b -a ≤ λ/2. Since the ball with diameter ab contains the points a, b, c, d, the triangles acd and bcd as well as the tetrahedron abcd belongs to K. Now if K is a Vietoris-Rips complex with parameter λ we must have b -a ≤ λ and, again, acd and bcd as well as the tetrahedron abcd belongs to K.

It follows that, in both cases, abc+abd is homologous to and has same boundary as acd+bcd in K. Therefore, if some chain Γ contains abc and abd then, the chain Γ = Γ+abc+abd+acd+bcd is homologous and has same boundary as Γ. One checks easily that, while Γ = Γ, one has Γ ∞ Γ and Γ lex Γ and Γ cannot be minimum in D for one of the orders ∞ or lex .

The formal proof of next lemma is reported to Appendix C. However, it is intuitively plausible since Lemma 7.7 forbids the situation described in section 7.3 where ∞ and lex differ. Lemma 7.8. Let P ⊂ R n be a finite set of points satisfying generic condition 7.1 and let K be a Čech or Vietoris-Rips complex over P. Let D ⊂ C 2 (K) be a set of chains in either of these forms:

D = {Γ ∈ C 2 (K) | ∃B ∈ C 3 (K) , Γ -A = ∂B} or, D = {Γ ∈ C 2 (K) | ∂Γ = β} for some A ∈ C 2 (K) or for some 1-cycle β ∈ Z 1 (K).

Then: min

∞ D = min lex D
Lemma 7.8 applies to 2-chains in Euclidean n-space. In the particular case where n = 2 it allows to give an elementary proof of a specialization of Theorem 6.2 or Corollary 6.3: Proposition 7.9. Let P = {P 1 , . . . , P N } ⊂ R 2 with N ≥ 3 be in general position and let K P be the 2-dimensional full complex over P. Denote by β P ∈ C 1 (K P ) the 1-chain made of edges belonging to the boundary of CH(P).

Then if:

Γ min = min lex {Γ ∈ C 2 (K P ), ∂Γ = β P } then the simplicial complex |Γ min | support of Γ min is the Delaunay triangulation of P.

Proof. Looking at Definition 7.2, we see

that if Γ 1 ≤ ∞ Γ 2 there is p(Γ 1 , Γ 2 ) large enough such that for any p ≥ p(Γ 1 , Γ 2 ), Γ 1 (p ) ≤ Γ 2 (p )
. Since there are only a finite number of chains Γ in a given finite simplicial complex, one can define for a given simplicial complex p = max Γ 1 ∞Γ2 p(Γ 1 , Γ 2 ) such that:

Γ 1 ∞ Γ 2 ⇐⇒ Γ 1 (p) ≤ Γ 2 (p)
Consider now Proposition 6.13 in the case of zero weights and n = 2. It implies that the support of the chain: min

∞ {Γ ∈ C 2 (K P ), ∂Γ = β P }
is the Delaunay triangulation of P. Applying Lemma 7.8 complete the proof.

Chapter 8

Application to point cloud triangulations

Sections 3, 4 and 5 were motivated by the study of polynomial algorithms in a specialization of the NP-hard OCHP. However, the order on simplices was not specified and one can wonder if choosing such an ordering makes the specialization of OCHP too restrictive for it to be useful. In this section, in the light of the total order defined in Section 6 (Equation 6.9) and its equivalent order for a 2D Delaunay triangulation in Section 7 (Lemma 7.6), we give a concrete example where this restriction makes sense and provides a simple and elegant application to the problem of point cloud triangulation. Whereas algorithms of Sections 3, 4 and 5 only dealt with abstract simplicial complexes, we now consider a bijection between vertices and a set of points in Euclidean space, allowing to compute geometric quantities on simplices.

Related works

Many methods have been proposed to answer the problem of surface reconstruction in specific acquisition contexts [START_REF] Kazhdan | Screened poisson surface reconstruction[END_REF][START_REF] Labatut | Robust and efficient surface reconstruction from range data[END_REF][START_REF] Li | Globfit: consistently fitting primitives by discovering global relations[END_REF]: [START_REF] Berger | State of the art in surface reconstruction from point clouds[END_REF] classifies a large number of these methods according to the assumptions and information used in addition to geometry. In the family of purely geometric reconstruction based on a Delaunay triangulation, one very early contribution is the sculpting algorithm by Boissonnat [9]. The crust algorithm by Amenta et al. [START_REF] Amenta | A new voronoi-based surface reconstruction algorithm[END_REF][START_REF] Amenta | A simple algorithm for homeomorphic surface reconstruction[END_REF] and an algorithm based on natural neighbors by Boissonnat et al. [START_REF] Boissonnat | Smooth surface reconstruction via natural neighbour interpolation of distance functions[END_REF] were the first algorithms to guarantee a triangulation of the manifold under sampling conditions. However, these general approaches usually have difficulties far from these sampling conditions, in applications where point clouds are noisy or under-sampled. This difficulty can be circumvented by providing additional information on the nature of the surface [START_REF] Tamal | Tight cocone: A water-tight surface reconstructor[END_REF][START_REF] Herbert | Surface Reconstruction by Wrapping Finite Sets in Space[END_REF]. Our contribution lies in this category of approaches. We provide some topological information of the surface: a boundary for the open surface reconstruction and an interior region and exterior region for the closed surface reconstruction.

Simplicial ordering

We use the total order on 2-simplices defined in Lemma 7.6 for this section. Indeed, the 2D Delaunay triangulation has some well-known optimality properties, such as maximizing the minimal angle, and we can hope that using the lexicographic order induced by this total order to minimize 2-chains in dimension 3 will keep some of those properties. In fact, Section 9 is devoted to showing that, for a Čech or Vietoris-Rips complex, under strict conditions linking the point set sampling, the parameter of the complex and the reach of the underlying manifold of Euclidean space, the minimal lexicographic chain using the described simplex order is a triangulation of the sampled manifold. Experimental results (Figure 8.1) show that this property remains true relatively far from these theoretical conditions.

Open surface triangulation

Using the Phat library [START_REF] Bauer | Phat -persistent homology algorithms toolbox[END_REF], we generate a Čech complex of the point cloud and the points of a provided cycle, with a sufficient parameter to capture the topology of the object [START_REF] Chazal | A sampling theory for compact sets in euclidean space[END_REF][START_REF] Attali | Vietoris-rips complexes also provide topologically correct reconstructions of sampled shapes[END_REF]. After constructing the 2-boundary, we apply the boundary reduction algorithm, slightly modified to calculate as well the transformation matrix V . We then apply Algorithm 4, and in the case the cycle is a boundary, we get a chain bounded by the provided cycle. We then apply Algorithm 3 to minimize the chain under imposed boundary. Figure 8.2 shows results of this method.

Closed surface triangulation

Using Algorithm 5 requires a strongly connected 3-pseudomanifold: we therefore use a 3D Delaunay triangulation, for its efficiency and non-parametric nature, using the CGAL library [START_REF] Jamin | 3D triangulations[END_REF], and complete it into a 3-sphere by connecting, for any triangle on the convex hull of the Delaunay triangulation, its dual edge to an "infinite" dual vertex. The choice of α 1 and α 2 will define the location of the closed separating surface. We can guide the algorithm by interactively adding multiple α 1 and α 2 regions as depicted in Figure 8.3. Algorithm 5 requires to be slightly modified to take as input multiple α 1 , α 2 : after creating all sets with MakeSet, we need to combine all α 1 sets together, and all α 2 sets together. The algorithm remains unchanged for the rest.

Experimentally, sorting triangles does not require exact predicates: the R B and R C quantities can simply be calculated in fixed precision. The quasilinear complexity of Algorithm 5 makes

Chapter 9

Triangulation of smooth 2-submanifolds of Euclidean space by minimal chains over point samples 9.1 Main result of the section

Fondamental class When M is a connected compact d-manifold (orientability is not required here since the coefficients field is Z 2 ), It is well known that H d (M) is one dimensional and is generated by the so called fundamental class of M, and, since the field is Z 2 , has a single non zero element:

H d (M) Z 2 .
In both contexts of simplicial and singular homology, this fundamental class can be built from a triangulation of M.

In the following, we consider:

Embedded manifold: For n > 2, we denote by M a connected, compact and C 2 smooth embedded 2-manifold M ⊂ R n with reach R > 0.

Sampling set S: S ⊂ M a finite "sampling set" such that for any point x ∈ M there is at least one point in S at distance less than from x, and such that any two points in S are at least η apart, with 0 < η ≤ /2.

Simplicial complex

Let K be the λ-Chech complex of S (in fact the 3-skeleton of the λ-Chech complex is enough since it defines H 2 (K)). It is known [START_REF] Niyogi | Finding the homology of submanifolds with high confidence from random samples[END_REF] that for < 3/5R, K has the homotopy type of M.

Main result

We show that for some constant C 3 > 0 (independent on the ambient dimension n), for any n > 2, and any such M and S such that < C 3 η 10 R , the support of the chain Γ min ∈ C 2 (K, Z/2Z) minimizing the lexicographic order lex in the homology class of the fundamental class of M is a triangulation of M. More precisely, the restriction to |Γ min | of the projection on M is an homeomorphism.

While this is not yet formally proven at this stage, it seems very likely that this minimum coincides with the tangential Delaunay complex [START_REF] Boissonnat | Manifold reconstruction using tangential delaunay complexes[END_REF] when all stars are consistent.

We denote by π M the orthogonal projection on M, in other words the map from M ⊕R • → M that associates to each point its closest point on M. Theorem 9.1. There are constants C 1 , C 1 , C 3 such that: If M is a C 2 manifold embedded in R n with reach R, S a ( , η)-sampling of M and K = Č(S, λ) the Čech complex on S with parameter λ, such that:

1. If:

C 1 < λ < C 2 R (9.1)
then one has β 2 (K) = 1.

Let T be the lexicographic minimal representative of the unique homology class in H 2 (K),

i.e. the lexicographic minimal 2-cycle which is not a boundary:

T = min lex Ker(∂ 2 ) \ im(∂ 3 ) (9.2) If R < C 3 η 10 (9.3) then the restriction of π M to |T | is an homeomorphism on M. In particular (|T |, π M ) is a triangulation of M.
Remark 9.2. Observe that::

• Thanks to Lemma 7.8, it follows that min lex could be replaced by ∞ and therefore, for a any complex K satisfying the condition of the theorem, there exists p large enough such that:

T = arg min Γ∈Ker(∂ 2 )\im(∂ 3 ) Γ (p) (9.4)
• when the theorem holds for a range of Čech complex parameter λ, √ 2λ there is a Rips-Vietoris complex R such that Č(S, λ) ⊂ R ⊂ Č(S, √ 2λ). Under stronger sampling conditions [START_REF] Attali | Vietoris-rips complexes also provide topologically correct reconstructions of sampled shapes[END_REF] this inclusion induces isomorphisms on Homology groups. In this situation one could replace Čech complex by Rips-Vietoris complex in the theorem (one may need Lemma 9.17 for a formal proof, to guarantee that taking larger simplices cannot give a lexicographic smaller representative).

The sequel of the section is devoted to the proof of Theorem 9.1.

Properties of lexicographic minimal homologous 2-chains

In this section T is (implicitly) assumed to be a 2-cycle in a Čech complex Č(S, λ) over a finite set S ⊂ R n which is a lexicographic minimum in its homology class. So for that for K = Č(S, λ) and some cycle A ∈ C 2 (K):

T = min lex {Γ ∈ C 2 (K) | ∃B ∈ C 3 (K) , Γ -A = ∂B}
We establishes some properties on T that does not require any geometric assumption on the set S, in particular S is not assumed to be the sampling of anything at this stage.

Lemma 9.3. If abc ∈ T is an acute triangle, then SEB(abc), the Smallest Enclosing Ball of abc, has no point of S in its interior:

SEB(abc) • ∩ S = ∅
Proof. For a contradiction, assume that T (abc) = 0 and SEB(σ) • ∩S = ∅. Take d ∈ SEB(σ) • ∩ S, then R B (abcd) = R B (abc) ≤ λ and therefore, abd, bcd, cad, abcd ∈ K.

One has R B (abd), R B (bcd), R B (cad) < R B (abc) and then abd + bcd + cad lex abc. Consider:

T = T + abc + abd + bcd + cad = T + ∂(abcd)
Then, T is homologous to T and is strictly lower for lex :

T lex T A contradiction with the definition of T .

B(o, r)

Similarly, if abc is obtuse with longest edge ab we call the the Spindle of edge ab in triangle abc the Spindle of edge ab with radius R C (abc), equivalently:

SP abc (ab) = def. SP R C (abc) (ab) = {x ∈ R n , ∠axb ≥ ∠acb } If r = 1
2 a -b then SP r (ab) = SEB(ab). One check easily that: c ∈ SP abc (ab)

From the definition we have also that for r, r ≥

B(o, R C (abd)) ⊂ SP R C (abd) (ad)⊂B(o,R C (abd)) B(o, R C (abd)) = {a,d}⊂B(o,R C (abd)) B(o, R C (abd)) = SP R C (abd) (ad)
This with (9.7) gives:

c ∈ SP R C (abd) (ad)
a contradiction with Lemma 9.5.

It follows from Lemma 9.7 that:

Corollary 9.8. Any obtuse triangle T 0 ∈ T belongs to at least one sequence T 0 , . . . , T m ∈ T of triangles with increasing bounding radius and circumradius, such that T 0 , . . . , T m-1 are obtuse, T m is acute and for i = 0, . . . , m -1, the longest edge of T i is an edge of T i+1 and if i < m -1 it is not the longest edge of T i+1 . In particular, this sequence is increasing for ≤ ∞ .

Lemma 9.9 below give us an explicit bound on the length of the increasing sequences of Corollary 9.8. Lemma 9.9. In a sequence of increasing triangles defined in Corollary 9.8, one has:

m ≤ R B (T m ) 2 η 2 -1 (9.8)
Proof. In the sequence, if 0 ≤ i ≤ m -1 triangle T i share its longest edge with an edge of triangle T i+1 . Denote the vertices of triangle T i as a i b i c i = T i where a i b i is the longest edge of

T i if 0 ≤ i ≤ m -1.
Since, for i ≤ m -1, T i is obtuse one has for all i = 0, . . . , m -1:

(b i -a i ) 2 > (c i -a i ) 2 + (c i -b i ) 2 (9.9)
Denotes by l i the length of edge a i b i for 0 ≤ i ≤ m -1. Since all edges have length greater or equal than η, one has (c i -a i ) 2 , (c i -b i ) 2 ≥ η 2 and (9.9) gives in particular:

l 2 0 > η 2 + η 2 = 2η 2 and since for i ≥ 1 one of (c i -a i ) 2 , (c i -b i ) 2 is l 2
i-1 (9.9) gives for all i = 1, . . . , m -1:

l 2 i > l 2 i-1 + η 2
The two last equations gives us:

l 2 m-1 > (m + 1)η 2 Since l m-1 ≤ R B (T m
), this proves the lemma.

Where the reach comes into play

Geometry of submanifolds with positive reach

We recall here a few geometric lemma about general set with positive reach as well as on C 2 submanifold of euclidean space. Lemma 9.10 (Lemma 5 in [START_REF] Attali | Geometry-driven collapses for converting a čech complex into a triangulation of a nicely triangulable shape[END_REF]). Let A ⊂ R d be a compact set and B(z, α) a closed ball with center z and radius α.

If 0 ≤ α < Reach (A) and A ∩ B(z, α) = ∅ then Reach (A) ≤ Reach (A ∩ B(z, α)).
Theorem 9.11 (Theorem 1 in [START_REF] Boissonnat | The reach, metric distortion, geodesic convexity and the variation of tangent spaces[END_REF]).

If A ⊂ R d is a closed set, then Reach (A) = sup r > 0, ∀a, b ∈ A, |a -b| < 2r ⇒ d A (a, b) ≤ 2r arcsin |a -b| 2r ,
where the sup over the empty set is 0.

and its corollary:

Corollary 9.12 (Corollary 1 in [START_REF] Boissonnat | The reach, metric distortion, geodesic convexity and the variation of tangent spaces[END_REF]). Let A ⊂ R d be a closed set with positive reach Reach (A) > 0. Then, for any r < Reach (A) and any x ∈ R d , if B(x, r) is the closed ball centered at x with radius r, then A ∩ B(x, r) is geodesically convex in A.

Lemma 9.13 (Corollary 3 in [START_REF] Boissonnat | The reach, metric distortion, geodesic convexity and the variation of tangent spaces[END_REF]). if p, q ∈ M, then sin ∠(T p M, T q M) 2 ≤ p -q 2R Lemma 9.14 (Theorem 4.8 [START_REF] Bauer | Phat -persistent homology algorithms toolbox[END_REF] in [START_REF] Federer | Curvature measures[END_REF]). if p, q ∈ M, then

d(q, T p M) ≤ p -q 2 2R
Local expression of M as the graph of a function In this section we assume, in adition to the assumption made on T ay the begiing of the previous section, that T meets the conditions of Theorem 9.1, in particular S is an ( , η)-sampling of a compact, connected submanifold M of R n with reach R.

D(m, R/4) = {q ∈⊂ Π m , q -m ≤ R/4} C(m, R/2, R/4) = {q ∈ B(m, R/2), π m (q) ∈ D(m, R/4)} = B(m, R/2) ∩ π -1 m (D(m, R/4)) Lemma 9.15. M ∩ C(m, R/2, R/4) is the graph of a map: φ : D(m, R/4) → R n-2
In other words, with the identification R n = R 2 × R n-2 , if we consider an orthogonal frame of R n centered at m and aligned with Π m , we get:

M ∩ C(m, R/2, R/4) = {(u, φ(u)), u ∈ D(m, R/4)} With, for any u ∈ D(m, R/4) φ(u) < 1 R u -m 2 (9.10) ∂φ ∂u (u) < 2 R u -m (9.11)
Proof of Lemma 9.15 is given in Appendix D.

From now on we assume the following bound on Cech parameter λ: λ < R/10. (This bound may certainly be relaxed and the constants in lemmas below improved).

Bounding the triangles circumradii Lemma 9.16. If abc ∈ T is an acute triangle, then R B (abc) < 2

The idea of the proof, given in Appendix D, is that otherwise there would be at least one sampling point not too far from the triangle circumcenter contradicting Lemma 9.3. This bound extends in fact to all triangles in T , more precisely: Lemma 9.17. If abc ∈ T , then

1 √ 3 η < R C (abc) < 2 Proof. If abc is acute, then R C (abc) = R B (
h min (abc) ≥ R C (abc) η R C (abc) 2 ≥ 1 2 η 2 = η 2 2 (9.12)
In any case, the sinus of the smallest angle θ min of triangle abc is lower bounded by: [START_REF] Boissonnat | Geometric and topological inference[END_REF] gives an upper bound on the angle between the supporting plane Π(T ) of a triangle T ∈ T and and Π m the plane tangent to M at m. Expressed in our setting it gives: Lemma 9.19 (Lemma 8.11 in [11] ). if T ∈ K and m is a vertex of T , then

sin θ min > 1 4 η Proof of
sin ∠(Π(T ), T m M) ≤ 2L 2 v h min R
Where L is an upper bound on the triangles edge lengths, so that in our case, thanks to Lemma 9.17 L < 4 and gives, using (10.21) sin

∠(Π(T ), T m M) ≤ 32 2 v h min R ≤ 64 R η 2 (9.13)
Next Lemma synthesizes the geometric bounds constrained by the manifold reach that are used in subsequent proofs.

β 1 = C 2 R = O R and: S ∩ B(m, C ) ⊂ Π(T ) ⊕β 2 (9.15)
with:

β 2 = C 2 1 + 64 η 2 R = O R η 2
Also the angle between Π m and Π(T ) is upper bounded:

∠ Π m , Π(T ) < β (9.16)
And for any triangle abc ∈ T such that {a, b, c} ⊂ B(m, C ) on has:

∠ Π(abc), Π(T ) < 3β (9.17)

with:

β = 64C R η 2 = O R η 2
Proof of Lemma 9.20 is given in Appendix D.

β = 8C R η 2 = O R η 2
Proof. From 9.20 the angle between the plane Π m tangent to M at m and the plane Π(T ) is

β = 4C R η 2 = O R η 2
. Since the distance from m to the circumcenter o T of T is upper bounded by 2 from Lemma 9.17, the distance between the circumcenter of T and the plane tangent to M at m is bounded by 2 sin β which proves the lemma.

Big O notation We use the notation O(f ( R )) and Ω(f ( R )) implicitly means respectively

O(f ( R )) R →0 and Ω(f ( R )) R →0 . More explicitly: g( R ) ∈ O(f ( R
)) if and only if:

∃C, n 0 > 0, ∀n ≥ n 0 , R < 1 n ⇒ g( R ) < Cf ( R )
and

g( R ) ∈ Ω(f ( R
)) if and only if:

∃C, n 0 > 0, ∀n ≥ n 0 , R < 1 n ⇒ g( R ) > Cf ( R )
Functions considered below f and g are in fact of the form:

C R k η l m
C is a true constant: it does not depends on the ambiant dimension or on S or M of course) and each of the three other factors can be seen as independent parameters. One could make things simpler taking R = 1 and maybe = 2η since this is always possible (ε-nets) and the one important parameter for the proof is R for which one allow ourselves to fix an upper bound taken as small as required to make the proof work without fighting for optimizing the constants.

Proof of Lemma 9.24. Let m be a vertex of T 0 . From Lemma 9.20, if ρ < , S ∩ S ∩ B(C C (T 0 ) , ρ + 2 ) is at distance β 1 ∈ O R from plane Π m . From the sampling conditions, balls centered on S with radius η/2 are disjoint. The intersection of these balls with plane Π m are disks with radius lower bounded by:

(η/2) 2 -β 2 1
which is arbitrarily close to η/2, for R small enough. These disks are of course disjoint as well which allows us to use a packing argument: the number of disjoint disks of radius say r included in a disk of radius R is upper bonded by he ratio of the disks area R 2 r 2 . For a set X, (X) denotes the cardinal of X. The packing argument gives us:

(S ∩ B(C C (T 0 ) , ρ + 2 )) < C ρ + 2 η/2 2
Where C is a small constant, say C < 6 1 3 . Since triangles circumradii are bounded by 2 (Lemma 9.17 ), if T ∈ T is such that C C (T ) ∈ B(C C (T 0 ) , ρ) then the vertices of T are in B(C C (T 0 ) , ρ + 2 ). Since N points define less than

1 6 N 3 triangles: {T ∈ T , C C (T ) ∈ B(C C (T 0 ) , ρ)} < ρ + 2 η/2 6
It follows that for ρ < if: Since ρ < , (9.18) is satisfied if:

δ ρ + 2 η/2 6 < ρ -δ (9.
δ < ρ 2 7 η 3 6 < 1 2 7 3 6 η 6 (9.19)
Then taking as in the lemma δ = R 1/2 we get that for R small enough (9.19) is satisfied and: Given a triangle T , V(T ) denotes the set of its 3 vertices.

ρ ≤ δ ρ + 2 η/2 6 < 2 6 3 6 η 6 R 1/2 ∈ O R

Lemma 9.27. For any constant

C > 0, if R is small enough, if T, T ∈ T such that V(T ), V(T ) ⊂ S m,C , if: C C (T ) -C C T > δ = R 1/2 then S(π m (T ), π m (T )) > -β
with: ∀i, j, -2α ≤ P T (s j ) -P T (s j ) -

β ∈ O R
(P T (s i ) -P T (s i )) = (C C (T ) -s j ) 2 -R C (T ) 2 -(C C T -s j ) 2 -R C (T ) 2 -(C C (T ) -s i ) 2 -R C (T ) 2 -(C C T -s i ) 2 -R C (T ) 2 = 2 C C (T ) -C C T , s i -s j This gives: C C (T ) -C C T , s i -s j ≥ -α (9.22)
If we denote π m the projection of vectors in R n on tangent plane to M at m and π ⊥ m the projection on the orthogonal (n -2)-linear space in such a way that for any vector w ∈ R n , π m (w) + π ⊥ m (w) = w. One has:

C C (T ) -C C T , s i -s j = π m C C (T ) -C C T , π m s i -s j + π ⊥ m C C (T ) -C C T , π ⊥ m s i -s j From Lemma 9.21 one has π ⊥ m C C (T ) -C C T ∈ O R η 2
and from Lemma 9.20 one has:

π ⊥ m s i -s j ∈ O R
which makes:

π ⊥ m C C (T ) -C C T , π ⊥ m s i -s j ∈ O R 2 η 2 2 Since R 2 η 2 2 ∈ O R 2 η 10 2
We therefore get from (9.22), with α still obeying the same asymptotic behavior given in (9.21) above:

π m C C (T ) -C C T , π m s i -s j ≥ -α (9.23)
From Lemma 9.21 we know that taking R small enough forces π ⊥ m (C C (T ) -C C (T )) to be arbitrary small with respect to C C (T ) -C C (T ) > δ = R 1/2 , which makes:

π m C C (T ) -C C T ∈ Ω R 1/2 (9.24)
If we define: Lemma 9.28. For R small enough, let T = s 1 , s 2 , s 3 ∈ T and s ∈ M, such that ∀i, s = s i with s, s 1 , s 2 , s 3 ∈ S m,R/2,C then the distance from π m (s) to π m (|T |) is lower bounded by some "constant" distance from T :

y = π m (C C (T ) -C C (T )) π m (C C (T ) -C C (T )) (9.
d(π m (s), π m (|T |)) > 1 64 η 2 ∈ O(1)
Proof. According to Lemma 9.23 , T is α-almost empty with: . We consider the maps π T and π ⊥ T similar to the one introduced in the proof of previous Lemma, with ∀w ∈ R n , π T (w) + π ⊥ T (w) = w where π T is now the projection on the supporting plane Π T of triangle T and vector π ⊥ T (w) in the orthogonal linear n -2-space. π T denote also the affine projection on Π T when applied to points.

α = O R
One has 2 . By sampling conditions, (s i -s) 2 ≥ η 2 and by Lemma 9.20, Therefore on has:

(s i -s) 2 = π T (s i -s) 2 + π ⊥ T (s i -s)
π ⊥ T (s i -s) 2 > 4β 2 2 with β 2 = O R η 2 . It follows that for R small enough: ∀i, π T (s i -s) 2 = (s i -π T (s)) 2 > η 2 /2 (9.26) Since |T | is compact there is a projection of s on |T | denoted p such that p ∈ |T | and d(s, p) = d(s, |T |). If π T (s) ∈ |T |, then p = π T (s). If not, if d(s, |T |) 2 < η 2 /2 then d(π T (s), |T |) 2 < η 2 /
d (s, |T |) = d s, |T | \ i B s i , η 2
The map x → P T (x) is convex and therefore its maximum on |T | \ i B s i , η 2 is reached on the boundary and more precisely on convex corners of the boundary. The boundary of

|T | \ i B s i , η 2 is
(o -c) 2 = h 2 + (d -η/2) 2 With R = R C (T ) = h 2 + d 2 we have: P T (c) = (o -c) 2 -R 2 = -d η + (η/2) 2
And since d ≥ η/2 we get P T (c) ≤ -η 2 /2 + (η/2) 2 = -(η/2) 2 Since x → P T (x) reaches its maximum on a corner such as c one has:

∀x ∈ |T | \ i B s i , η 2 , P T (x) ≤ -(η/2) 2
and this gives:

|T | \ i B s i , η 2 ⊂ B o, R 2 -(η/2)
d(s, |T |) = d s, |T | \ i B s i , η 2 ≥ R 2 -α -R 2 -(η/2) 2 ≥ (η/2) 2 -α /(2R)
Since R ≤ 2 and, for R small enough, α < (η/2) 2 /2, we get:

d(s, |T |) ≥ 1 32 η 2
Now, from Lemma 9.20, d(s, π T (s)) < β 2 and, if d h denote the Hausdorff distance, one get

easily that d h (|T |, π T (|T |)) < β 2 with β 2 = O R η 2
. It follows that for R small enough,

β 2 < 1 128 η 2 which gives: d(π m (s), π m (|T |)) ≥ d(s, |T |) -d(s, π T (s)) -d h (|T |, π T (|T |)) > 1 64 η 2 ∈ O(1)
Lemma 9.29. For R small enough, let T ∈ T , s ∈ M such that V(T ) ⊂ S m,R/2,C . Then any height of triangle π m (T ) is larger than η 2 4 . Any angle of triangle π m (T ) has his sinus larger than η 8 . Proof. Lemma 9.18 gives similar lower bounds for T . Since by Lemma 9.20 the distance between T and the plane Π m is O R , for R small enough this distance become arbitrarily small with respect to the lower bound η on edge lengths. It results that the transformation T → π m (T ) is as close as we want to an isometry. And the lower bounds on angle and heights can be made arbitrarily close to the one for T . It follows in particular that small enough R allows to guarantee lower bounds for π m (T ) twice smaller than the lower bounds on T . Lemma 9.30. For R small enough, for

s ∈ M, let T, T ∈ T such that V(T ), V(T ) ⊂ S m,R/2,C , if π m (T ) • ∩ π m (T ) • = ∅ one has: width π m (T ) ∩ π m (T ) > 2 -10 η 3 Proof. if π m (T ) • ∩ π m (T ) • = ∅ then π m (T ) ∩ π m (T )

is a convex polygon with non empty

interior. There is a disk with positive maximal radius included in π m (T ) ∩ π m (T ). Generically this disk is tangent to three sides of the polygon (for non generic configurations it is enough to consider arbitrarily close generic configurations).

Consider the first case where this three sides belong to the same triangle, say π m (T ) = abc. Since the radius of the incircle of a triangle is ρ(abc) = 2S/(ab + bc + ac) where S is the area of abc, we have that if h is the smallest height of abc, then ρ(abc) ≥ h/3. Since width (π m (T ) ∩ π m (T )) > 2ρ(abc), thanks to Lemma 9.29 we get the result in this case with a lower bound of 2 8 , we have that a, b , ac ≥ η 2 8 . We get therefore that the smallest height of ab c is lower bounded by η 2 8 η 8 . It remains to consider the case where a is not a vertex of π m (T ). It follows that, thanks to Lemma 9.28, d(π m (a), π m (|T |)) > 2 -7 η 2 . Denote by t ab (respectively t ac ) the point where the maximal disk is tangent to ab (respectively ac). Since t ab , t ac ∈ π m (|T |) we get at ab = at ac > 2 -7 η 2 . The radius ρ of the maximal disk is then ρ = at ab tan ∠bac 2 . Since, from Lemma 9.29 one has tan ∠bac 2 ≥ 1 2 sin ∠bac > η 16 , we get:

ρ > 2 -7 η 2 η 16 = 2 -11 η 3
One has width (π m (T ) ∩ π m (T )) ≥ 2ρ and we get the lower bound.

Lemma 9.31. For R small enough, let T, T ∈ T , s ∈ M such that V(T ), V(T ) ⊂ S m,R/2,C .
If T and T are not in the same connected component of G δ for δ = R 1/2 one has:

π m (T ) • ∩ π m (T ) • = ∅ Proof. For a contradiction assume π m (T ) • ∩ π m (T ) • = ∅. From Lemma 9.
β ∈ O R 3/2 η 10
which, for R small enough is smaller than 2 -10 η 3 and then:

S(π m (T ), π m (T )) > -width π m (T ) ∩ π m (T )
which contradicts (9.20). All along this section 9.6 we assume that δ = R 1/2 , as assumed in Lemmas 9.24 and 9.31.

Triangles in

Each connected component of G δ corresponds to a set CC ⊂ T . We consider CC = {T 1 , . . . , T m } a such connected connected component of triangles in G δ . We consider the dual graph in CC, i.e. the graph whose vertices are triangles in CC and two vertices are connected by an edge in the graph if the corresponding triangles share an edge. Connected components (CC j ) j=1,k in this dual graph defines again a partition of CC = j=1,k CC j .

Recall that, for given m ∈ M and C we say that two triangles T, T with vertices in S m,R/2,C overlap if the interior of their projections on plane Π m are not disjoint, i.e. π m (T ) • ∩π m (T ) • = ∅.

In order to prove that, locally, no two triangle's projection on Π m overlap we consider the three alternatives. Lemma 9.31 above says that triangles in separate connected components of G δ do not overlap. Then Lemma 9.39 in section 9.6.4 below states the same property for two triangles in a same connected component CC i of the dual graph over a connected component CC of G δ . Lastly, Lemma 9.40 in section 9.6.5 states the same property for two triangles in a same connected component CC of G δ but in separate connected components CC i , CC j of the dual graph in CC.

A pentagram as counter example

In some sense the problem of proving the manifoldness of the support of the minimal chain is reduced to the simple case of quasicocyclic points. However the simplicity of the configuration do not allow to conclude directly and the minimality condition has to be used further in the argument as is shown by the following counter example: Denote by V 0 , . . . , V 4 the 5 vertices of a pentagon with

V k = e k 5 2πi , k = 0, . . . , 4. Consider the chain τ = V 0 V 1 V 3 + V 1 V 2 V 4 + V 2 V 3 V 0 + V 3 V 4 V 1 + V 4 V 0 V 2 Observes that ∂τ = V 0 V 1 + V 1 V 2 + V 2 V 3 + V 3 V 4 + V 4 V 0
The support of τ is not a valid triangulation of the pentagon, it does not collapse either on a triangulation since it a Moebius strip. Remark: this example does not work with R as field coefficients since it is not orientable (find an orientable counter-example ?).

Some properties of triangles in a same connected component of G δ

Let V be the set of vertices of all triangles in a given connected component CC of G δ . Since circumradii are upper bounded by 2 and since all circumcenters in a connected component of

G δ lie in a ball of radius ρ ∈ O R 1/2 η 6
, by Lemma 9.24.

Moreover we assume that for some m ∈ M and C one has:

V ⊂ S m,R/2,C Lemma 9.32. Let V ⊂ S m,R/2,C be the set of vertices of all triangles in a connected component of G δ , for δ = R 1/2 . There is a circle C 0 ⊂ Π m of radius in [η/2, 2 ] such that any vertex in v ∈ V as well as its projection π m (s) on Π m are at distance less than O R 1/2 η 6 from C 0 .
In other words, if π C0 denote the projection on (i.e. the closest point on) circle C 0 , for any v ∈ V :

v -π C0 (v) ∈ O R 1/2 η 6 π m (v) -π C0 (v) ∈ O R 1/2 η 6
Proof. Call T 0 , . . . , T m-1 the m triangles in the connected component. From Lemma 9.24, all circumradius lies in a ball of radius

ρ ∈ O R 1/2 η 6
It follows that any circumcenter c i of a triangle T i lies at distance less than 2ρ from c 0 . For i = 0 considers a vertex s i of T i . One has:

s i -c 0 ≤ s i -c i + c i -c 0 ≤ s i -c i + 2ρ ≤ R i + 2ρ
Where

R i = R C (T i ).
But on another side from Lemma 9.23 T 0 is α-almost empty with:

α ∈ O R 2 η 10 2
Therefore P T 0 (s) ≥ -α,

s i -c 0 = R 2 0 + P T 0 (s i ) = R 0 1 + P T 0 (s i ) R 2 0 ≥ R 0 1 - α R 2 0 ≥ R 0 -α With: α ∈ O R 2 η 10
. The two last inequalities gives:

R 0 -α ≤ s i -c 0 ≤ R i + 2ρ
It follows that:

R 0 -R i ≤ 2ρ + α ∈ O R 1/2 η 6
Triangle T 0 has been chosen arbitrarily, swapping T 0 and T i and combining the two inequalities gives:

|R 0 -R i | ≤ 2ρ + α ∈ O R 1/2 η 6
So that we have proven that any point in V lies at distance

O R 1/2 η 6
from the sphere of centre c 0 and radius R 0 . From Lemma 9.21, we know that:

c 0 -π m (c 0 ) ≤ β with: β = O R η 2
From Lemma 9.20:

s i ∈ Π ⊕β 2
T 0 with:

β 2 = O R η 2
The statement of the Lemma follows with the circle C 0 ⊂ Π m with center π m (c 0 ) and radius R 0 .

In the remaining of this section, following the notation introduced in the proof of Lemma 9.32, we consider a connected component CC = {T 0 , . . . , T m-1 } of G δ whose triangles are sharing a set of vertex V = ∪ i T i (in this notation we see a triangle as a set of three points T = {a, b, c}). We denote by C 0 the circle introduced in Lemma 9.32 which is the circumcircle of T 0 . For any s ∈ V we denote by π C 0 (s) its projection on C 0 , i.e. the closest point of s on C 0 .

Inequalities on π C 0 (V ) In this section we states inequalities satisfied by vertices in π C 0 (V ), as π C 0 (V ) is used below as an approximation (Lemma 9.32) of V and π m (V ). Lemma 9.33. For R small enough the vertices in π C 0 (V ) satisfies the following properties.

(a) For any a, b ∈ V, a = b: π C 0 (a) -π C 0 (b) ≥ η 2 (b) For a, b, c ∈ V such that either π C 0 (ab) is a diameter of C 0 , either π C 0 (ab) is not a diameter of C 0 but π C 0 (c) is on the smallest of the two arcs of circle of C 0 \ {π C 0 (a), π C 0 (b)}, then one has: π C 0 (a) -π C 0 (c) , π C 0 (b) -π C 0 (c) < π C 0 (a) -π C 0 (b) - 1 144 η 3 (c) If a, b, c ∈ V and bc is not the longest edge of abc, then π C 0 (bc) is not a diameter of C 0 and π C 0 (a) is on the longest of the two arcs of circle of C 0 \ {π C 0 (b), π C 0 (c)}and: π C 0 (b) -π C 0 (c) ≤ 2R 0 - 1 4096 η 3 (d) If a, b, c ∈ V and bc is not the longest edge of abc, then if d ∈ V is such that π C 0 (d) is not on the same arc of circle of C 0 \ {π C 0 (b), π C 0 (c)} than π C 0 (a), then: π C 0 (c) -π C 0 (d) , π C 0 (b) -π C 0 (d) ≤ π C 0 (b) -π C 0 (c) - 1 144
η 3
Proof. One has by sampling hypothesis that a -b ≥ η. By Lemma 9.32 we have π C 0 (a)π C 0 (b) ≥ η 2 for R small enough and (a) is proved. Under the assumptions of (b) one has (π

C 0 (a) -π C 0 (c)) 2 < (π C 0 (a) -π C 0 (b)) 2 -(π C 0 (b) -π C 0 (c)) 2 . From (a) we know that (π C 0 (b) -π C 0 (c)) 2 ≤ η 2
4 and from Lemma 9.17 we know that a-b < 2 , which gives for R small enough by Lemma 9.32 π C 0 (a) -π C 0 (b) < 3 . We get:

(π C 0 (a) -π C 0 (c)) 2 < (π C 0 (a) -π C 0 (b)) 2 1 - η 2 36 2
and then:

π C 0 (a) -π C 0 (c) < π C 0 (a) -π C 0 (b) 1 - η 2 36 2 ≤ π C 0 (a) -π C 0 (b) 1 - η 2 72 2 And since π C 0 (a) -π C 0 (b) > η/2 one gets (b).
In the context of (c), without loss of generality assume that ab is the longest edge of abc. If π C 0 (bc) was a diameter of C 0 , or if it was not but with a on the shortest of the two arcs of circle of

C 0 \{π C 0 (b), π C 0 (c)}, one could apply (b) to get π C 0 (a)-π C 0 (b) < π C 0 (c)-π C 0 (b) -1 144 η 3
which, for R small enough, contradicts the fact that ab > bc.

On another hand a short computation shows that if

π C 0 (b) -π C 0 (c) > 2R 0 -1 4096 η 3
then he distance between π C 0 (c) and the point π C 0 (b) opposite to π C 0 (b) on circle C 0 is less than η/8. It follows from (a) that π C 0 (a) is at distance at least 3η/8 from π C 0 (b) and, for R small enough, this would contradicts ab > bc.

In the context of (d), by (c), π C 0 (bc) is not a diameter of C 0 and π C 0 (d) is on the shortest arc of circle of C 0 \ {π C 0 (b), π C 0 (c)}. Then applying (b) gives the required inequality for (d).

Properties on π m (V ) Lemma 9.34. For R small enough the vertices in π v (V ) and triangles in CC satisfy the following properties.

(a) For a given oriented frame in Π m , if a, b, c ∈ V , π m (abc) and π C 0 (abc) have consistent orientation (and are not flat).

(b) Vertices of π m (V ) are in strict convex position.

(c) For T 1 , T 2 ∈ CC one has

π m (T 1 ) • ∩ π m (T 2 ) • = ∅ ⇐⇒ π C 0 (T 1 ) • ∩ π C 0 (T 2 ) • = ∅ Proof.
Points in π C 0 (V ) are on circle C 0 with radius R 0 ≤ 2 and their mutual distances are lower bounded by η/2 by Lemma 9.33(a). Therefore for any triples of points

v 1 , v 2 , v 3 ∈ π C 0 (V ) , η 3 16 is a lower bound on the norm of determinant |det (π C 0 (v 2 ) -π C 0 (v 1 ), π C 0 (v 3 ) -π C 0 (v 1 ))|. By Lemma 9.32 we get that for R small enough then det (π C 0 (v 2 ) -π C 0 (v 1 ), π C 0 (v 3 ) -π C 0 (v 1 )) and det (π m (v 2 ) -π m (v 1 ), π m (v 3 ) -π m (v 1
)) are non zero and have same sign. This gives (a). But properties (b) and(c) relie entirely on the signe of such determinants: since π C 0 (V ) is on a circle it is obviously in convex position and so is π m (V ) which gives (b). Similarly the equality of determinant signs implies (c).

Triangles in a same connected component CC i of the dual graph

By Lemma 9.34, if we chose an orientation of plane Π m this defines an orientation of circle C 0 and a cyclic corresponding cyclic order on he vertices π C 0 (V ) and π m (V ) which From Lemma 9.34(b) we know that vertices in π m (V ) are in convex position.

Denote by V CC i the set of vertices of triangles in CC i . We call convex boundary edge of CC i an edge connecting two vertices of V CC i which are successive in the cyclic order, equivalently an edge of CH(π m (V )), where CH(X) denotes the convex hull of X. Lemma 9.35. If an edge ab of a triangle in CC i is shared by a triangle not in CC i then ab is a convex boundary edge.

Proof. If ab is shared by a triangle not in CC i then, by definition of CC i it is shared by a triangle not in CC. For a contradiction assume that there are vertices c and d on opposite side of ab in triangles of CC i . By Lemma 9.34, since the vertices π m (V CC i ) are in convex position and CH(π m (V CC i \ [π m (a), π m (b)] has two connected components containing respectively π m (c) and π m (d). A path γ in the union of closed triangle (convex hulls of) from c to d, such that γ((0, 1)) remains in the interior of the union, of triangles in CC i will project on Π m on a path π m • γ that will cross the relative interior of π m (ab). But since there is a triangle not in CC that shares edge ab we get a contradiction with Lemma 9.31.

Observes that since T is minimum, any 2-chain σ with vertices in V must be the minimum chain with boundary ∂σ. Indeed the restriction K V of K to V contains all possible tetrahedra because V is contained in a ball of radius smaller than λ and has trivial homology. It follows that ∂σ = ∂σ if and only there is a

3-chain α ∈ C 3 (K V ) such that σ -σ = ∂α.
Also one has a direct consequence of Lemma 9.35: Lemma 9.36. If σ is the chain corresponding to CC i , the edges in ∂σ are precisely the convex boundary edges of CC i .

Proof. If an edge is in ∂σ is must be shared by a triangle not in CC i and therefore , from Lemma 9.35 it is a convex boundary edge. The set of convex boundary edges is a topological circle. Since ∂σ is a cycle (i.e. ∂∂σ = 0) and ∂σ cannot be 0 (if it was σ could be removed from T and contradict the minimality of T ) it must cover the whole circle.

Lemma 9.37. (for R small enough), If ab is the longest edge of all triangles in CC i it can not be shared by two folded triangles of CC i .

Proof. Let ab be the longest edge of all triangles in CC i and assume for a contradiction that abc, abd ∈ CC i are folded along ab.Without loss of generality, we assume that a, c, d, b are ordered according to the cyclic order. By assumption we have bc < ab. We are in the situation of Lemma 9.33(c). From Lemma 9.32 we get that for R small enough O R 1/2 η 6 will be smaller than 1 4 1 256 η 3 and therefore we get by triangle inequality dc, bd < bc and bcd is obtuse with longest edge bc. It results that bcd < ∞ abd. Similarly, one has adc < ∞ abc. But (abc + abd) -(adc + bdc) = ∂abcd with abcd ∈ K since λ > 3 and adc + bdc ∞ abc + abd contradicts the minimality of T . Lemma 9.38. If bc is the not the longest edge of a triangle abc ∈ CC i and is not a convex boundary edge of V CC i , then the vertex v ∈ V CC i \ {b, c} that minimizes abv for ≤ ∞ order is obtuse with largest edge bc and π C 0 (v) is on the smallest of the two arcs of circle of

C 0 \ {π C 0 (b), π C 0 (c)}, Proof. Takes v 1 ∈ V CC i \ {b, c} such that π C 0 (v 1 ) is on the smallest of the two arcs of circle of C 0 \ {π C 0 (b), π C 0 (c)}. Then π C 0 (b)π C 0 (c)π C 0 (v 1 ) is obtuse with longest edge π C 0 (b), π C 0 (c) and, according to Lemma 9.33(c): R B (π C 0 (b)π C 0 (c)π C 0 (v 1 )) = 1 2 π C 0 (b) -π C 0 (c) < R 0 - 1 8192 η 3 (9.28)
where R 0 is the radius of

C 0 . Consider now v 2 ∈ V CC i \ {b, c} such that π C 0 (v 2 ) is not on the smallest of the two arcs of circle of C 0 \ {π C 0 (b), π C 0 (c)}. If π C 0 (b)π C 0 (c)π C 0 (v 2 ) is acute then R B (π C 0 (b)π C 0 (c)π C 0 (v 2 )) = R 0 (9.29)
We know from Lemma 9.32 that the distance between points in V CC i and their projection on

C 0 is in O R 1/2 η 6
and therefore, for for R small enough, applying triangle inequality on (9.28) and (9.29) gives R B (bcv

1 ) < R B (bcv 2 ) and therefore bcv 1 ≤ ∞ bcv 2 . If π C 0 (b)π C 0 (c)π C 0 (v 2 ) is obtuse then π C 0 (b)π C 0 (c) cannot be its longest edge, since then π C 0 (v 2 ) would be on the smallest of the two arcs of circle of C 0 \ {π C 0 (b), π C 0 (c)}. Assume now without loss of generality that π C 0 (a)π C 0 (v 2 ) is the longest edge. Applying Lemma 9.33(b) we get again, for R small enough, R B (bcv 1 ) < R B (bcv 2 ) and bcv 1 ≤ ∞ bcv 2 .
Lemma 9.39. Assume that for some m ∈ M and C > 0 one has V ⊂ S m,R/2,C . The algorithm 6 below computes the chain σ with support CC i . In the result of the algorithm no pair of triangles in CC i overlap:

∀T, T ∈ CC i , T = T , π m (T ) • ∩ π m (T ) • = ∅
Of course the algorithm is purely conceptual, since one assume an oracle giving us the initialization, (which would be easy if one already had the solution).

proof of Lemma 9.39. Since there are no possible ambiguities from the context, we denote by σ = CC i both the set of triangles and the corresponding chain. Similarly τ designate both the Let ab be the longest edge of CC i and V CC i the set of vertices of triangles in CC i .

τ ←τ init = triangles in CC i sharing ab while (∂ τ ∂σ) cd ← longest edge in ∂ τ \ ∂σ e ∈ V CC i such that ∀v ∈ V CC i , cde ≤ ∞ cdv τ ← τ + cde
variable of algorithm 6 seen as a set of triangles and the corresponding chain. From Lemma 9.36 we know that ∂σ is the set of convex boundary edges of V CC i .

Observes that from Lemma 9.37, if ab is a convex boundary edge it is shared by exactly one triangle in CC i and if not it is shared by exactly two opposite triangles in CC i . In the first case the initialization τ init has cardinal τ init = 1 and in the second case to τ init = 2 Denote τ 0 = τ init and τ i the value of variable τ at iteration i.

We want to prove that at each iteration τ i lex σ and that the algorithm stop at iteration m with τ m ≤ σ and ∂τ m = ∂σ which gives τ m = σ by minimality of σ.

We claim by induction that ∂τ i is the set of convex boundary edge on the set V τ i . Indeed it is true at initialization by Lemma 9.37. At each iteration a new vertex is inserted in ∂τ i to produce ∂τ i+1 , and from Lemma 9.38 we get that it is inserted along the cyclic order defined by C 0 . Also, at each step, the longest edge in ∂τ i is replaced by two strictly shorter ones (Lemma 9.33(b) together with Lemma 9.32 shows that this is true for R small enough). Since, after initialization, triangles added at each step of the algorithm are obtuse by Lemma 9.38 with longest edge being the one from which they have been built, we get that triangles added along the execution of the algorithm are decreasing along ≤ ∞ ordering.

We claim by induction that we have τ i lex σ. Indeed, at initialization one has τ init ⊂ σ and therefore τ init lex σ.

At step i, if τ i ⊂ σ, since the edge cd selected by the algorithm is in ∂τ i \ ∂σ there must be at least one triangle T in σ \ τ i with cd as boundary. Two things may happen. Either T = cde is the triangle picked by the algorithm and one get inductively τ i+1 ⊂ σ and obviously τ i+1 lex σ in which case we reproduce the same situation. Either T = cde which, by the choice of vertex e means cde < ∞ T and since the triangles are added along the algorithm in decreasing order the chain τ i will remain strictly smaller in lexicographic order than σ at each iteration.

If ∂ τ ⊆ ∂σ, the program stop and we claim that τ = σ. Indeed, since ∂ τ ⊆ ∂σ and from Lemma 9.36, edges in ∂ τ are convex boundary edges and as in the proof of Lemma 9.36, ∂ τ is a non zero cycle in topological circle and therefore ∂ τ = ∂σ. Since by induction hypothesis τ lex σ and since σ is minimal under the constraint ∂x = ∂σ we get τ = σ.

The fact that no pair of triangles in τ = σ overlap follows Lemma 9.34(c) and the fact that at each step of the algorithm:

π C 0 (∪τ ) = π C 0 T ∈τ π C 0 (T )
is a convex polygon with vertices on C 0 and at each step a triangle T is added to τ its projection interior π C 0 (T ) is disjoint with π C 0 (∪τ ).

Triangles in a same

π m (T 1 ) • ∩ π m (T 2 ) • = ∅
Proof. From Lemma 9.34(c) we know that for two triangles T 1 ∈ CC i and T 2 ∈ CC j one has

π m (T 1 ) • ∩ π m (T 2 ) • = ∅ ⇐⇒ π C 0 (T 1 ) • ∩ π C 0 (T 2 ) • = ∅ If π m (T 1 ) • ∩ π m (T 2 ) • = ∅,
We proceed as in the proof of Lemma 9.35. Since triangles in CC i and CC j do not share any edges and since both π m (∪ T ∈CC i T ) and π m (∪ T ∈CC j T ) are convex polygons (Lemma 9.34(b)), There must be an edge π m (ab) boundary of π m (∪ T ∈CC i T ) whose relative interior intersects the interior of π m (∪ T ∈CC j T ) or the reverse. Indeed, if no boundary edge of π m (∪ T ∈CC i T ) has its relative interior intersecting the interior of π m (∪ T ∈CC j T ), then if p is a point in the relative interior of an edge π m (ab) boundary of π m (∪ T ∈CC i T ) it cannot be on the boundary of π m (∪ T ∈CC j T ) (we know that π m (∪ T ∈CC i T ) and π m (∪ T ∈CC j T ) have no boundary edges in common) and is therefore outside

π m (∪ T ∈CC j T ). Then if q ∈ π m (T 1 ) • ∩ π m (T 2 ) • the segment [pq] should cut the boundary of π m (∪ T ∈CC j T ).
But since there is a triangle not in CC that shares edge ab we get a contradiction with Lemma 9.31.

Proof of Theorem 9.1

As a consequence of Lemmas 9.31, 9.39 and 9.40 we get: Lemma 9.41. For given C and for R small enough, if T 1 , T 2 ∈ T have vertices in S m,R/2,C , then :

π m (T 1 ) • ∩ π m (T 2 ) • = ∅
From 9.17 we have L < 4 . So that taking C > 4 × 2.8 in Lemma 9.41, with our sampling conditions and Lemmas 9.17 and 9.18 we can check that the conditions of Theorem 4 in [START_REF] Boissonnat | Local conditions for triangulating submanifolds of euclidean space[END_REF] are met.

Chapter 10

Appendices

A Proof of Proposition 6.13

Proof. Note that Γ reg is unique under the assumed general position.

Since, in the regular triangulation, all (n -1)-simplices that are not on the boundary of CH(P) are shared by exactly two n-simplices, while only those in β P have a single n-coface, we have:

∂Γ reg = β P
We claim now that :

∂Γ = β P ⇒ Γ reg (p) ≤ Γ (p) (10.1)
Indeed, (6.13) and (6. From the equivalence between regular triangulations and convex hull on lifted points we know that if σ reg ∈ Γ reg , then for any n-simplex in σ ∈ K :

x ∈ |σ| ∩ |σ reg | ⇒ δ σreg (x) ≤ δ σ (x) (10.3)
According to Lemma 10.1, in (10.2), there is an odd number of, and therefore at least one, simplex σ ∈ Γ satisfying |σ| x in the condition on the sum. Therefore (10.3) gives:

x ∈ |σ reg | ⇒ δ σreg (x) p ≤ σ∈Γ |σ| x δ σ (x) p (10.4)
And, since, from definition of triangulation, for x ∈ CH(P) \ |K n-1 P | there is exactly one simplex σ reg such that |σ reg | x , (10.4) can be rewritten as: Proof. We claim that since x ∈ CH(P) \ |K n-1 P | there is x ∈ R n \ CH(P) such that:

[x x] ∩ |K n-2 P | = ∅ (10.6)
where [x x] denote the line segment in R n between x and x. Indeed, we consider moving a point x t from x 0 to some x 1 , picking x 0 , x 1 far away enough to have [x 0 x 1 ] ∩ CH(P) = ∅ and in such a way that [x 0 x 1 ] belongs to none of the affine hyperplanes spanned by (n -1)-simplices in K P ), which occurs generically. Then, the negation of condition (10.6) with x = x t , occurs only as isolated values of t. We can pick a value t for which is does not occur: set x = x t and the claim is proved. | Next, we navigate a point y( t Then when crossing any other (n -1)-simplex τ i / ∈ |β P |, at some point y(t i ), the condition ∂Γ = β P requires the number n i of n-simplices in |Γ| coface of τ i to be even. When crossing |τ i |, along [x x], point y(t i ) exits k -, and enters k + n-simplices in |Γ|, with k -+ k + = n i . The current number of covering n-simplices value is incremented by k + -k -. Since n i is even and:

k + -k -= k + + k --2k -= n i -2k - k + -k -is

B Proof of Lemma 7.3

We need a preliminary definition and lemma.

φ(u) p = 1 0 D φ (t)(1 -t) p dt
Moreover if there is β > 0 such that D φ is defined and continuous on (0, β) with:

∀t ∈ (0, β), D φ (t) > 0
Then, for any given α > 0, (with α ≤ 1):

lim p→∞ α 0 D φ (t)(1 -t) p dt D φ(u) p = 1
Proof. Since, in the interval [0, 1], the derivative of the map s → s p is upper bounded by p, one has:

∀a, b ∈ [0, 1], |a p -b p | ≤ p|b -a|
In particular, for a positive integer k:

∀a ∈ [0, 1], a p - 1 k ka p ≤ p k
For a compact set D ⊂ R d and a continuous function φ : D → [0, 1] one has therefore:

D φ(u) p - D 1 k kφ(u) p ≤ p k µ L (D) Since: D 1 k kφ(u) p = k-1 i=0 D φ i + 1 k -D φ i k 1 - i k p
Using the Riemann integrability of t → p(1 -t) p-1 D φ (t), we get:

D φ(u) p = lim k→∞ k-1 i=0 D φ i + 1 k -D φ i k 1 - i k p = lim k→∞ k-1 i=1 1 - i -1 k p -1 - i k p D φ i k = 1 0 -D φ (t)p(1 -t) p-1 dt = [-D φ (t)(1 -t) p ] 1 0 + 1 0 D φ (t)(1 -t) p dt = 1 0 D φ (t)(1 -t) p dt (10.7)
For the second part of the lemma, one has:

D φ(u) p α 0 D φ (t)(1 -t) p dt = 1 0 D φ (t)(1 -t) p dt α 0 D φ (t)(1 -t) p dt = 1 + 1 α D φ (t)(1 -t) p dt α 0 D φ (t)(1 -t) p dt
Since D φ is increasing and K-Lipschitz for some constant K, one has D φ (t) ∈ [0, K] whenever it is defined which gives:

1 α D φ (t)(1 -t) p dt ≤ K(1 -α) p
and:

α 0 D φ (t)(1 -t) p dt ≥ α/2 0 D φ (t)(1 -t) p dt ≥ A(1 -α/2) p with: A = α/2 0 D φ (t)dt
Since there is β > 0 such that D φ is defined and continuous on (0, β) with ∀t ∈ (0, β), D φ (t) > 0 we have A > 0 and:

D φ(u) p α 0 D φ (t)(1 -t) p dt -1 ≤ K(1 -α) p A(1 -α/2) p = K A 1 -α 1 -α/2 p
Proof of Lemma 7.3. Applying a scale factor λ to a triangle abc would multiply both its area and the function x → L x 0 (x)-(x-x 0 ) 2 by a ratio λ 2 . Therefore w p (abc) p = abc L x 0 (x) -(x -x 0 ) 2 p dx would by multiplied by λ 2+2p . Therefore, without loss of generality, and for the clarity of the equations, one assume in the sequel of the proof that: R B (abc) = 1

Consider then σ = abc with R B (abc) = 1. We introduce the coordinates system:

ξ abc : Π abc → R 2 q → (x q , y q ) = ξ abc (q)
defined by an orthogonal and normed frame of the supporting plane Π abc of abc centered at circumcenter of C C (abc) and such that x a = x b = h and x c > h. In the case abc is not strictly acute, ab is assumed (w.l.o.g.) to be the longest edge of triangle abc. One consider the map: φ σ : R 2 → R:

φ σ (x, y) = L (0,0) ((x, y)) -((x, y) -(0, 0)) 2 = R C (abc) 2 -x 2 -y 2
Motivated by:

w p (σ) p = |σ| φ σ (x, y) p dxdy
In this frame, if abc is strictly acute, then R C (abc) = 1, h < 0 and (0, 0) is in the interior of abc and therefore there is α > 0 small enough such that: Now if abc is right, one has R C (abc) = 1 and h = 0. There is α > 0 small enough such that: In any case (acute, right or obtuse), the map D φσ is Lipschitz with Lipschitz constant π since for 0 ≤ t < t + u ≤ 1:

∀t ∈ [0, α], φ -1 σ ([1 -t, 1]) = {(x,
∀t ∈ [0, α], φ -1 σ ([1 -t, 1]) = {(x, y), x 2 + y 2 ≤ t and x ≥ 0}
0 ≤ D φσ (t + u) -D φσ (t) ≤ µ L (x, y) ∈ R 2 , h 2 + t ≤ x 2 + y 2 ≤ h 2 + t + u} ≤ πu
Therefore, Lemma 10.3 apply and one can estimate w p (σ) p . If abc is acute, then 10.8 gives:

lim p→∞ α 0 π(1 -t) p dt D φ(u) p = 1 Since: α 0 (1 -t) p dt = 1 -(1 -α) p p + 1
we get:

σ strictly acute triangle ⇒ lim p→∞ w p (σ) p π/p = 1 (10.10)

Similarly, using equation 10.9 we get:

σ right triangle ⇒ lim p→∞ w p (σ) p π/(2p) = 1 (10.11)
Now, if abc is strictly obtuse one has h > 0, R C (abc) > 1 and h 2 = R C (abc) 2 -1. There is α > 0 small enough such that :

∀t ∈ [0, α], φ -1 σ ([1 -t, 1]) = {(x, y), x 2 + y 2 ≤ h 2 + t and x ≥ h}
∀t ∈ [0, α], D φσ (t) = (h 2 + t)   π 2 -arcsin h 2 h 2 + t   - √ h 2 t
and then: = 1 and applying an integration by part to compute

σ strictly obuse triangle ⇒ ∀t ∈ [0, α], D φσ (t) =
√ α/h 0 (1 -h 2 u 2 ) p
∀σ 1 , σ 2 ∈ Γ, σ 1 = σ 2 ⇐⇒ R B (σ 1 ) = R B (σ 2 )
It follows that the order ≤ ∞ coincide with the order on bounding radius:

∀σ 1 , σ 2 ∈ Γ, σ 1 ≤ ∞ σ 2 ⇐⇒ R B (σ 1 ) ≤ R B (σ 2 ) Now consider Γ 1 , Γ 2 ∈ D with Γ 1 = Γ 2 and Γ 1 lex Γ 2 .
According to definition 2.1, this means that:

σ max = max ≤∞ {σ ∈ Γ 1 + Γ 2 } ∈ Γ 2 \ Γ 1
If we denote by Γ + the chain made of all simplices in Γ 2 (or equivalently in Γ 1 ) greater than σ max we can write:

Γ 1 = Γ + + Γ 1- Γ 2 = Γ + + Γ 2-
where all triangles in Γ 1-or Γ 2-are strictly smaller than any triangles in Γ + . According to Definition 7.2, one has:

Γ 1 ∞ Γ 2 ⇐⇒ def. ∃p ∈ [1, ∞), ∀p ∈ [p, ∞), Γ 1 p ≤ Γ 2 p
and for all q ∈ [1, ∞):

Γ 1 q ≤ Γ 2 q ⇐⇒ Γ 1 q q ≤ Γ 2 q q ⇐⇒ σ∈Γ 1 w q (σ) q ≤ σ∈Γ 2 w q (σ) q ⇐⇒ σ∈Γ 1- w q (σ) q ≤ σ∈Γ 2-
w q (σ) q (10.14)

If Γ 1-= 0 we have then trivially Γ 1 ∞ Γ 2 . Now if Γ 1-= 0 denote by σ 1-,max the maximal simplex in Γ 1-and by n 1 the number of simplices in Γ 1-. Since σ 1-,max < ∞ σ max we must consider two possible situations:

1. R B (σ 1-,max ) < R B (σ max ), 2. R B (σ 1-,max ) = R B (σ max ) and R C (σ 1-,max ) > R C (σ max ).
Using the notation of Lemma 7.3, we introduce At fixed R B (σ 1-,max ), independently of the nature of the triangle, we can bound w p (σ 1-,max ) by the acute triangle expression for p large enough:

ω 1 (p) = max
w p (σ 1-,max ) p ≤ π p R B (σ 1-,max ) 2+2p ω 1 (p)
We have therefore:

σ∈Γ 1- w p (σ) p ≤ n 1 π p R B (σ 1-,max ) 2+2p ω 1 (p) (10.16)
We can as well lower bound w p (σ max ) p . There exists a constant C such that, for p large enough:

C p 2 R B (σ max ) 2+2p ω σmax (p) ≤ w p (σ max ) p
We have therefore, for p large enough:

C p 2 R B (σ max ) 2+2p ω σmax (p) ≤ σ∈Γ 2-
w p (σ) p (10.17)

Since R B (σ 1-,max ) < R B (σ max ) and lim p→∞ ω σmax (p)/ω 1 (p) = 1, there exist a p large enough to hold true Equations (10.16) and (10.17) , which gives us: Two generic triangle configurations can verify this case: both triangles are obtuse or σ max is strictly acute and σ 1-,max is obtuse. If both σ 1-,max and σ max are obtuse, we have:

∃p ∈ [1, ∞), ∀p ∈ [p, ∞), σ∈Γ 1- w p (σ) p ≤ σ∈Γ 2-
h 2 (σ 1-,max ) ≥ h 2 (σ max ) with: h 2 (abc) = R C (abc) 2 -R B (abc) 2 R B (abc) 2
Therefore, using Lemma 7.3, w p (σ 1-,max ) p ≤ w p (σ max ) p . The same is true for σ max strictly acute and σ 1-,max obtuse, as for a p large enough:

1 h 2 1 p 2 R B (σ 1-,max ) 2+2p ω σ 1-,max (p) ≤ π 1 p R B (σ max ) 2+2p ω σmax (p)
In both cases,

σ∈Γ 1- w p (σ) p ≤ n 1 w p (σ 1-,max ) p ω 1 (p) ω σmax (p) w p (σ max ) p ≤ σ∈Γ 2- w p (σ) p
and therefore Γ 1 ∞ Γ 2 with (10.14).

We have shown that for Γ

1 , Γ 2 ∈ D , Γ 1 lex Γ 2 ⇒ Γ 1 ∞ Γ 2 Since lex is a total order, if Γ 1 = Γ 2 : ¬ (Γ 1 lex Γ 2 ) ⇒ Γ 2 lex Γ 1 ⇒ Γ 2 ∞ Γ 1 ⇒ ¬ (Γ 1 ∞ Γ 2 )
whose contraposition gives us the reverse inclusion:

Γ 1 ∞ Γ 2 ⇒ Γ 1 lex Γ 2

D Proof of Lemmas of section 9.3

Proof of Lemma 9.15. First, we claim that the restriction to M ∩ B(m, R/2) ∩ π -1 m (D(m, R/4)) of the projection π m is surjective onto D(m, R/4).

Indeed consider a point q on the relative boundary of M ∩ C(m, R/2, R/4) in M. q belongs to the boundary ∂ ( C(m, R/2, R/4)) of C(m, R/2, R/4)). But since q ∈ B(m, R/2), we know from lemma 9.14 that:

d(q, T m M) ≤ R/8 Since: ∂B(m, R/2) ∩ π -1 m (D(m, R/4) ∩ T m M ⊕R/8 = ∅ where T m M ⊕R/8 is the R/8 offset of the tangent plane T m M. It follows that q ∈ ∂ C(m, R/2, R/4)∩ T m M ⊕R/8 cannot be in ∂B(m, R/2), therefore one has: π m (q) ∈ ∂D(m, R/4) Now if q ∈ M ∩ C(m, R/2, R/4), Lemma 9.13 gives: sin ∠(T q M, T m M) 2 ≤ 1 4
So that ∠(T q M, T m M) ≤ 2 arcsin 1 4 . This angle is always below π/2, which implies that the restriction to M∩ C(m, R/2, R/4) of the projection π m has a full rank derivative and is therefore an open map.

So that the boundary of π m (M ∩ C(m, R/2, R/4)) can only be on ∂D(m, R/4)). It follows that since m is in the image of M ∩ C(m, R/2, R/4) this image has to be the whole set D(m, R/4). Put differently, the image is a relatively open and compact, non empty subset of the connected set D(m, R/4): it must be the whole set D(m, R/4) and the first claim is proven.

Second we claim that the restriction to M∩ C(m, R/2, R/4) of the projection π m is injective. Indeed assume for a contradiction that q, q ∈ M ∩ C(m, R/2, R/4) with π(q) = π(q ). Thanks to Lemma 9.10, the reach of M ∩ B(m, R/2) is not larger than R. Thanks to Corollary 9.12, the shortest path between q and q in M ∩ B(m, R/2) remains in any ball of radius r < R containing q and q . It follows that this shortest path γ remains in the spindle SP r (q, q ): γ ⊂ M ∩ SP r (q, q ) (10.18)

However, in a neighborhood of q the intersection of the tangent cone (i.e. the set of tangent vectors as defined in Definition 4.3 in [START_REF] Federer | Curvature measures[END_REF]) to M at q, i.e. T q M, and the tangent cone to SP r (q, q ) at q, i.e. a cone centered on the direction qq , orthogonal to T q M, with apex halfangle θ = arcsin 2r q -q < π/2, contains only 0 so that q is an isolated point in M ∩ SP r (q, q ), a contradiction with (10.18).

Since the restriction to M ∩ C(m, R/2, R/4) of the projection π m is a bijection, one can define the map φ of the lemma. Then Lemmas 9.13 and 9.14 give (9.10) and (9.11) after a short computation.

Proof of Lemma 9.16. Let o = C C (abc) be the circumcenter of abc. We claim that there exists a point o ∈ M such that:

o -o ≤ 5 R B (abc) 2 /R (10.19)
Indeed since R B (abc) < λ < R/10, and

a -b , a -c ≤ 2 R B (abc) < R/5
we have b, c ∈ M ∩ C(a, R/2, R/4) and therefore one can apply Lemma 9.15 for m = a. Consider an orthogonal frame of R n centered at a and aligned with Π a , i.e. for which the two first basis vectors are in the linear space associated to Π a . any x of R n is the sum of a point in tangent plane Π a and a vector in the n -2 dimensional linear space Π ⊥ a orthogonal to Π a . Denotes by F a : R 2 × R n-2 → R n the map that assign to the (u, v) ∈ R 2 × R n-2 = R n the corresponding point on the orthogonal frame.

One has a = F a (0, 0) and there are u

b , u c ∈ D(0, R/2) such that b = F a (u b , φ(u b )) and c = F a (u c , φ(u c )) with φ(u b ) ≤ u b 2 /R ≤ 4 R B (abc) 2 /R. Similarly φ(u c ) ≤ 4 R B (abc) 2 /R. Since abc is acute, o belongs to its convex hull: o ∈ |abc| and therefore we have o = F a (u o , v o ) with u o ∈ D(0, R/2) and v o ≤ 4 R B (abc) 2 /R. Take o = F a (u o , φ(u o )) ∈ M. Since u o ≤ a -o = R C (abc) = R B (abc), we have by Lemma 9.15 φ(u o ) < R B (abc) 2 /R and: o -o = φ(u o ) -v o ≤ φ(u o ) + v o ≤ 5 R B (abc) 2 /R
which proves the claim.

Since, thanks to lemma 9.3,

B(o, R B (abc)) • ∩ S = ∅, we have B o , R B (abc) -5 R B (abc) 2 /R • ∩ S = ∅ And since R B (abc) < λ < R/10, one has 5 R B (abc) 2 /R < 1 2 R B (abc) which gives B o , 1 2 R B (abc) ∩ S = ∅
But from the sampling condition we know that B (o , ) ∩ S = ∅ and therefore .20) and: Since by Lemma 9.17 R = R C (abc) < 2 we get the lower bound for h min (abc). For the smallest angle, using the well known equality for general triangles:

h min (abc) = R (1 -cos θ) ≥ R θ 2 4 ( 10
θ = ∠aoc + ∠cob with ∠aoc = 2 arcsin ac 2 ≥ 2 arcsin η 2R ≥ η R ∠cob = 2 arcsin cb 2 ≥ 2 arcsin η 2R ≥ η R This makes: θ ≥ 2 η R
sin ∠cab b -c = sin ∠abc c -a = sin ∠bca a -b
Since any edge length lower bonded by η and upper bounded by 2 , one has that the ratio between the smallest sin and the largest one is bounded by 2 η and since the largest angle cannot be smaller than π/3, we get that the smallest angle is lower bounded by: sin θ min > η 2 sin(π/3) > η 4

Proof of Lemma 9.20. (9.14) is direct consequence of Lemma 9.14 with p -q ≤ C (we loose a factor 2 but we don't care). Similarly, (9.16) is a direct consequence of Lemma 9.19. For (9.15), the rotation angle θ between Π(T ) and Π m may increases the distance to the plane by C sin θ. since sin θ ≤ θ ≤ β one gets β 2 < β 1 + C β .

For (9.17), one has:

∠ Π(abc), Π(T ) ≤ ∠ Π(abc), Π a + ∠ Π a , Π m + ∠ Π m , Π(T ) ≤ 2β + ∠ Π a , Π m
And by Lemma 9.13, one has ∠ Π a , Π m ≤ C 2R < β

E Proof of Lemma 9.23

The proof of Lemma 9.23 proceeds by induction, as in the proof of Lemma 9.17, along the directed acyclic graph given by Corollary 9.8. Before giving the proof we need some preliminary lemmas.

B(o, R) • ∩ B(o , R) • ⊂ B(m, h) • We get: s / ∈ B(m, h) • ⇒ max P B(o,R) (s), P B(o ,R) (s) ≥ 0
Therefore the theorem holds whenever s / ∈ S ∩ B(m, h) • . We assume now that s ∈ S ∩ B(m, h) • . We denote o H the orthogonal projection of o on H, s ab the orthogonal projection of s on line ab, and s abc the orthogonal projection of s on plane Π(abc), Observe that, since s ∈ B(m, h) • , s ab belongs to the open segment (a, b). From Lemma 9.5, we have:

s -s ab ≥ R 2 -(s ab -m) 2 -R 2 -h 2 (10.22)
Also, since a, b, s ∈ S, one has from the sampling conditions, min ( a -s , b -s ) ≥ η. Since for /R small enough one has 2 > R ≥ h and s ∈ B(m, h) • we get, as a rough estimate, min ( a -s ab , b -s ab ) ≥ 1/8(η/ ) 2 and therefore:

h -s ab -m ≥ 1/8(η/ ) 2
From this and (10.22) we get: In this case, one has:

s -s ab ≥ h 2R 1 8 (η/ ) 2 ≥ 1 64 (η/ ) 3 (
s abc -o H = s abc -s ab + s ab -o H This with (s -o) 2 = (s -s abc ) 2 + (s abc -o H ) 2 + (o H -o) 2 gives: (s -o) 2 = (s -s abc ) 2 + ( s abc -s ab + s ab -o H ) 2 + (o H -o) 2
And in particular we have:

(s -o) 2 ≥ ( s abc -s ab + s ab -o H ) 2 + (o H -o) 2 (10.27)
Also (s -s ab ) 2 = (s -s abc ) 2 + (s abc -s ab ) 2 and then:

s abc -s ab = s -s ab 1 - (s -s abc ) 2 (s -s ab ) 2 ≥ s -s ab 1 - (s -s abc ) 2 (s -s ab ) 2
and from (10.25) and (10.23) we get:

(s -s abc ) 2 (s -s ab ) 2 = O η 10 R 2 Therefore s abc -s ab ≥ s -s ab -O η 10 R 2
and equation (10.27) gives:

(s -o) 2 ≥ ( s -s ab + s ab -o H ) 2 + (o H -o) 2 -O η 10 R 2 2
Using equation (10.22) and the fact that

s ab -o H = m -o = √ R 2 -h 2 this gives: (s -o) 2 ≥ R 2 -(s ab -m) 2 + (o H -o) 2 -O η 10 R 2 2
But since s ab -m = o H -o we get:

P B(o,R) (s) = (s -o) 2 -R 2 ≥ -O η 10 R 2 2 = -α
And this concludes the proof of the lemma.

→ d ab = (b -a)/ b -a - → e c = (c -a) -c -a, -→ d ab -→ d ab - → n = (d -a) -d -a, -→ d ab -→ d ab -d -a, - → e c - → e c (m, - → e c , - →
∈ S ∩ B(v, C ). (s -ω) 2 -(s -ω ) 2 = (s -ω) + (s -ω ), (s -ω) -(s -ω ) = ω -ω, 2s -ω -ω
Denote by θ the angle between π(abc) and Π(abd).

One has: x ω = ω -m cos θ, z ω = ω -m sin θ and x ω = ω -m , z ω = 0, and Y ω = Y ω = 0. We get:

(s -ω) 2 -(s -ω ) 2 = (s -ω) + (s -ω ), (s -ω) -(s -ω ) = ω -ω, 2s -ω -ω = ( ω -m (1 -cos θ)) (2x s -ω -m (1 + cos θ)) + (-ω -m sin θ) (2z s -ω -m sin θ) According to Lemma 9.20 one has θ ≤ O R η 2 , This gives sin θ ≤ O R η 2 , 1 -cos θ ≤ O R 2 η 4 . |z s | ≤ O R η 2 and ω -m , |x s | ≤ O ( ).
We get as required:

|P abd (s) -P abd (s)| = (s -ω) 2 -(s -ω ) 2 ≤ α = C R 2 η 4 2
Proof of Lemma 9.23. If T ∈ T is acute, we have seen, from Lemma 9.3 that T is 0-almost empty. If T = abc is obtuse with longest edge ab, abc has a successor abd in the sequence defined in Corollary 9.8. Denote by m(abc) the length of the sequence defined in Corollary 9.8 from triangle abc to the last, and therefore acute, triangle in the sequence. One has m(abc) = m(abd) + 1 and, according to Lemma 9.9 one has m(abc) ≤ O ( /η) 2 ) . We proceed by a finite induction along the sequence. If abd is successor of abc, we will show that ∀s ∈ S, P abc (s) ≥ -max α Sp , α(abd )

Where

α Sp ≤ O R 2 η
10 2 is given by Lemma 10.4 And

α(abd ) = α(abd) + α with α = O R 2 η
4 2 given by Lemma .10.6.

Since the last triangle T last in the sequence, i.e. m(T last ) = 0, is acute, and therefore 0-almost empty.

Our induction hypothesis is that α(abd)-almost empty with:

α(abd) = O R 2 η 10 2
This is indeed correct for the acute triangle T last , last of the sequence. Considers -→ e c ∈ R n a vector in plane Π(abc), orthogonal to ab in direction c (since abc ∈ T it is not degenerate). More explicitly takes:

-→ d ab = (b -a)/ b -a - → e c = (c -a) -(c -a), -→ d ab -→ d ab
Consider the closed half space H+ and H-defined by: We examine now the case when x ω ≥ x o . As we see below this may arise only if abd is acute. Since abc is obtuse with longest edge ab we have x o < 0. Since c ∈ S, (10.28) gives: We claim that for /R small enough inequations (10.32) can not hold when abd is obtuse: indeed, if abd is obtuse, its longest edge is ad or bd (Lemma 9.7). W.l.o.g. assume it is ad. Since the angle ∠abd > π/2, we have ad 2 > ab 2 + bd 2 ≥ (2h) 2 + η 2 . Since ad ≤ 2ρ we get

H + = {x ∈ R n , x -a, - → e c ≥ 0} H -= {x ∈ R n , x -a, - → e c ≤ 0} Since H + ∪ H -=
(x c -x ω ) 2 + y 2 c -ρ 2 ≥

F An alternative to Whitney's Lemma

The proof of Theorem ?? makes use of [START_REF] Boissonnat | Local conditions for triangulating submanifolds of euclidean space[END_REF] for its final global argument. [START_REF] Boissonnat | Local conditions for triangulating submanifolds of euclidean space[END_REF] relies heavily on a Whitney Lemma which we consider to be the simplest argument there. However we produced an alternative argument to Whitney Lemma that perform a recursion on the link of spherical complexes. Since this argument, beside Whitney lemma, may have its own merit, we give it in this section.

F.1 Background

For a k-simplex σ we denote by |σ| the compact d-manifold simplex {x = (x 0 , . . . , x k ) ∈ R d , x i ≤ 1; ∀i, x i ≥ 0} and by σ • the open manifold relative interior of |σ|.

For a simplicial complex K, K d designates the set of d-dimensional simplex in K. K is said full dimensional if each simplex has at least one dimension d coface.

The topological space |K| is the support of K: Proof. For a contradiction, assume x 1 = x 2 and φ(x 1 ) = φ(x 2 ). Since φ |W and φ |E\W are injective one can assume w.l.o.g. that x 1 ∈ W and x 2 ∈ E \ W . Since E is Hausdorff, there are V x 1 and V x 2 respective open neighborhood of x 1 and x 2 such that

V x 1 ∩ V x 2 = ∅. V x 1 ∩ W x 1
and is open and since φ |W is open, φ(V x 1 ∩ W ) is open. Since φ(x 2 ) = φ(x 1 ) ∈ φ(V x 1 ∩ W ) and φ continuous, there exists an open neighborhood U 2 ⊂ V x 2 of x 2 such that φ(U 2 ) ⊂ φ(V x 1 ∩ W ). Since W is dense, W ∩ U 2 = ∅. If y 2 ∈ W ∩ U 2 , φ(y 2 ) ∈ φ(V x 1 ∩ W ) and there exits y 1 ∈ V x 1 ∩ W such that φ(y 1 ) = φ(y 2 ) and, since U 2 ∩ V x 1 = ∅, y 1 = y 2 , a contradiction since y 1 , y 2 ∈ W Definition 10.10 (Convex preserving). We say that a map from R n to R m is convex preserving if the image of the convex hull is the convex hull of the image.

If a map is injective and convex preserving, it sends simplex to simplex of the same dimension and images of joins are joins of images. Homographies are convex preserving. We consider in the proof of the theorem below an homography h. We denote by dom h ⊂ R n , its domain, i.e. the set of points where the denominator does not vanish. One can check that h |C , the restriction of h to a compact convex set C ⊂ domain(h) is convex preserving. For some ŝ > 0 small enough, one has λŝ ≤ 1 and:

x + ŝ 1 -λŝ t ∈ τ • F.3 Case M = S d
Notice that the theorem below is not true for infinite simplicial complexes as one can see if K is a 1 dimensional simplicial complex whose support |K| = R and edges are {[j, j + 1], j ∈ Z} and φ : |K| → S 1 , such that φ(j) = e i arctan j .

Theorem 10.12. Let d ≥ 0 and K be a finite, d-dimensional simplicial complex. For a piecewise linear map φ : |K| → R d+1 \ {0} define Remark: Condition 2. could be expressed in a more specific form: 0 and the image by φ of the d + 1 vertices of any d simplex in K span a (d + 1)-dimensional affine space. We keep the general formulation since we expect the theorem to extend to more general situations.

Proof of Theorem 10.12. The theorem is true for d = 0: since K has at least two vertices and φ is injective (condition 3.), K is made of exactly two vertices and • φ is a bijection onto S 0 . The proof for d ≥ 1 goes by induction on the dimension. We consider the case d ≥ 1 and we assume the theorem to be true for any dimension d < d.

Barycentric subdivisions of K leads to complex K sub with natural homeomorphisms h : |K sub | → |K| such that K sub and φ sub = φ • h satisfy the hypothesis of the theorem since φ does. It is possible to apply barycentric subdivisions until we have that if x, y ∈ |σ| for σ ∈ K sub ,

• φ sub (x),

• φ sub (y) > 0. We therefore, for simplicity, assume without loss of generality that K and φ meet themselves this condition:

x ∈ |σ| ⇒ ∀y ∈ |σ|,

• φ(x),

• φ(y) > 0 (10.34)

It is enough to prove that

• φ is open. Indeed, by Lemma 10.8

• φ is then one to one on its image and, since it is open, the

- • φ(x)
It is well defined by 10.34. The restriction of ψ x to some simplex in St τ x is an homography restricted in a convex set included in its domain by 10.34. It is therefore convex preserving.

Observes also that since the restriction of:

z → z • φ(x), z - • φ(x) to • φ(| St τ x |
) is an homeomorphism on its image, properties 2. and 3. of For the proof of the lemma it remains to check that φ satisfies conditions 2. and 3. of the theorem. Assume that • φ (y 1 ) = • φ (y 2 ). This is equivalent to the existence a positive real number λ > 0 such that φ (y 1 ) = λφ (y 2 ). In other words ψ x (y 1 ) -λψ x (y 2 ) ∈ span A (τ x ) = span L (τ x ). We can then apply Lemma 10.11 and we have:

F.4 Local injectivity

Theorem 10.14 is an easy consequence of Theorem 10.12. ) and x 1 and x 2 are in a same simplex, then condition 2. of the theorem implies x 1 = x 2 . Assume now for a contradiction that π(x 1 ) = π(x 2 ) and that x 1 and x 2 does not belong to a same simplex. We know then that x 1 = v and x 2 = v since if for example x 1 = v then there would be a d-dimensional simplex containing both x 2 and, necessarily, v = x 1 . Without loss of generality we can assume that π(v) = 0 and π(x 1 ) = π(x 2 ) = 0. We have, for some λ 1 , λ 2 > 2, x i = (1 -λ i )v + λ i xi with xi ∈ | Lk v| and π(x i ) = λ i π( xi ) for i = 1, 2. Then π(x 1 ) = π(x 2 ) ⇒ λ 1 π( x1 ) = λ 2 π( x2 ) and, using the notation of Theorem 10.12 this gives

  , ..., a i , ...a d ] where the symbol a i means the vertex is deleted from the array. The kernel of the boundary operator Z d = Ker ∂ d is called the group of d-cycles and the image of the operator B d = Im ∂ p+1 is the group of d-boundaries. We say two d-chains A and A are homologous if A -A = ∂ d+1 B, for some (d + 1)-chain B.

Definition 3 . 1 .

 31 A d-chain A ∈ C d (K) is said reducible if there is a d-chain Γ ∈ C d (K) (calledreduction) and a (d + 1)-chain B ∈ C d+1 (K) such that:

Algorithm 2 :Proposition 3 . 5 .

 235 Total reduction algorithm Inputs : A d-chain Γ, the reduced boundary matrix R for i ← m to 1 do if Γ[i] = 0 and ∃j ∈ [1, n] with low(j) = i in R then Γ ← Γ + R j end end After the reduction algorithm, Algorithm 2 finds the total reduction of a given d-chain in O(m 2 ) time complexity.

  2 a slight variant of the Problem 4.1: in case we can find a representative Γ 0 in the set B A = ∅, such that ∂ d Γ 0 = A, we are then taken back to Problem 4.1 to find the minimal d

Algorithm 3 :Proposition 4 . 2 .

 342 Total reduction variant Inputs : A d-chain Γ and Z for i ← m to 1 do if Γ[i] = 0 and ∃j ∈ [1, n Z ] with low(j) = i in Z then Γ ← Γ + Z j end end After matrix reduction, Algorithm 3 computes the solution for Problem 4.1 in O(m 2 ) time complexity.

Definition 5 . 1 (Definition 5 . 2 (Definition 5 . 3 (Problem 5 . 1 .

 51525351 Pseudomanifold). A d-pseudomanifold is a pure d-dimensional simplicial complex for which each (d -1)-face has exactly two d-dimensional cofaces.In particular any combinatorial k-manifold is a k-pseudomanifold. Dual Graph of a pseudomanifold). The dual graph of a d-pseudomanifold M is the graph whose vertices are in one-to-one correspondence with the d-simplices of M and whose edges are in one-to-one correspondence with (d -1)-simplices of M : an edge e connects two vertices v 1 and v 2 of the graph if and only if e corresponds to the (d -1)-face with cofaces corresponding to v 1 and v 2 . Strongly connected pseudomanifold). A strongly connected d-pseudomanifold is a d-pseudomanifold whose dual graph is connected.Given a strongly connected (d + 1)-pseudomanifold M and τ 1 = τ 2 two (d + 1)-simplices of M, we consider a special case of problem 3.1 where K = M \ {τ 1 , τ 2 } and A = ∂τ 1 : Given a strongly connected (d + 1)-pseudomanifold M with a total order on the d-simplicies and two distinct (d + 1)-simplices (τ 1 , τ 2 ) of M, find:

Proposition 5 . 7 .

 57 Γ min is solution of Problem 5.1 if and only its dual 1-chain Γmin is solution of Problem 5.2 on the dual graph G(M) of M where τ1 and τ2 are respective dual vertices of τ 1 and τ 2 .

Figure 6 .

 6 Figure 6.1 illustrates the possibilities for Θ(σ) in the case n = 3 and zero weights.

Figure 6 . 1 :

 61 Figure 6.1: Illustration for the definition of Θ(σ) for a tetrahedron σ = abcd in the case of zero weights.

Figure 6 . 2 :

 62 Figure 6.2: Illustration for the definition of bis τ and π τ (top left and right) and Φ τ (bottom).

Figure 6 . 3 :

 63 Figure 6.3: Illustration of the shadow polytope of Definition 6.21 corresponding to the example of Figure 6.2.

Figure 6 .

 6 Figure 6.3 depicts in blue the Shadow polytope corresponding to the example of Figure 6.2.Observe that the shadow polytope is indeed a polytope since for each lower half-space H j with boundary going through (0, µ C (τ )) and contributing to the convex cone of Φ τ (P) at (0, µ C (τ )), the intersection H j ∩ bis τ is a (n -k)-dimensional half-space in bis τ . The shadow polytope is precisely the intersection of all such half-spaces H j ∩ bis τ . Since each H j is a lower half-space and since by observation 6.18 one has µ C (τ ) > 0, H j does not contains (0, 0), which implies that H j ∩ bis τ does not contain the point o τ in bis τ . It follows hat:

  other words, τ ∪ σ has an odd number of n-cofaces in the chain Γ. This in turn means that σ has an odd number of (n -k)-cofaces in the trace of Γ in the link of τ , i.e. σ ∈ ∂ Tr τ (Γ).Farthest point cannot be in the interior of the visible part of a convex boundaryLemma 6.26. Let C ⊂ R n be a polytope and O ∈ R n \ C. Let X ⊂ ∂C be a compact set union of facets of C visible from O. If x ∈ X maximizes the distance to O, then x is in the closure of ∂C \ X.

Figure 6 . 4 :

 64 Figure 6.4: Illustration of Lemma 6.27 for n = 1.

Figure 6 . 5 :

 65 Figure 6.5: Illustration of the recursion in the proof of Lemma 6.27 for n = 2.

Figure 6 . 6 :

 66 Figure 6.6: Illustration of the recursion in the proof of Lemma 6.27 for n = 3.

Figure 6 . 7 :

 67 Figure 6.7: Illustration for equation (6.44).

  then τ µ = B is (from the general position asumption) the unique simplex in K P whose bounding weight is µ = B . But then Γ reg and Γ min coincide on simplices with bounding weight µ = B , a contradiction with the definition of µ = B . Assume now that dim(τ µ = B ) = k < n.

Lemma 7 . 3 .

 73 Consider σ = abc a non degenerate triangle. Then we have the following. For any triangle abc there is a function ω abc ω abc : [1, ∞) → R such that: lim p→∞ ω abc (p) = 1 and:

5 .

 5 When d = 2, Condition 7.1 is generic.

Figure 8 . 1 :

 81 Figure 8.1: Watertight reconstructions under different perturbations. Under small perturbations (first two images from the left), the reconstruction is a triangulation of the sampled manifold. A few non-manifold configurations appear however under larger perturbations (Rightmost image).

Figure 8 . 2 :

 82 Figure 8.2: Open surface triangulations under imposed boundaries (red cycles).

Figure 8 . 3 :

 83 Figure 8.3: Providing additional topological information can improve the result of the reconstruction.

Figure 8 . 4 :

 84 Figure 8.4: Closed surface triangulation of 440K points in 7.33 seconds.

Figure 9 . 1 :

 91 Figure 9.1: Spindle of edge ab with radius R C (abc).

  Let m ∈ M and Π m the plane tangent to M at m. Denote by π m : R n → Π m the orthogonal projection on Π m . Denote by D(m, R/4) ⊂ Π m the disk centered at m of radius R/4 and C(m, R/2, R/4) the set of points in B(m, R/2) that project on D(m, R/4):

  Lemma 9.18 is given in Appendix D. Denote by v h min the minimal altitude (height) of all triangles:

Lemma 9 . 20 .

 920 Consider T ∈ T and m a vertex of T . Denote by Π(T ) the supporting plane of T and Π m the plane tangent to M at m, then nearby point clouds are near these plane, more precisely for any given constant C > 1: S ∩ B(m, C ) ⊂ Π ⊕β 1 m (9.14) with:

Lemma 9 . 21 .

 921 For any constant C > 0, m ∈ M, and T ∈ T such that T ⊂ S ∩ B(m, C ), denote by Π(T ) the supporting plane of T . The distance between the circumcenter of T and the plane tangent to M at m is bounded by β with:

  [START_REF] Chen | Quantifying homology classes[END_REF] then any path in the connected component of CC (T 0 ) in G δ cannot get out of B(C C (T 0 ) , ρ)since it has exhausted the maximal number of triangles with circumcenters in B(C C (T 0 ) , ρ) after a length of ρ -δ.It follows that in this case the cardinal of the connected component of C C (T 0 ) in G δ is upper bounded by: ρ + 2 η/2 6

1 /2 η 6 9. 5 . 1 Definition 9 . 25 .

 1651925 Triangles in separate connected components of G δ do not overlap If A, B ⊂ R 2 , we denote by S(A, B) the separation distance of A, B defined by: S(A, B) = sup y =1 inf a∈A b∈B y, b -a Since y, b -a = -y, a -b one has: S(A, B) = S(B, A) We denote by |A| the convex hull of A. Since ∀y, inf a∈A y, a = inf a ∈|A| y, a one has: S(A, B) = S(|A|, B) = S(A, |B|) = S(|A|, |B|) if |A| ∩ |B| = ∅: S(A, B) = inf a∈|A| b∈|B| a -b If A and B are compact sets, then: S(A, B) > 0 ⇐⇒ |A| ∩ |B| = ∅ We define width(A) for a convex set A as: Definition 9.26. width(A) = -S(A, A) = inf y =1 sup a,a ∈A y, a -a One has S(A, B) = S(|A|, |B|) = sup y =1 inf a∈|A| b∈|B| y, b -a ≤ sup y =1 inf a,b∈|A|∩|B| y, b -a and therefore: If |A| ∩ |B| = ∅: S(A, B) ≤ -width(|A| ∩ |B|) (9.20)

3 /2 η 10 Proof. 2 η 10 2 ( 9 . 21 )

 3102102921 Denote s i for i = 1, 2, 3 the vertices of T and Denote s j for j = 1, 2, 3 the vertices of T . According to Lemma 9.23 one has: ∀i, P T (s i ) ≥ -α and ∀j, P T (s j ) > -α with α = O R Since by definition: ∀j, P T (s i ) = 0 and ∀j, P T (s j ) = 0 It follows:

  [START_REF] Tamal | Tight cocone: A water-tight surface reconstructor[END_REF] and(9.24) gives us:∀i, j, y, π m (s i ) -π m (s j ) S(π m (T ), π m (T )) > -βRecall that for a triangle T = abc , V(T ) = {a, b, c}, denotes the set of vertices of T , that |T | denotes the convex hull of T and, if A is a set, d(v, A) = inf a∈A d(v, a).

  a union of parts of edges of T and intersections of balls boundaries with |T |. Convex corners appears at the intersection of edges and balls. Considers edge s 1 s 2 . The two convex corners appears at the intersection of spheres with radius η/2 centered at s 1 or s 2 . Let us denote by o = C C (T ) the circumcenter of T , by m = (s 1 s 2 )/2 the middle of edge s 1 s 2 , and by c a corner. With h = m -o and d = m -s 1 = m -s 2 ≥ η/2, one has:

3 η 2 8

 32 > 2 -10 η 3 . Now consider the case when only two of the three tangent edges to the maximal disk, say ab and ac, belong to triangle T . If a is a also a vertex of π m (T ) = ab c , this means that the maximal disk has is third tangent point on b c . call b (respectively c ) the intersection of b c with ab (respectively ac). Then the triangle ab c is a subset of π m (T ) ∩ π m (T ). It follows that width (π m (T ) ∩ π m (T )) is lower bounded by the smallest height of ab c . But from Lemma 9.29 we have that the sinus of the angle ∠b ac = ∠bac is lower bounded by η 8 . Since the height d(a, (b c )) = d(a, (b , c )) is lower bounded (Lemma 9.29 again) by η 2

  30 we have then that: width π m (T ) ∩ π m (T ) > 2 -10 η 3 and from Lemma 9.27, if T and T are not in the same connected component of G δ this means that C C (T ) -C C (T ) > δ and Lemma 9.27 gives: S(π m (T ), π m (T )) > -β with:

same connected component of G δ 9 . 6 . 1

 961 Partition of a connected components CC of G δ into dual graph connected components (CC j ) j=1,k

Lemma 10 . 1 .

 101 with (10.2) gives the claim(10.1). Now, if some n-simplex σ ∈ Γ with |σ| x, for some x ∈ CH(P) \ |K n-1 P |, is not Delaunay, thenσ∈Γreg |σ| x δ σ (x) p = δ σreg (x) p < |σ| x δ σ (x) pand since the function is continuous, this implies:Γ (p) > Γ reg (p) Given P = {P 1 , . . . , P N } ⊂ R n , with N ≥ n + 1,in general position, denote by β P ∈ C n-1 (K P ) the (n -1)-chain made of simplices belonging to the boundary of CH(P). Let Γ ∈ C n (K P ) be such that: ∂Γ = β P If x ∈ CH(P) \ |K n-1 P | then there is an odd number of n-simplices σ ∈ Γ such that x ∈ |σ|.

  ) = (1 -t)x + tx along segment [x x]. This segment intersect transversally the (n -1)-faces |τ |, for τ ∈ K P . At each intersection point we can keep track of the change in the number of covering n-simplices, where, by covering simplices we name the n-simplices σ ∈ Γ such that x ∈ |σ|. We know that this number is zero at x since x / ∈ CH(P). Since CH(P) ∩ [x x] is convex there is a single intersection point y(t b ) between [x x] ans the boundary of CH(P). This point y(t b ) ∈ (x , x) hits a (n -1)-simplex τ b ∈ |β P |, face of the convex hull boundary. Since ∂Γ = β P , we know that τ b is shared by an odd number n b of n-simplices in |Γ|. By definition of the convex hull, and since P is in general position, for each n-simplex σ coface of τ b , |σ| is on the inner side of the convex hull supporting half plane. It follows that the number of covering simplices become the odd number n b just after the first crossing.

  even and the number of covering simplices remains odd all along the path [x x].

Definition 10 . 2 (

 102 Upper set measure D φ ). Consider a compact set D ⊂ R d . For a continuous function φ : D → [0, 1] we denote by D φ the upper set measure of φ, the map Dφ : [0, 1] → R + defined as: D φ (t) = def µ L ({u ∈ D, φ(u) ≥ 1 -t})where µ L denotes the Lebesgues measure.

  y), x 2 + y 2 ≤ t} which gives for the upper set measure D φσ : ∀t ∈ [0, α], D φσ (t) = πt and then, if D φσ denotes the derivative of D φσ : σ strictly acute triangle ⇒ ∀t ∈ [0, α], D φσ (t) = π (10.8)

Figure 10 . 1 : 2 t

 1012 Figure 10.1: Acute triangle case

Figure 10 . 2 :

 102 Figure 10.2: Right triangle case

8 Proof of Lemma 7 . 8 .Figure 10 . 3 :

 878103 Figure 10.3: Obtuse triangle case

Case 1 .

 1 Assume for this case:R B (σ 1-,max ) < R B (σ max )

Case 2 .

 2 w p (σ) p and we get Γ 1 ∞ Γ 2 with (10.14). Assume for this case:R B (σ 1-,max ) = R B (σ max ) and R C (σ 1-,max ) > R C (σ max )

2 ( 10

 210 and with(10.20):h min (abc) ≥ R η R

Lemma 10 . 4 .α= O R 2 η 10 2 Proof.

 1042102 Let abc ∈ T be an obtuse triangle with longest edge ab. If o = C C (T ) and o = a + b -o is the point symmetric to o with respect to (a + b)/2, then have: ∀s ∈ S, max P B(o,R C (T )) (s), P B(o ,R C (T )) (s) ≥ -α Sp with: Sp In the condition of the theorem, Consider the hyperplane H orthogonal to ab going through s. Let us denote m = (a + b)/2 and h = a -b /2 the center and radius of the open ball B • (m, h) with diameter ab and by R = R C (abc) the circumradius of triangle abc. Since

Definition 10 . 5 (Lemma 10 . 6 .Proof.

 105106 Unfolded adjacent triangles). Let abc, abd ∈ T be adjacent triangles in T . The circle centered at (a + b)/2, orthogonal to ab in the 3-affine space spanned by {a, b, c, d} and going through d cuts the plane Π(abc) at two points. Since the angle between π(abc) and Π(abd) is small for /R small enough (Lemma 9.20), one of these two ponts is strictly closer than the other from d. It is called the unfolded point of d in plane Π(abc) along ab. If d is the unfolded point of d in plane Π(abc) along ab, triangle abd is called the unfolded triangle of abd in plane Π(abc) along ab. For abc, abd ∈ T , if abd is α-almost empty and abd is the unfolded triangle of abd in plane Π(abc) along ab then abd is (α + α )-almost empty, with: Denote by m = (a + b)/2 the middle of segment ab. Denote by -→ d ab ∈ R n the unit vector in direction -→ ab and by -→ e c ∈ R n the unit vector in plane Π(abc) orthogonal to ab and such that c -a, e c > 0. Vector -→ n is in the linear space spanned by {a, b, c, d} and orthogonal to plane abc. More explicitly takes: -

2 η 10 2

 2102 10.6 we have that, if d is the unfolded of d in plane Π(abc) along ab, abd is α -almost empty for: α = α(abd) + α ≤ O R Denote by ω = C C (abd ) and ρ = R C (abd ) = R C (abd) respectively the center and radius of the circumscribing circle of abd . α -almost empty writes as: ∀s ∈ S, (s -ω) 2 -ρ 2 ≥ α (10.28) Denote by m = (a + b)/2 and h = ab/2 respectively the middle of ab and its half length. Since abc is obtuse with longest edge ab we have: (m -c) 2 < h 2 (10.29) Denote by o = C C (abc) and R = R C (abc) the respectively the center and radius of the circumscribing circle of abc. One has (abc obtuse and Lemma 9.7): ρ > R ≥ h (10.30) In plane Π(abc) we consider the orthonormal frame (m, -→ e c , -→ d ab ) and denote by (x o , y o ) = (x o , 0), (x c , y c ) and (x ω , y ω ) = (x ω , 0) the respective coordinates of o, c and ω in this frame. Observes that the radical hyper-plane of spheres B(o, R) and B(ω, ρ) is orthogonal to the line oω and goes through m. Then, if x ω < x o one has ∀s ∈ S ∩ H -, P abc (s) = P B(o,R) (s) ≥ P B(ω,ρ) (s) ≥ -α So that we have proven the induction when x ω < x o .

η 2 / 4 < ρ 2 -η 2 α 2 < η 2 / 4 2 η 4 2 From ( 10 . 32 ) 2 η 6 2

 242224242103226 h 2 = x 2 ω and for /R small enough we have8 which proves the claim. It follows that it just remains to consider the case when abd, and therefore abd , is acute. abd is 0-almost empty and, from Lemma 10.6 abd is α -almost empty with α(abd ) ≤ O R we get that:o -ω < 16 η 2 α(abd ) (10.33) Since, for /R small enough we have R ≤ ρ < 2 . If o -s > 2 then P abc (s) = (s -o) 2 -R 2 > 0. Now if ω -s > 3 , then o -s ≥ ω -s -o -ω > 3 -16 η 2 α(abd ) and for /R small enough 3 -16 η 2 α(abd ) > 2 which gives again o -s > 2 and P abc (s) > 0. Assume now that o -s ≤ 2 and ω -s ≤ 3 . (10.33) gives:|(o -s) 2 -(ω -s) 2 | = | o -ω, (o -s) + (ω -s) | ≤ o -ω (o -s) + (ω -s) ≤ ( 16 η 2 α(abd ))(5 )Which gives in particular:P abc (s) -P abd (s) -(ρ 2 -R 2 ) = (o -s) 2 -(ω -s) 2 ≥ -α with α ≤ O R Which gives, since ρ 2 -R 2 >0, P abc (s) ≥ P abd (s) -α . Since abd is acute, by Lemma 10.6, abd is α -almost empty with α = O R 2 η 4 2 , therefore, one has ∀s ∈ S, P abc (s) ≥ -α -α which proves the induction in this case and concludes the proof of the lemma.

|σ|Lemma 10 . 9 .

 109 Lk σ and St σ denotes respectively the link and the star of the simplex σ in K. St • σ denotes the corresponding open topological space: St • σ = τ ∈St σ τ • σ τ denotes the join of σ and τ Recall that a map f between topological spaces is said open if it maps open sets to open sets:U open ⇒ f (U ) open. We say that f is open at x if the restriction of f to some neighborhood of x is open. It is easy to check that f : E → F is open iff. it is open at any x ∈ E. Since x 1 ∈ U ∩ V x 1 , U ∩ V x 1 is a non empty open set and since W is dense in E, W 1 = W ∩ U ∩ V x 1 is an open set dense in U ∩ V x 1 . The same holds for W 2 = W ∩ U ∩ V x 2 .Since φ is continuous and open, φ(W 1 ) and φ(W 2 ) are open sets dense in φ(U ). The intersection of two dense open sets is a dense open set. Therefore φ(W 1 ) ∩ φ(W 2 ) is dense in φ(U ) and in particular non empty. But if y∈ φ(W 1 ) ∩ φ(W 2 ), there are w 1 ∈ W 1 ⊂ W and w 2 ∈ W 2 ⊂ W such that w 1 , w 2 ∈ W , φ(w 1 ) = φ(w 2 ) = y and, since W 1 ∩ W 2 = ∅, w 1 = w 2 ,a contradiction. J'ai l'impression qu'on pourrait raccourcir cette preuve. Let φ : E → F be a continuous map . If E is Hausdorff and W ⊂ E is a dense open subset such that φ |W is injective and open and φ |E\W is injective, φ is injective.

Lemma 10 . 11 . 2 For 0

 101120 Let |τ | ⊂ R n be a k-simplex and τ • its relative interrior. For x ∈ τ • and z 1 , z 2 ∈ R n \ span A (τ • ), if there is λ > 0, such that:(z 2 -x) -λ(z 1 -x) ∈ span L (τ • ) then: {z 1 } |τ | ∩ {z 2 } |τ | \ |τ | = ∅ Proof. If t ∈ span L (τ • ) is such that: t = (z 2 -x) -λ(z 1 -x)One has:z 2 = x + λ * (z 1 -x) + t Consider, for s ∈ [0, 1]: g 2 (s) = (1 -s)x + sz < s ≤ 1,g 2 (s) ∈ {z 2 } |τ | \ |τ |. Also a short computation gives: g 2 (s) = (1 -λs) x + s 1 -λs t + λsz 1

•φ: 1 . 2 . 3 .φ

 123 |K| → S d as : Any simplex τ ∈ K with dim τ ≤ d -1 has at least two d-dimensional cofaces for d ≥ 1, and K has at least two 0-dimensional simplices for d = 0. For any σ ∈ K d , the restriction of • φ to |σ| is injective. The restriction of • is a homeomorphism between |K| and S d .

• φ - 1

 1 is continuous. But since |K| is compact (as finite simplicial complex) and open, • φ(|K|) is a compact and open subset of S d . Since S d is connected, • φ(|K|) = S d .We introduce the open set W k ⊂ |K|:W k = τ ∈K dim τ ≥k τ • One has σ∈K d σ • = W d ⊂ W d-1 ⊂ . . . ⊂ W 0 = |K| Since φ |W d is injective (condition 2.), itfollows from the invariance of domain theorem that • φ is open on W d . We prove now by induction on decreasing k that • φ |W k is open and injective. For k < d, we assume that this is true for anyk such that k < k ≤ d. For x ∈ W k \ W k+1 , there is a unique simplex τ x ∈ K such that x ∈ τ • x . One has dim τ x = k. Since St • τ x \ τ • x ⊂ W k+1 is open and • φ |W k+1 is open and injective, • φ | St • τx\τ •x is open and injective. Then one can apply Lemma 10.9 withE ← St • τ x and W ← St • τ x \ τ •x . It follows that • φ | St • τx is injective. It remains to prove that it is open at x. Denote by Π x the plane tangent to S d at • φ(x) and by | St τ x | = ∪ σ∈St τx |σ| the closure of St • τ x . Let ψ x : | St τ x | → Π x defined as:

• φ are inherited by ψ x : ••

 : For any σ ∈ St τ x , the restriction of ψ x to |σ| is injective and convex preserving. The restriction of ψ x to W k+1 ∩ | St τ x | is injective.In the identification Π x = R d , without loss of generality one can assume that ψ x (x) = 0 andψ x (τ • x ) spans R k × {0}. Define π τ ⊥ : R d → R d-k projection on the (d -k) th last coordinates.Lemma 10.13. φ : Lk τ x → R d-k , defined by φ = π τ ⊥ • ψ x | Lk τx satisfies the theorem for d = d -k -1 Lemma 10.13 allows us to recursively apply the theorem to get that | Lk τ x | is homeomorphic to S d and therefore St • τ x is a manifold. Since • φ | St • τx is continuous injective from a d-manifold to a d-manifold, the invariance of domain theorem says that it is open, in particular • φ is open at x. Since this is true for any x ∈ W k \W k+1 , it follows that • φ |W k is open. We can apply Lemma 10.8 with E ← W k and W ← W k+1 (or W ← W d ) to get that • φ |W k is injective and open. One has in particular at the end of the recursion that • φ |W 0 = • φ is open and injective and we are done. Proof of Lemma 10.13. Observe first that Lk τ x is a d -dimensional simplicial complex, with d = d -k -1 such that any simplex has at least 2 d -dimensional cofaces for d > 0 and Lk τ x has has least two vertex if d = 0. It follows that condition 1. of the theorem is met by φ .We prove now that ∀y ∈| Lk τ x |, φ (y) ∈ R d \ {0}. Assume that there is y ∈ | Lk τ x | with φ (y) = 0, that is ψ x (y) ∈ span A (ψ x (τ • x )) where span A (ψ x (τ • x )) is the affine span of ψ x (τ • x ) (it corresponds also to the linear span since 0 = ψ x (x) ∈ ψ x (τ • x )). There is a simplex σ ∈ Lk τ x such that y ∈ σ • and:ψ x (y) ∈ span A (ψ x (τ • x )) ∩ ψ x (σ • ) which gives dim span A [ψ x (τ • x ) ψ x (σ •)] ≤ dim ψ x (τ • x ) + dim ψ x (σ • ).The restriction of ψ x to τ • x σ • is convex preserving and injective. It follows that ψ x (τ • x ) ψ x (σ • ) = ψ x (τ • x σ • ) has dimension dim τ x + dim σ + 1, a contradiction.

( 1 • and y 2 ∈ σ 2 • with σ 1 , σ 2 ∈

 1212 {ψ x (y 1 )} |τ x | ∩ {ψ x (y 2 )} |τ x |) \ |τ x | = ∅ (10.35) If, for some σ ∈ St τ x , y 1 , y 2 ∈ |σ | and y 1 = y 2 , (10.35) contradicts the fact that the restriction of ψ x to |τ x σ | is injective. This proves that φ satisfies condition 2. of the theorem. Now If y 1 ∈ σ St τ x , σ 1 = σ 2 and dim σ 1 = σ 2 = d , then (10.35) contradicts the fact that the restriction of ψ x to W k+1 ∩ | St τ x | is injective. This proves that φ satisfies condition 3. of the theorem.

Theorem 10 . 14 . 1 .

 10141 For a vertex v, we denote by St v the closed star of v, i.e. the open star St • v of v augmented by all the faces of simplices in St • v. Note that Lk v ⊂ St v. Let d ≥ 1 and K be a finite, d-dimensional simplicial complex such that for any vertex v ∈ K 0 there exists a piecewise linear map π : St v → R d such that: Any simplex in τ ∈ K with dim τ ≤ d -1 has at least two d-dimensional cofaces in K.

2 .

 2 For any σ ∈ St v, the restriction of π to |σ| is injective.

3 .

 3 The restriction of π to σ∈K d ∩St v σ • is injective. Then St • v is homeomorphic to an open ball in R d and π is injective and its restriction to St • v is open. In particular |K| is a d-manifold. Proof. Denote by π Lk v the restriction of π to Lk v. π Lk v satisfies the conditions of Theorem 10.12. It follows that π Lk v is injective and open and that | Lk v| is homeomorphic to S d-1 . We get then that since St v is the cone on Lk v, |St v| and St • v are homeomorphic respectively to the closed and an open ball in R d . Since |K|, as any realization of simplicial complex, is Hausdorff and since any point x ∈ |K| belongs to the open star St • v of some vertex v, it has a neighborhood homeomorphic t a neihgborhood in R d . It follows hat |K| is a d-manifold. It remain to prove that π is injective and open. If π(x 1 ) = π(x 2

•

  π( x1 ) = • π( x2 ) and since • π is one to one we get x1 = x2 , a contradiction with the fact that x 1 and x 2 does not belong to a same simplex. We have proven that π is injective and since it is continuous and St • v is a d-manifold, Invariance of Domain (Theorem 10.7) applies and the restriction of π to St • v is open.

First generic condition. Condition 6.1. We say that P =

  1 , µ 1 ) and (P 2 , µ 2 ) are orthogonal if D ((P 1 , µ 1 ), (P 2 , µ 2 )) = 0. {(P 1 , µ 1 ), . . . , (P N , µ N )} ⊂ R n × R satisfies the first generic condition if no (n + 1) points {P i 1 , . . . , P i n+1 } lie on a same (n -1)-dimensional affine space.

Generalization of circumradius and bounding radius.

  We define the following generalizations to set of weighted points of circumsphere and smallest enclosing ball.

	Definition 6.5. Assume that P satisfies Condition 6.1. Given a k-simplex σ ⊂ P with 0 ≤
	k ≤ n the generalized circumsphere and smallest enclosing ball of σ are the weighted points
	(P C , µ C )(σ) and (P B , µ B )(σ) respectively defined as:

  is in general position if it satisfies the first generic condition 6.1 and if, for a k-simplex σ and a k -simplex σ in K P

	with 2 ≤ k, k ≤ n, one has:
	µ C (σ) = µ C (σ ) ⇒ σ = σ	(6.4)
	Lemma 6.10. Under generic condition 6.2 on P, for any simplex σ, there exists a unique
	inclusion minimal face Θ(σ) of σ such that (P B , µ B )(σ) = (P C , µ C )(Θ(σ)). Moreover one has
	(P C , µ C )(Θ(σ)) = (P B , µ B )(Θ(σ)).

  abc) and the result follows from Lemma 9.16. If abc is obtuse this follows from Corollary 9.8 (and Lemma 9.16). The lower bound follows from the fact that edge lengths are lower bounded by η.

	Controlling triangle planes and circumcenters For a triangle abc, we denote by h min (abc)
	its smallest height.

Lemma 9.18. If abc ∈ T is acute then its smallest height h min (abc) is lower bounded by R C (abc). If abc ∈ T is obtuse then its smallest height h min (abc) is lower bounded by:

  2 while, after equation (9.26) if p was vertex s i of T one would have d(π T(s), |T |) 2 = d(π T (s), s i ) 2 > η 2 /2. Therefore, if π T (s) /∈ |T | then p is on an edge, say, w.l.o.g., s 1 s 2 . Then, similarly to the case π T (s) ∈ |T |, we can split s i -s in a component on the vectorial line supporting s 1 s 2 and its orthogonal space. In both cases we have:

	∀i, (s i -p) 2 > η 2 /2	(9.27)

2

  Since by Lemma 9.23, T is α-almost empty with α = O R

	B o,	√	R 2 -α and therefore:	2	η	10 2	we have that s / ∈

connected component CC of G δ but in separate connected components of the dual graph

  We consider now the case of triangles in a same connected component CC of G δ but in separate connected components CC i , CC j of the dual graph in CC. For given C > 0 and for R small enough, let be CC is a connected component of G δ and V the set of vertex of triangles in CC be such that for some m ∈ M one has V ⊂ S m,R/2,C . If CC i and CC j are two distinct connected components of the dual graph in CC, for T 1 ∈ CC i and T 2 ∈ CC j one has:

	Lemma 9.40.

  It follows from the definition that the upper set measure t → D φ (t) is non decreasing. For next Lemma, recall that, by Rademacher Theorem, Lipschitz function are differentiable almost everywhere. Consider a compact set D ⊂ R d and a continuous function φ : D → [0, 1]. Assumes the upper set measure D φ of φ is Lipschitz and denote by D φ its derivative defined a.e.. Then one has:

	Lemma 10.3. D

  1 2 R B (abc) < .Proof ofLemma 9.18. A triangle abc is obtuse if and only, when inscribed in its circumcircle, it does not cover the centre of the circle. It follows that abc is obtuse if and only if h min (abc) < R C (abc). If abc is acute one has then: h min (abc) ≥ R C (abc) ≥ 1 If abc is obtuse with longest edge ab, its smallest height is the height above ab. Considers triangle abc inscribed in its circumcircle with radius R = R C (abc) and center o, with angle ∠aob positive. Taking: θ = ∠ aob 2 One has:

	√	3 η

  10.23) Since s ab and s abc are in plane Π(abc) and the vector (s -s abc ) is orthogonal to it, one has:(s ab -s abc ) 2 + (s -s abc ) 2 = (s -s ab ) 2Since abc is obtuse with longest edge ab, one has o = m and then s ab -o H = m -o = 0. Since s ab ,s abc and o H all lie on the same line H ∩ Π(abc) and since, from (10.26) s ab -s abc = 0 we get:s ab -o H , s abc -s ab = 0If s ab -o H , s abc -s ab > 0 we prove that P B(o,R) (s) ≥ -α. The proof that P B(o ,R) (s) ≥ -α when s ab -o H , s abc -s ab < 0 goes similarly. So assume now that s ab -o H , s abc -s ab > 0.

								(10.24)
	From Lemma 9.20 we have also s ∈ Π(T ) ⊕β , with β = O R η	2	and therefore
	(s -s abc ) 2 ≤ β 2 = O	R	2	η	4	2	(10.25)
	This with (10.23) and (10.24) gives, for /R small enough:
	(s ab -s abc ) 2 >	1 128	(η/ ) 3			(10.26)

  n ) is a frame for the 2-plane in linear space spanned by {a, b, c, d} and orthogonal to ab.For a point t ∈ R n , we denote its "coordinates" (x t , z t , Y

t ) ∈ R × R × R d-2 . Where x t = t -m, -→ e n , z t = t -m, -→ n ,

and the vector Y t ∈ R d-2 contains the coordinates in some orthogonal frame of the d -2 linear space orthogonal to -→ e c and -→ n of the component of vector t-o in this linear space: t-o-t-o, -→ e c -→ e c -t-o, -→ n -→ n . The capital Y of the third coordinate Y t are there to emphasizes the fact that it represents d -2 scalar coordinates. Denote by ω = C C (abd) and ω = C C (abd ) the respective circumcenters of abd and abd . Take s

  In fact, in the computation below one has to consider particular cases, when abd is acute and abc nearly co-circular with abd , that follows induction proof.Consider o = a + b -o as in Lemma 10.4. Since the hyper-planeH + ∩ H -is the radical plane of B(o, R C (T )) and B(o , R C (T )),and since abc is obtuse with longest edge ab, one has o ∈ H -\ H + and o ∈ H + \ H -. It follows that we have ∀s ∈ H + , P B(o ,R C (T )) (s) < P B(o,R C (T )) (s) = P abc (s). This together with Lemma 10.4 gives: ∀s ∈ S ∩ H + , P abc (s) ≥ -α

R n we split he proof in proving successively that ∀s ∈ S ∩ H + , P abc (s) ≥ -α Sp and ∀s ∈ S ∩ H -, P abc (s) ≥ -(α(abd) + α ) Sp Now for s ∈ S ∩ H -we uses the induction hypothesis that abd is α(abd)-almost empty and, from Lemma

  And with equation(10.29) this gives:h 2 > ρ 2 + 2x c x ω -αand with equation (10.30) we get: 2x c x ω < α and since x c > 0 and, from the lower bound on triangles heights |x c | > η 2 8 , one has x c > η 2 8 :On another hand, from (10.30) we haveρ 2 = x 2 ω + h 2 > x 2 o + h 2 = R 2 which gives x 2 ω > x 2o and, since x o < 0 and x ω > x o one has:

			-α
	that is:
	x 2 c + y 2
	x ω <	8 η 2 α		(10.31)
	0 ≤ -x o < x ω <	8 η 2 α	(10.32)

c ≥ ρ 2 + 2x c x ω -α

In order to avoid to introduce non essential formal definitions, the coboundary operator is defined over chains since, for finite simplicial complexes, the canonical inner product defines a natural bijection between chains and cochains.

Acknowledgments This work has benefited from many discussions and exchanges on related topics with Dominique Attali, Jean-Daniel Boissonnat and Mathijs Wintraecken.

We have then: Lemma 6.29. Using the notation and context of section 6.10, for two n-chains Γ 1 , Γ 2 ∈ C n (K P ) one has:

Proof. If we denote by → µ = B Γ the set of simplex in Γ with bounding weight equal to µ = B :

We claim that:

Indeed, by definition of the lexicographic order, if this did not holds, it would imply →

Γ 2 which proves the claim (6.51). Note that, from Lemma 6.10 and generic condition 6.2, all the simplices in → and it follows abd, bcd, cad < abc. Consider:

Then, T is homologous to T and is strictly lower for lex :

A contradiction with the definition of T .

Lemma 9.6. If triangles σ 1 , σ 2 ∈ T then:

and if σ ∈ T then either σ is is acute and is the unique triangle in K with same R B (σ) = R C (σ), either σ is obtuse, in which case it is the unique triangle with maximal circumradius among triangles in K with same bounding radius R B (σ).

Proof. In the context of condition 7.1, R B (σ 1 ) = R B (σ 2 ) ⇒ SEB(σ 1 ) = SEB(σ 2 ), and, in order to prove (9.6) it is enough to consider the case when

, σ 1 is acute and we get then a contradiction with Lemma 9.

, σ 1 is obtuse and we get then a contradiction with Lemma 9.5 since if abc = σ 1 and abd

The second part of the Lemma follows similarly from Lemmas 9.3 when σ is acute and from Lemma 9.5 when σ is obtuse.

Observe that we get immediately from Lemma 9.5 and the genericity condition that in T one can not have two obtuse triangles sharing their longest edge. More precisely we have the following: Lemma 9.7. If abc ∈ T is an obtuse triangle with ab its longest edge, then ab is shared by at least another triangle abd in T such that:

• either abd is obtuse with longest edge ad or bd and R C (abc) ≤ R C (abd).

Moreover any triangle abd sharing ab obeys to the same alternative.

Proof. Since ∂T = 0 one has in particular ∂T (ab) = 0:

Since Γ(abc) = 1, there exists at least some triangle abd with d = c and Γ(abd) = 1. If abd is acute, then we have from Lemma 9.3 that c / ∈ SEB(abd) and therefore R C (abc) ≤ R C (abd). Assume now that abd is obtuse. ab can not be the longest edge of abd: indeed if it was we get from the generic condition that either R C (abc) > R C (abd) either R C (abc) < R C (abd), that is, according to (9.5) that either c ∈ SP abd (ab), either d ∈ SP abc (ab), and both cases contradicts Lemma 9.5.

Without loss of generality, we can assume therefore that ad is the longest edge of abd. It remains to prove that in this case one has R C (abc) ≤ R C (abd).

Triangles in minimal chains have almost empty circumspheres

For a ball B(o, R) we denote by P B(o,R) (s) the power of point s with respect to B(o, R):

For a triangle T we denote by P T (s) the power of point s with respect to the circumscribing ball of T :

The proof of Lemma 9.23 is in Appendix E. It proceeds by induction, as in the proof of Lemma 9.17, along the directed acyclic graph given by Corollary 9.8.

Proximity graph G δ of triangle circumcenters

Connected components of G δ are small In this section, for a given δ > 0, we study the proximity graph G δ of circumcenters of triangles in T . For T 1 , T 2 ∈ T , C C (T 1 ) and

Let T 0 ∈ T . Lemma 9.24 below says that for δ small enough, the connected component of C C (T 0 ) in the proximity graph is included in B(C C (T 0 ) , ρ) for ρ < 1 8 η 2 . Lemma 9.24 below is central in the proof of the theorem. The main difficulty is to prove that, locally, the projection on a local tangent plane is injective. More precisely, one have to show that the projection of two triangles on a common nearby tangent plane have disjoint interiors. Thanks to Lemma 9.24 this is done separately for pairs of triangles in separate connected components of G δ (section 9.5.1) and for pairs of triangles in the same connected component (section 9.6).

In section 9.5.1, for triangles in separate connected components we want δ to be significantly larger than the bound given in Lemma 9.21 on the distance between circumcenters and tangent planes in order to guarantee a lower bound on the distance between projections on nearby tangent plane of corresponding circumcenters. For triangles in the same connected component, we need in section 9.6 to upper bound the distances between circumcenters of projections on tangent plane of triangles by , which motivate the value chosen for ρ in Lemma 9.24. Lemma 9.24. Given T 0 ∈ T , for:

We recall here the invariance of domain theorem (Brouwer, Leray ??) used in the proof of Theorem 10.12. For a set E ⊂ R n , span L (E) and span A (E) respectively denotes the linear span and the affine span of E.

F.2 Technical lemmas

Lemmas in this section are used in the proof of Theorem 10.12. Recall that a topological space E is said Hausdorff if: Proof. For a contradiction assume x 1 = x 2 and φ(x 1 ) = φ(x 2 ). Since E is Hausdorff, there are V x 1 and V x 2 respective open neighborhood of x 1 and x 2 such that V Proof. We first check that for R small enough, T and the projections on local tangent plane satisfy the conditions of Theorem 10.14. Observes that , from the bound 2 on the circumradius of triangles in T , U is a subset of the set of triangles having their vertices in S m,R/