David Cohen-Steiner
email: david.cohen-steiner@inria.com

André Lieutier
email: andre.lieutier@gmail.com

Julien Vuillamy
email: julien.vuillamy@3ds.com

Delaunay and regular triangulations as lexicographic optimal chains

Keywords: Delaunay, Regular triangulations, Minimal chains, Lexicographic, Simplicial Mathematics Subject Classification (2010) MSC 52C07, MSC 52C99

We introduce a total order on n-simplices in the n-Euclidean space for which 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. This new characterization of regular and Delaunay triangulations is motivated by its possible generalization to submanifold triangulations as well as the recent development of polynomial-time triangulation algorithms taking advantage of this order.

Introduction

Besides their elegant mathematical properties [11,[START_REF] Aurenhammer | Voronoi diagrams -a survey of a fundamental geometric data structure[END_REF][START_REF] Rajan | Optimality of the Delaunay triangulation in R d[END_REF], Delaunay triangulations, and more generally regular triangulations, are intensively used in the industry, being the basis of much of the meshing algorithms for geometry processing and engineering applications [START_REF] Cheng | Delaunay mesh generation[END_REF].

Related work: regular triangulations and their optimality properties

The usual definition of Delaunay triangulation considers a finite set of points P ⊂ R n that is in general position, by which it is meant that no n + 1 points of P belong to a same hyperplane and no n + 2 points of P belong to a same sphere.

Given a finite set P of at least n + 1 points in R n in general position, the Delaunay triangulation of P is then defined as the set of n-simplices σ ⊂ P whose circumscribed sphere contains no points in P \ σ. Equivalently, it can be defined as the dual of the Voronoi diagram of P. Associating a weight µ i to each point P i in P, the Laguerre-Voronoi diagram of P, alternatively called power diagram, is a generalization of the Voronoi diagram. Its dual is called regular triangulation of the set of weighted points and coincides with the Delaunay triangulation when all weights µ i are equal.

Delaunay triangulations satisfy several optimality criteria. It has been shown [START_REF] Rajan | Optimality of the Delaunay triangulation in R d[END_REF] and [3, section 17.3.4] that "Among all triangulations of a set of points in R 2 , the Delaunay triangulation lexicographically maximizes the minimum angle, and also lexicographically minimizes the maximum circumradii". We call bounding radius of a simplex the radius of the smallest ball containing it. In [3, section 17.3.4], the grain of a triangulation T of points in the plane is defined as the maximum of the bounding radii of all triangles of T . Then [START_REF] Boissonnat | Algorithmic geometry[END_REF]Theorem 17.3.9] asserts that, given a point set P ⊂ R 2 , the Delaunay triangulation minimizes the grain among all triangulations of P. This last fact is also a consequence of our main theorem when the dimension is 2.

The grain minimization property is a necessary but not sufficient condition for a triangulation to be Delaunay. Our result is a strengthening of this property into a necessary and sufficient condition, as well as a generalization to any dimension and to regular triangulations. Even for the significantly simpler situation of 2-dimensional Delaunay, we are not aware of any work giving the strengthening of the grain optimization required to get our sufficient condition.

Our work relies strongly on a variational characterization of Delaunay triangulations obtained in [START_REF] Chen | Optimal delaunay triangulations[END_REF]. It is well known [START_REF] Edelsbrunner | Incremental topological flipping works for regular triangulations[END_REF][START_REF] Boissonnat | Algorithmic geometry[END_REF] that the Delaunay triangulation in R n is equivalent to the lower convex hull of points in R n × R where each point (x 1 , . . . , x n ) ∈ P ⊂ R n is lifted to:

lift (x 1 , . . . , x n ) = def.   x 1 , . . . , x n , n j=1 x 2 j   ∈ P
where P ⊂ R n+1 is the graph of the square norm function. Along this correspondence, a n-simplex {p 0 , . . . , p n } ⊂ P belongs to the Delaunay triangulation in R n if and only if its lifted counterpart {lift p 0 , . . . , lift p n } belongs to the boundary of the lower convex hull of lift P ⊂ P, where "lower" refers to the negative direction on the last coordinate x n+1 . This equivalence extends to regular triangulations where the weighted point ((x 1 , . . . , x n ), µ) ∈ R n × R is now lifted to x 1 , . . . , x n , j x 2 j -µ ∈ R n+1 [START_REF] Edelsbrunner | Incremental topological flipping works for regular triangulations[END_REF][START_REF] Boissonnat | Algorithmic geometry[END_REF].

Starting from this equivalence, Chen and coauthors [START_REF] Chen | Optimal delaunay triangulations[END_REF] observed that Delaunay triangulations minimize, among all triangulations over a given vertex set P, the L p norm of the difference between the squared norm function and its piecewise-linear interpolation on the triangulation (see [START_REF] Cohen-Steiner | Lexicographic optimal homologous chains and applications to point cloud triangulations[END_REF] below for a formal definition). This variational formulation has been successfully exploited [START_REF] Alliez | Variational tetrahedral meshing[END_REF][START_REF] Chen | Efficient mesh optimization schemes based on optimal delaunay triangulations[END_REF][START_REF] Chen | Revisiting optimal delaunay triangulation for 3d graded mesh generation[END_REF] for the generation of Optimal Delaunay Triangulations obtained by optimizing the same functional with respect to the vertex positions in two and three dimensional Delaunay triangulations.

Result and motivation in a few words

We introduce a new variational characterization of Delaunay and regular triangulations. Recall that a k-simplex is a set of k + 1 points or vertices. Given a finite set of points P ⊂ R n , respectively a set of weighted points P ⊂ R n × R, in general position, we define a specific total order σ 0 < . . . < σ N -1 on the set of n-simplices with vertices in P. This order allows to compare sets of simplices by comparing the sum of simplex weights, where the weight of simplex σ i is 2 i . This total order on sets of n-simplices, induced by the total order on simplices, is called lexicographic order.

A simplicial k-chain, whose formal definition is recalled in Section 2, is a set of k-simplices behaving as a vector over Z 2 , the field of integers modulo 2, when the addition is defined as the set-theoretic symmetric difference:

Γ 1 + Γ 2 = (Γ 1 ∪ Γ 2 ) \ (Γ 1 ∩ Γ 2 ).
The lexicographic comparison of two chains, or, merely, of two sets of simplices, can equivalently be defined as follows. We say that Γ 1 is less than Γ 2 , in lexicographic order, and we write Γ 1 lex Γ 2 , if Γ 1 = Γ 2 or if the maximal simplex in their symmetric difference is in Γ 2 . In other words, for Γ 1 = Γ 2 :

Γ 1 lex Γ 2 ⇐⇒ max σ ∈ (Γ 1 ∪ Γ 2 ) \ (Γ 1 ∩ Γ 2 ) ∈ Γ 2
The main result of this work (Theorem 1) asserts that the Delaunay, respectively regular, triangulation of P, is the minimal simplicial chain for the lexicographic order, among chains whose boundary coincides with the boundary of the convex hull of P.

The formal statement of Theorem 1 is given in Section 3 after the exposition of some prerequisites.

The definition of the total order we use for comparing simplices might not seem very intuitive. It is introduced progressively, in Section 3.2 for 3dimensional Delaunay, then in Section 3.5 for the general case of Delaunay or regular triangulation in any dimension n ≥ 1. In the case of Delaunay triangulation in the plane, the comparison ≤ between two triangles, T i , i = 1, 2 is defined as follows.

We denote by R B (T i ) the bounding radius of T i , which is the radius of the smallest circle containing T i and by R C (T i ) the radius of the circumcircle of

Acute triangle

Obtuse triangle

R B = R C R C R B
Fig. 1 The triangle bounding radius R B is the radius of the smallest enclosing circle. Triangles bounding radius R B and circumradius R C characterize the order among 2-simplices.

T i , or circumradius (see Figure 1). These two radii coincide when T i is acute.

In order to compare T 1 and T 2 we first compare R B (T 1 ) and R B (T 2 ):

R B (T 1 ) < R B (T 2 ) ⇒ T 1 ≤ T 2
In case of equality, which arises generically in case of two obtuse triangles sharing their longest edge, the tie is broken by comparing R C (T 1 ) and R C (T 2 ), in reverse order:

R B (T 1 ) = R B (T 2 ) and R C (T 1 ) > R C (T 2 ) ⇒ T 1 ≤ T 2
In the particular case of dimension 2 and zero weights, using this particular total order on triangles, Theorem 1 asserts that the 2D Delaunay triangulation is the lexicographic minimum under boundary condition.

Our result characterizes regular triangulations as solutions of a particular linear programming problem over Z 2 that can be computed in polynomial time, by simple matrix reduction algorithms [START_REF] Cohen-Steiner | Lexicographic optimal homologous chains and applications to point cloud triangulations[END_REF][START_REF] Vuillamy | Simplification planimétrique et chaînes lexicographiques pour la reconstruction 3D de scènes urbaines[END_REF]. However, we do not expect such algorithms to compete with existing algorithms for the computation of Delaunay or regular triangulation in Euclidean space.

Instead, the characterization given by Theorem 1, being concise and linear by nature, enable generalizations beyond the situation of Delaunay or regular triangulation [START_REF] Cohen-Steiner | Lexicographic optimal homologous chains and applications to point cloud triangulations[END_REF][START_REF] Vuillamy | Simplification planimétrique et chaînes lexicographiques pour la reconstruction 3D de scènes urbaines[END_REF]. This is illustrated by an example of application in section 1.3. Also, we believe that our algebraic flavored characterization, by offering a novel perpective on a classical notion, may stimulate further theoretical research as well as applications.

Regular triangulations on curved objects

Our initial motivation for this work was the design of meshing algorithms for manifolds or stratified sets, typically 2-submanifolds of the Euclidean 3-space [START_REF] Cohen-Steiner | Lexicographic optimal homologous chains and applications to point cloud triangulations[END_REF][START_REF] Vuillamy | Simplification planimétrique et chaînes lexicographiques pour la reconstruction 3D de scènes urbaines[END_REF]. When the submanifold is known through a point set sampling, possibly Fig. 2 Our variational formulation, defining Delaunay triangulations when applied to nchains in ambient R n , can be extended to k-chains in R n . This is illustrated here for k = 2 and n = 3. The boundary constraint β of ( 1) is the set of edges connecting the red dots.

with outliers, the computation of such a triangulation is known as surface reconstruction, or, when the ambient dimension is high, manifold learning.

In this context, we would like our triangulations to benefit from the same quality and optimality properties enjoyed by the Delaunay triangulation in Euclidean space and to be able to ignore outliers. A natural idea, in order to extend Delaunay or regular triangulations to this general situation, consists in using the same variational formulation of Theorem 1, but considering k-chains in R n for k < n instead of n-chains in R n .

The case n = 3 and k = 2 is illustrated on Figure 2 which shows triangulated surfaces made of the triangles in Γ min , the lexicographic minimal 2-chains in R 3 under imposed boundary, where the total order ≤ on triangles is the one given in Section 1.2:

Γ min = min lex Γ ∈ C 2 (K), ∂Γ = β .
(

For ease of computation we can take K to be the 3D Delaunay triangulation of the data points rather than the full complex. We first see that the support of the minimal chain is a manifold. It has in fact been proved [START_REF] Cohen-Steiner | Lexicographic optimal chains and manifold triangulations[END_REF] that given a connected compact smooth 2-submanifold of Euclidean space, under good sampling conditions relatively to the reach of the manifold and starting from a well chosen Čech or Rips simplicial complex over the points sample, the support of the lexicographic minimal cycle non-homologous to 0 has to be a triangulation of the manifold. We also see that the quality and arrangement of triangles in the obtained surface triangulation is, as expected, similar to that of planar Delaunay triangulations, making our approach a good candidate for extending the notion of Delaunay (or regular) triangulation to sampled curved objects.

Organization of the paper

The paper is devoted to the proof of Theorem 1.

Section 2 recalls standard definitions about simplicial complexes and chains, regular triangulations of weighted points, and states the formal definition of the lexicographic order. Section 3 states our main result.

Section 4 establishes geometric constructions of regular triangulations, with an emphasis on properties of their simplex links. A characterization of regular triangulations is given in terms of the support of a chain minimizing a weighted L 1 norm, denoted • (p) , under boundary constraints (Proposition 2). The weights in the norm • (p) are parametrized by a real number p ≥ 1. Lemmas 4 and 5 imply that, informally, for p large enough, a chain minimizing • (p) under boundary constraints minimizes in particular a lexicographic preorder induced by the comparison of bounding radii µ B of simplices.

Sections 4.2 and 4.3 describe a geometric construction that maps the link of a k-simplex τ in the regular triangulation to a polytope in R n-k . It establishes correspondences between properties of the link of τ with properties of the polytope, which are summarized in Lemma 7. In this section are defined several geometric objects used along the proof, such as the bisector bis τ of a simplex τ , the associated maps π bisτ , π τ , Φ τ , and Sh τ , and the notion of visible facet of a polytope.

Section 5 is self-contained and does not rely on previous constructions. It is devoted to the proof of Lemma 10, which establishes that convex hulls can be defined as minimal lexicographic chains under boundary constraints, for a particular lexicographic order denoted 0 . This lemma is a crucial tool for the proof of the main theorem.

Finally, in section 6, we are ready to give the proof of Theorem 1.

The proof of the theorem requires many constructions, notations and intermediate results. In order to help the reader, we provide in Appendix A a proof outline, with two flowcharts and associated explanations. This proof outline is not self contained: it is meant to serve as a roadmap that, by giving a global view of the proof, may support the reader along sections 4, 5 and 6. It is completed by a glossary, Section A.4, of the main notions used in the proof outline.

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

Simplicial complexes, simplicial chains and lexicographic order

We recall here basic definitions of simplicial complexes and chains. A thorough exposition can be found in the first chapter of [START_REF] Munkres | Elements of algebraic topology[END_REF].

Simplicial complexes

Simplicial complexes For any k ≥ 0, a simplex of dimension k, or k-simplex, is a set of k + 1 vertices. If τ and σ are simplices, we say that τ is a face of σ, or, equivalently, that σ is a coface of τ , when τ ⊆ σ.

A set K of simplices is called a simplicial complex if any σ ∈ K has all its faces in K:

σ ∈ K and ∅ = τ ⊆ σ ⇒ τ ∈ K
We consider in this paper only finite sets K, i.e. only finite simplicial complexes. The dimension of a simplicial complex is the maximal dimension of its simplices. If any simplex in a n-dimensional simplicial complex K has at least one coface of dimension n, K is said to be a pure simplicial complex. Given a simplicial complex K, we denote by K [k] the subset of K containing all k-simplices of K.

Stars and Link

For a simplex τ ∈ K, the star of τ in K, denoted St K (τ ) is defined by St K (τ ) = {σ ∈ K, σ ⊇ τ } and the link of τ in K, denoted Lk K (τ ) is defined by Lk K (τ ) = {σ ∈ K, σ ∪ τ ∈ K and σ ∩ τ = ∅}. When, for 0 ≤ k < n, τ is a k-simplex in a pure n-dimensional simplicial complex K, the link Lk K (τ ) of τ in K is a (n -k -1)-dimensional pure simplicial complex.
Embedded simplicial complexes and geometric realization Given a k-simplex σ = {v 0 , . . . v k }, where each vertex v i , 0 ≤ i ≤ k belongs to R N for some N ≥ k such that the points {v 0 , . . . v k } are affinely independent, the convex hull of σ, denoted CH (σ), is called a geometric k-simplex.

Given a n-dimensional simplicial complex K, an embedding of K consists in associating to each vertex in K a point in R N such that: 1 1. for any k-simplex τ ∈ K, the points associated to the vertices of τ are affinely independent, 2. for any pair of simplices σ 1 , σ 2 ∈ K, one has:

CH (σ 1 ) ∩ CH (σ 2 ) = CH (σ 1 ∩ σ 2 ) ,
The geometric realization G(K) ⊂ R N of K is then defined as:

G(K) = σ∈K CH (σ)
In the sequel of the paper, we consider several n-dimensional simplicial complexes whose vertices belong to R n . For example, given four points a, b, c, d in general position in R 2 , the simplicial complex made of the triangles in the

1 If the simplicial complex K contains N vertices v 1 , . . . v N , associating to vertex v i the point ṽi ∈ R N whose j th coordinate is: (ṽ i ) j = 1 if j = i 0 else
gives an embedding of K in R N and the induced canonical geometric realization defines the topological space associated to the simplicial complex K. It is homeomorphic to any other geometric realization of K.

Delaunay triangulation of {a, b, c, d}, together with all their faces, is a simplicial complex embedded in R 2 . By contrast, the full 2-dimensional simplicial complex over a, b, c, d, defined as the simplicial complex made of all possible triangles, {abc, abd, bcd, acd} with all their faces, is not embedded in R 2 , regardless of the configurations of points a, b, c, d. We mention that if K is a full simplicial complex, so is the link Lk K (τ ) of one of its simplex τ ∈ K. If the geometric realization G(K) of K is a nmanifold, then the geometric realization of Lk K (τ ), G(Lk K (τ )), is a (n-k-1)sphere.

Simplicial chains

Let K be a simplicial complex of dimension at least k. 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. Denoting by K [k] the set of k-simplices in K, a k-chain Γ with coefficients in Z 2 is a formal sum of k-simplices:

Γ = i x i σ i , with x i ∈ Z 2 and σ i ∈ K [k]
(2)

Interpreting the coefficient x i ∈ Z 2 = {0, 1} in front of simplex σ i as indicating the existing of σ i in the chain Γ , we can view the k-chain Γ as a set of k-simplices: for a k-simplex σ and a k-chain A, we write that σ ∈ Γ if the coefficient for σ in Γ is 1. With this convention, the sum of two chains corresponds, when chains are seen as set of simplices, to their set-theoretic symmetric difference. For a k-chain Γ and a k-simplex σ, we denote by Γ (σ) ∈ Z 2 the coefficient of σ in Γ , in other words:

Γ (σ) = 1 Z2 ⇐⇒ σ ∈ Γ.
We denote C k (K) the vector space over the field Z 2 of k-chains in the complex K.

For a k-chain Γ in C k (K), we denote by |Γ | the support of Γ , which is the subcomplex of K made of all k-simplices in Γ together with all their faces.

Boundary operator.

In what follows, a k-simplex σ can also be interpreted as the k-chain containing only the k-simplex σ, which is consistent with the notation in [START_REF] Aurenhammer | Voronoi diagrams -a survey of a fundamental geometric data structure[END_REF]. Since the set of k-simplices K [k] is a basis for C k (K), a linear operator on C k (K) is entirely defined by its image on each simplex.

For a k-simplex σ = {v 0 , . . . , v k }, the boundary operator ∂ k is the linear operator defined as:

∂ k : C k (K) → C k-1 (K) ∂ k σ = def. k i=0 [v 0 , . . . , v i , ...v k ]
where the symbol v i means the vertex is deleted from the set.

A k-cycle is a k-chain with null boundary. We say two k-chains Γ and Γ are homologous if their difference (or equivalently their sum) is a boundary, in other words, if Γ -Γ = ∂ k+1 B, for some (k + 1)-chain B.

Regular triangulations of weighted points

Definition 1 generalizes the square of Euclidean distance to weighted points.

Definition 1 (Section 4.4 in [4]

) 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 (3)
We recall now the definition of a regular triangulation over a set of weighted points. Regular triangulations can alternatively be defined as duals of the Laguerre (or power) diagrams of a set of weighted points. We use here a generalization of the empty sphere property of Delaunay triangulations.

Definition 2 (Lemma 4.5 in [4])

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 , denoting (P C (σ), µ C (σ)) (Definition 7) the generalized circumsphere of σ, then:

(P i , µ i ) ∈ P \ σ ⇒ D (P C (σ), µ C (σ)), (P i , µ i ) > 0 ( 4
)
Definition 4 is equivalent to the definition of a Delaunay triangulation when all weights are equal. Notice the strict inequality in [START_REF] Boissonnat | Geometric and topological inference[END_REF], where the usual definition would use a greater or equal inequality instead. However, the equality case will not occur under the generic condition assumed in Section 3.

Lexicographic order

We assume now a total order on the k-simplices of K, σ 1 < ... < σ N , where N = dim C k (K). From this order, we define a lexicographic total order on kchains. Recall that with coefficients in Z 2 for k-chains Γ 1 , Γ 2 ∈ C k (K), we can use interchangeably vector and set-theoretic operations:

Γ 1 + Γ 2 = Γ 1 -Γ 2 = (Γ 1 ∪ Γ 2 ) \ (Γ 1 ∩ Γ 2 ).
Definition 3 (Lexicographic Order on chains) Assume there is a total order ≤ on the set of k-simplices of K. For Γ 1 , Γ 2 ∈ C k (K):

Γ 1 lex Γ 2 ⇐⇒ def.      Γ 1 = Γ 2 or max {σ ∈ Γ 1 + Γ 2 } ∈ Γ 2
The lexicographic order can equivalently be defined as a comparison of L 1 norm for a particular choice of simplices weights. For that, the d-simplices being totally ordered as σ 0 < σ 1 < . . . < σ N -1 , we assign the weight 2 i to simplex σ i . We can then define the norm of a d-chain Γ = j c j σ j were c j ∈ Z 2 as:

Γ * = j c j σ j * = j |c j | 2 j
where |.| : Z 2 → {0, 1} ⊂ R assigns respective real numbers 0 and 1 to their corresponding elements in Z 2 = {0 Z2 , 1 Z2 }, i.e. |0 Z2 | = 0 and |1 Z2 | = 1. Another way of saying this is to associate to each k-chain Γ ∈ C k (K) the integer number whose j th bit in the binary expression, starting from the least significant bit, corresponds to the coefficients of σ j in Γ . Then Γ * is the value of the integer number. With this convention one has:

Γ 1 lex Γ 2 ⇐⇒ Γ 1 * ≤ Γ 2 *

Main result

This section gives the main result of the paper, Theorem 1, before entering into more technical matters. Both the generic condition and the total order on simplices inducing the lexicographic order are formally defined in Section 3.4.

These formal definitions do not provide an easy visual intuition, being inductive by nature and expressed for the general case of weighted points. For this reason, we first provide an intuitive introduction in the case of zero weights, which corresponds to Delaunay triangulations.

Generic configurations

In computational geometry, a property defined on a space of configuration parametrized by R N is usually said generic when the set G ⊆ R N for which it holds is open and dense in R N . Another legitimate definition for a property to be generic is to hold almost everywhere, in other words such that R N \ G has Lebesgue measure zero.

Definition 4 (Generic property)

We say that a property on a space of configuration parametrized by R N satisfied on G ⊆ R N is generic, if G is an open dense subset whose complement has Lebesgues measure zero.

Note that the conjunction of finitely many generic conditions is generic. In the case of the Delaunay triangulation of m points in R n , the configuration space has dimension N = mn, and, for regular triangulations of m weighted points in R n × R, the dimension is N = m(n + 1).

In the context of applications, as a consequence of some symmetries in the input or from the finite representations by floating point numbers, the probability to encounter a non-generic configuration with real world data is not zero and practical implementations simulate generic configurations by breaking ties artificially, typically by symbolic perturbation (see Simulation Of Simplicity in [START_REF] Edelsbrunner | Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms[END_REF]). Section I provides a more detailed discussion of the generic conditions 1 (Section 3.4) and 2 (Section 5), including the proofs that they are indeed generic.

3.2 Order ≤ on simplices for Delaunay triangulations in R 2 and R 3 .

The following definitions of total orders on simplices of two and three-dimensional Delaunay triangulations should be seen as particular cases of Definition (9) in Section 3.5.

2-dimensional Delaunay triangulations

For 2-dimensional Delaunay triangulations, the total order defined by ( 9) has already been introduced in Section 1.2. Denoting respectively R B (T ) and R C (T ) the bounding radius, radius of the smallest circle containing triangle T , and the circumradius of T (see figure 1), the order on triangles is defined as:

T 1 ≤ T 2 ⇐⇒                T 1 = T 2 or R B (T 1 ) 2 < R B (T 2 ) 2 or R B (T 1 ) 2 = R B (T 2 ) 2 and R C (T 1 ) 2 > R C (T 2 ) 2
This preorder is a total order under our generic condition. Compared to Section 1.2, we have here used squared radii comparisons instead of radii comparisons. This obviously does not change the ordering, but makes the expression consistent with the general definition (9) since, for 2-dimensional Delaunay triangulations, one has µ 0 (T ) = R B (T ) 2 and µ 1 (T ) = R C (T ) 2 .

3-dimensional Delaunay triangulations

Given a non-degenerate tetrahedron σ = abcd in R 3 , it must belong to one of the three categories illustrated on Figure 3. This category depends on the dimension of Θ(σ), which is, under generic condition, the unique lowest dimensional face of σ with the same bounding radius as σ.

Equivalently, Θ(σ) is the unique face of σ such that R B (σ) = R C (Θ(σ)).
For all three categories, we define µ 0 (σ) as the squared bounding radius of the simplex σ:

µ 0 (σ) = R B (σ) 2 .
For the second category, in the middle of Figure 3, corresponding to Θ(σ) = abc, we define moreover µ 1 (σ) = R C (σ) 2 which is the squared radius of the circumscribing sphere. For the third category, on the right of Figure 3, corresponding to

Θ(σ) = abcd = σ Θ(σ) = abc Θ(σ) = ab
Θ(σ) = ab, we define µ 1 (σ) = min(R C (abc), R C (abd)) 2 and µ 2 (σ) = R C (σ) 2 .
The total order ≤ on tetrahedra is then defined as:

σ 1 ≤ σ 2 ⇐⇒                        σ 1 = σ 2 or µ 0 (σ 1 ) < µ 0 (σ 2 ) or µ 0 (σ 1 ) = µ 0 (σ 2 ) and µ 1 (σ 1 ) > µ 1 (σ 2 ) or µ 0 (σ 1 ) = µ 0 (σ 2 ) and µ 1 (σ 1 ) = µ 1 (σ 2 ) and µ 2 (σ 1 ) > µ 2 (σ 2 )
Note that µ 1 and µ 2 are not defined for all kinds of tetrahedra. However, the equality configurations requiring the definitions of the quantities µ 1 and µ 2 only arise when the category of the triangles allows to define these quantities. As an example, if the tetrahedron σ 1 is from the first category (Θ(σ) = abcd), then µ 0 (σ 1 ) = R B (σ 1 ) = R C (σ 1 ). Under our generic condition, there cannot be another simplex with same circumradius as σ 1 , and therefore, no tetrahedron with same bounding radius. It follows that in this case σ 1 is the only tetrahedron with bounding radius R B (σ 1 ):

σ 1 = σ 2 ⇒ R B (σ 1 ) = R B (σ 2 ).

The theorem

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

The aim of this paper is to prove Theorem 1 below, where the relation lex among n-chains is the lexicographic order defined according to Definition 3, the total order on n-simplices is given by ( 9) and the general position assumption is a generic condition formalized in Condition 1 of Section 3.4. Definition 5 (Full simplicial complex) Given a finite set P, the n-dimensional full simplicial complex over P, denoted K P , is the simplicial complex made of all possible simplices up to dimension n with vertices in P.

Recall that, as explained in Section 2.2, a chain with coefficients in Z 2 is identified to the set of simplices for which the coefficient is 1.

Theorem 1 Let P = {(P 1 , µ 1 ), . . . , (P N , µ N )} ⊂ R n × R, with N ≥ n + 1,
be weighted points in general position and K P the n-dimensional full simplicial complex over P. Denote by β P ∈ C n-1 (K P ) the (n-1)-chain, set of simplices belonging to the boundary of the convex hull CH (P).

Then the simplicial complex |Γ min | support of

Γ min = min lex Γ ∈ C n (K P ), ∂Γ = β P
is the regular triangulation of P.

When all the weights µ i are equal, the regular triangulation (Definition 2) is the Delaunay triangulation.

Obviously, replacing in Theorem 1 the full simplicial complex K P by any complex containing the regular triangulation would again give this triangulation as a minimum.

Generic condition and simplex order, the formal definition

Definition 6 (Degenerate simplex) A k-simplex σ = (P 0 , µ 0 ), . . . , (P k , µ k ) is said to be degenerate if the set P 0 , . . . , P k is included in some (k -1)dimensional affine space.

Note that if a k-simplex is non-degenerate, neither are any of its faces of dimension k < k.

As Definition 1 generalizes the squared Euclidean distance to weighted points, we now define the respective generalizations of squares of both circumradius and smallest enclosing ball radius, to sets of weighted points. Definition 7 (P C , µ C , P B , µ B ) Given a non-degenerate 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:

µ C (σ) = def. min µ ∈ R, ∃P ∈ R n , ∀(P i , µ i ) ∈ σ, D ((P, µ), (P i , µ i )) = 0 (5) µ B (σ) = def. min µ ∈ R, ∃P ∈ R n , ∀(P i , µ i ) ∈ σ, D ((P, µ), (P i , µ i )) ≤ 0 (6) P C (σ) (respectively P B (σ))
is the unique point P that realizes the minimum in Equation ( 5) (respectively ( 6)).

Note that, since σ is non-degenerate, (P, µ), ∀(P i , µ i ) ∈ σ, D ((P, µ), (P i , µ i )) = 0 = ∅, so that the minimum in ( 5) is well defined and finite.

The weights µ C (σ) and µ B (σ) are called respectively circumweight and bounding weight of σ.

In the Delaunay case where weights are zero, µ C (σ) and µ B (σ) correspond respectively to the square of the circumradius and the square of the radius of the smallest ball enclosing σ, as depicted on Figure 1, while P C (σ) and P B (σ) are the respective circles centers.

We give now the condition required in Theorem 1, for the general case, which, as explained in Section 3.1, is generic and can be handled by standard symbolic perturbation.

Generic condition 1

We say that P = (P 1 , µ 1 ), . . . ,

(P N , µ N ) ⊂ R n × R is in general position if it does not contain any degenerate n-simplex, and if, for a k-simplex σ and a k -simplex σ in K P with 2 ≤ k, k ≤ n, one has: µ C (σ) = µ C (σ ) ⇒ σ = σ (7)
We have the following observation deduced from Definitions 1 and 7:

Observation 2 If the weights of all points in P are assumed non-positive, then, under the generic condition 1, one has µ C (τ ) > 0 and µ B (τ ) > 0 for any simplex τ .

From now on, we assume P to be in general position i.e. it satisfies generic condition 1.

The next lemma assigns to any simplex σ a face Θ(σ) which is inclusion minimal among the faces of σ sharing the same generalized smallest enclosing ball as σ (see Figure 3).

Lemma 1 (Proof in Appendix C) Under generic condition 1 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 )(Θ(σ)).
Figure 3 illustrates the possibilities for Θ(σ) in the case n = 3 and zero weights. In general, Θ(σ) can even be of dimension 0 (a single vertex) but this cannot happen with zero weights.

We will need the following lemma:

Lemma 2 For any k-simplex σ ∈ K P , one has P B (σ) ∈ CH (Θ(σ)).
Proof We claim first that, for any simplex σ, one has

P B (σ) ∈ CH (σ). If σ = {(P 0 , µ 0 ), . . . , (P k , µ k )}, CH (σ)
is the convex hull of {P 0 , . . . , P k }. If P / ∈ CH (σ) the projection of P on CH (σ) decreases the weighted distance from P to all the vertices of σ, which shows that (P, µ) cannot realize the arg min in [START_REF] Chen | Optimal delaunay triangulations[END_REF]. This proves the claim. Since by definition of Θ(σ) (Lemma 1) one has P B (σ) = P B (Θ(σ)), the lemma follows by applying the claim to the simplex Θ(σ).

Total order on simplices: the general case

In this section, we provide the general definition of the total order on simplices that has been made explicit in Section 3.2 in the particular case of Delaunay triangulations in R 2 and R 3 .

For a n-simplex σ and k such that 0 ≤ k ≤ dim(σ) -dim(Θ(σ)) we define the (k + dim(Θ(σ)))-dimensional face Θ k (σ) as follows.

For

k = 0, Θ 0 (σ) = Θ(σ), where Θ(σ) is defined in Lemma 1. 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 (τ ) (8)
and

µ k (σ) is the circumweight of Θ k (σ): µ k (σ) = µ C (Θ k (σ)). In particular, µ 0 (σ) = µ C (Θ(σ)) = µ B (σ) (by Lemma 1) and if k = dim(σ) -dim(Θ(σ)) then µ k (σ) = µ C (σ).
Observe that, thanks to generic condition 1 and Lemma 1, one has, for two n-simplices σ 1 , σ 2 :

µ B (σ 1 ) = µ B (σ 2 ) ⇒ Θ(σ 1 ) = Θ(σ 2 ). 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 order relation on n-simplices (recall that µ 0 (σ) = µ B (σ)):

σ 1 ≤ σ 2 ⇐⇒ def. σ 1 = σ 2 or          µ 0 (σ 1 ) < µ 0 (σ 2 ) or ∃k ≥ 1, µ k (σ 1 ) > µ k (σ 2 ) and ∀j, 0 ≤ j < k, µ j (σ 1 ) = µ j (σ 2 ) (9)
One can check that when P is in general position, the relation ≤ is a total order.

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 ). This is enough to induce, generically, an order on acute triangles. But obtuse triangles could generically share their longest edge and therefore have same bounding radius. 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 ).
By Definition 3, and under generic Condition 1, the total order ≤ on nsimplices induces a lexicographic total order lex on the n-chains of K P .

Observation 3 From the definition of the order on simplices, the lexicographic minimum is invariant under a global translation of the weights by a common shift s: ∀i, µ i ← µ i + s. (as explicitly explained in Observation 8 in Appendix B). The same holds for regular triangulations. Therefore proving Theorem 1 for non-positive weights is enough to extend it to any weights.

Some geometric properties of regular triangulations

Lifts of weighted points and p-norms

Given a weighted point (P, µ) ∈ R n × R, its lift with respect to the origin O ∈ R n , denoted by lift(P, µ), is a point in R n × R given by: lift(P, µ) = def.

(P -O), (P -O) 2 -µ , and, for a set of weighted points P = (P 1 , µ 1 ), . . . ,

(P N , µ N ) ⊂ R n × R, lift(P) = lift(P 1 , µ 1 ), . . . , lift(P N , µ N ) ⊂ R n × R.
Similarly to Delaunay triangulations, it is a well known fact that simplices of the regular triangulation of P are in one-to-one correspondence with the lower convex hull of lift(P): Proposition 1 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).

Based on this lifted paraboloid formulation, the idea of variational formulation for Delaunay triangulations has emerged [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.

We define a function on the convex hull of a k-simplex f σ : CH (σ) → R where σ = {(P 0 , µ 0 ), . . . , (P k , µ k )} as the difference between the linear interpolation of the height of the lifted vertices and the function x → (x -O) 2 . More precisely, for a point x ∈ CH (σ) 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 (10)
A short computation shows that the function f σ , expressed in terms of barycentric coordinates, is invariant by isometry (translation, rotation or symmetry on σ). In particular f σ (x) does not depend on the origin O of the lift. It follows from Proposition 1 that, if σ reg is a simplex containing x in the regular triangulation of P, for any other simplex σ containing x with vertices in P:

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

w p (σ) = def. f σ p = CH(σ) f σ (x) p dx 1 p ( 12
)
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 (13)
In this last equation, the notation |Γ (σ)| instead of Γ (σ) is there since Γ (σ) ∈ Z 2 and the sum is in R. For this reason, we used the map |.| : Z 2 → {0, 1} ⊂ R, that assigns respective real numbers 0 and 1 to their corresponding elements in

Z 2 = {0 Z2 , 1 Z2 }, i.e. |0 Z2 | = 0 and |1 Z2 | = 1.
Formally, we have the following Proposition 2 that characterizes regular triangulations as a linear programming problem over Z 2 .

Proposition 2 Let P = {(P 1 , µ 1 ), . . . , (P N , µ N )} ⊂ R n ×R, with N ≥ n+1 be in general position with non-positive weights, and let K P be the n-dimensional full simplicial 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) and by Γ reg the n-chain defined by the set of nsimplices in the regular triangulation of P. Then, for any p ∈ [1, ∞), one has:

Γ reg = arg min Γ ∈Cn(K P ) ∂Γ =β P Γ (p) (14)
The proof of this proposition requires the next lemma. We consider points in the convex hull of P that do not belong to the convex hull of any (n-1)-simplex in K P , i.e. x ∈ CH (P)

\ σ∈K [n-1] P CH (σ). Note that σ∈K [n-1] P CH (σ), finite
union of convex hulls of (n -1)-simplices in R n , has Lebesgue measure 0. Let Γ ∈ C n (K P ) be such that:

∂Γ = β P If x ∈ CH (P)
does not belong to the convex hull of any (n -1)-simplex, then there is an odd number of n-simplices σ ∈ Γ such that x ∈ CH (σ).

Proof (Proof of Proposition 2) Note that the minimum in the right hand side of ( 14) 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) (15)
Indeed, ( 12) and ( 13) gives:

Γ (p) = σ∈Γ CH(σ) f σ (x) p dx = CH(P) σ∈Γ CH(σ) x f σ (x) p dx
We get:

Γ (p) = CH(P)\ σ∈K [n-1] P CH(σ) σ∈Γ CH(σ) x f σ (x) p dx ( 16
)
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 ∈ CH (σ) ∩ CH (σ reg ) ⇒ f σreg (x) ≤ f σ (x) (17)
According to Lemma 3, in [START_REF] Rajan | Optimality of the Delaunay triangulation in R d[END_REF], there is an odd number of simplex σ ∈ Γ satisfying CH (σ)

x in the condition. It follows that the condition has to hold for at least one simplex σ.

Therefore [START_REF] Rockafellar | Convex analysis[END_REF] gives:

x ∈ CH (σ reg ) ⇒ f σreg (x) p ≤ σ∈Γ CH(σ) x f σ (x) p ( 18
)
Since for x ∈ CH (P) \ σ∈K [n-1] P CH (σ) there is exactly one simplex σ reg such that CH (σ reg ) x , ( 18) can be rewritten as:

σ∈Γreg CH(σ) x f σ (x) p ≤ σ∈Γ CH(σ) x f σ (x) p (19)
which, together with [START_REF] Rajan | Optimality of the Delaunay triangulation in R d[END_REF] gives the claim [START_REF] Munkres | Elements of algebraic topology[END_REF]. Now, if some n-simplex σ ∈ Γ with CH (σ) x, for some x ∈ CH (P)

\ σ∈K [n-1] P CH (σ), is not Delaunay, then σ∈Γreg CH(σ) x f σ (x) p = f σreg (x) p < CH(σ) x f σ (x) p
and since the function is continuous, this implies Γ (p) > Γ reg (p) .

Lemma 4 (Proof in Appendix E) One has:

sup x∈CH(σ) f σ (x) = µ B (σ) ( 20
)
The following is an immediate consequence used in the proof of Lemma 5:

lim p→∞ w p (σ) = w ∞ (σ) = f σ ∞ = sup x∈CH(σ) f σ (x) = µ B (σ) (21)
Lemma 5 Let P = {(P 1 , µ 1 ), . . . , (P N , µ N )} ⊂ R n × R, with N ≥ n + 1, be in general position with non-positive weights. Let K P be the corresponding ndimensional full simplicial complex. For p large enough, the weight w p (σ) p of any n-simplex σ ∈ K P , is larger than the sum of the weights of all n-simplices in K P with smaller bounding weight µ B . In other words, denoting by K

[n]

P 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 weights (respectively squared radii for the Delaunay case) of n-simplices in K P :

ι = min σ 1 ,σ 2 ∈K [n] P µ B (σ 1 )<µ B (σ 2 ) µ B (σ 2 ) µ B (σ 1 )
One has ι > 1. Choose ι such that 1 < ι < ι. For any n-simplex σ ∈ K

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

p→∞ w p (σ) = µ B (σ),
it follows that, since there is only finitely many simplices in K

[n] P , that there exists some p 0 large enough such that for any p > p 0 one has:

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

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

As explained in the proof of the main theorem of Section 6, Lemma 5 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 (Sections 4.2 and 4.3).

Projection on the bisector of a simplex

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

Given a k-simplex τ , we denote by bis τ the (n-k)-dimensional affine space bisector of τ , formally defined as: In the particular case where τ is a vertex, i.e. dim(τ ) = 0, one has bis τ = R n .

bis τ = def. x ∈ R n | ∀v 1 , v 2 ∈ τ, D ((x, 0), v 1 ) = D (x, 0), v 2 . ( 22
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: Let o τ = P C (τ ) ∈ bis τ denote the circumcenter of τ (or, for weighted points, the generalized circumcenter as defined in Definition 7, page 13). If

π τ (P, µ) = def. π bisτ (P ), µ -d(P, bis τ ) 2 . ( 23
)
Φ τ (d) Φ τ (c) Φ τ (τ ) Φ τ (x, 0) = π bisτ (x) -o τ , (x -o τ ) 2 z = x 2 π τ (τ ) o τ
(P i , µ i ) ∈ τ , then D ((o τ , µ C (τ )), (P i , µ i )) = 0.
Since o τ = π bisτ (P i ) we have: It follows that if we denote µ(π τ (P i , µ i )) the weight of π τ (P i , µ i ), one has:

(P i -o τ ) 2 -µ i -µ C (τ ) = d(P, bis τ ) 2 -µ i -µ C (τ ) = 0 a b c d Φ τ (d) Φ τ (c) Φ τ (τ ) Sh τ (c, 0) z = x 2 o τ
µ(π τ (P i , µ i )) = µ i -d(P, bis τ ) 2 = -µ C (τ )
Therefore, π τ sends all vertices of τ to a single weighted point:

(P i , µ i ) ∈ τ ⇒ π τ (P i , µ i ) = (o τ , -µ C (τ )) (24)
Lemma 6 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 Under our 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 (25) ∀(P i , µ i ) ∈ P \ σ, D ((P C (σ), µ C (σ)), (P i , µ i )) > 0 (26)
Observe that, since τ ⊂ σ, (25) implies:

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

P C (σ) ∈ bis τ ( 27
)
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 ) (28)
In the last two lines, the weighted distance is denoted D bisτ instead of D in order to stress that, thanks to (27) , it occurs on weighted point of bis τ × R rather than R n × R. Therefore (25) and ( 26) are equivalent to:

∀(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).

An immediate consequence of Lemma 6 is:

Corollary 1 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

π τ (τ ) = {(o τ , -µ C (τ ))
} is a vertex of the regular triangulation of π τ (P), 2. if τ is in the regular triangulation of P, π τ induces a simplicial isomorphism between the link of τ in the regular triangulation of P and the link of vertex π τ (τ ) in the regular triangulation of π τ (P).

Polytope and shadow associated to a link in a regular triangulation

In this section, we study the link of a k-simplex τ in the regular triangulation of P that satisfies:

(P B , µ B )(τ ) = (P C , µ C )(τ ) (29)
Equivalently, we assume Θ(τ ) = τ and in this case both generalized smallest enclosing sphere and generalized circumsphere of τ coincide so that o τ is also the center of the generalized smallest ball containing τ .

We know, from Proposition 1 and Corollary 1(2 .), 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 = π bisτ (P ) -o τ , (P -o τ ) 2 -µ ∈ R n-k × R
The construction of Φ τ is illustrated on Figure 7 in dimension 2 and Figure 9, bottom, in dimension 3.

Observe that the image by Φ τ of all vertices of simplex τ coincide. Therefore the image of τ is a single vertex:

Φ τ (τ ) = 0, µ C (τ ) ⊂ R n-k × R
Call P τ the set of weighted points in (P i , µ i ) ∈ P \ τ such that τ ∪ (P i , µ i ) has the same bounding weight as τ . In the case of the Delaunay triangulation, P τ corresponds to the set of points in P (strictly) inside the smallest ball enclosing τ . Formally, using the assumption (29), we introduce the following subset of vertices in the link of τ :

P τ = def. (P i , µ i ) ∈ P \ τ, D ((P C (τ ), µ C (τ )), (P i , µ i )) < 0 (30)
Denote by K τ the (n -k -1)-dimensional simplicial complex made of all simplices over vertices in P τ with dimension up to (n -k -1). Observe that, for any weighted point (P, µ), one has:

D ((P C (τ ), µ C (τ )), (P, µ)) < 0 ⇐⇒ (π bisτ (P ) -o τ ) 2 -µ + d (P, bis τ ) 2 < µ C (τ ) (31)
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, µ)) = (P -o τ ) 2 -µ (32)
We have assumed the weights to be non-positive, µ ≤ 0, and since under our generic conditions we have π bisτ (P ) -o τ = 0, (32) implies that v ∈ P τ ⇒ Height(Φ τ (v, µ)) > 0 and, using observation 2, (31) can be rephrased as: Observation 4 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 (τ )
This observation allows to define the following conical projection: Definition 8 (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 τ )
The shadow of a simplex σ ∈ K τ is a simplex in bis τ whose vertices are the shadows of vertices of σ.

The construction of Sh τ is illustrated on Figure 8 in dimension 2 and Figure 9, bottom, in dimension 3. 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 in the link of τ made of simplices σ ∈ K τ such that τ ∪ σ ∈ |Γ reg |: X(τ ) = def. σ ∈ K τ , dim(σ) = n -k -1, τ ∪ σ ∈ Γ reg (33) = {σ ∈ Lk |Γreg| τ | µ B (τ ∪ σ) = µ B (τ )}
Sh τ (X(τ )) will play a key role for the proof of Theorem 1 in section 6.

(P) at Φ τ (τ ) = (0, µ C (τ )) with bis τ = R n-k × {0} is called shadow polytope of τ .
Figure 10 depicts the shadow polytope corresponding to the example of Figure 9 as the filled area and the bounded cells of its boundary by the two edges in blue.

For each upper half-space H j contributing to the convex cone of the lower convex hull of Φ τ (P) at (0, µ C (τ )), the intersection H j ∩ bis τ is a (n -k)dimensional half-space in bis τ . The shadow polytope is precisely defined as the intersection of all such half-spaces H j ∩bis τ . Since each H j is a upper halfspace and since by observation 4 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 that:

Observation 5 All facets of the shadow polytope are visible from 0.

Lemma 7 Let P be in general position with non-positive weights.

τ 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).

When τ is in the regular triangulation of P, Sh τ induces a bijection between the simplices in X(τ ) and the set of bounded facets of the boundary of the shadow polytope.

Proof 1. follows from Corollary 1(1 .), together with Proposition 1. 2. follows from Corollary 1 item 2. together with Proposition 1.

For the claim 3., observe that 2. implies that the faces of the convex cone of the lower convex hull of Φ τ (P) at Φ τ (τ ) = (0, µ C (τ )) are in one-to-one correspondence with the link of τ in the regular triangulation. If σ is a simplex in the link of τ in the regular triangulation, denote by CC σ the convex cone in R n-k × R with apex Φ τ (τ ) = (0, µ C (τ )) and through CH (Φ τ (σ)):

CC σ = def. {(0, µ C (τ )) + λx | x ∈ CH (Φ τ (σ)) , λ ≥ 0}.
Since µ C (τ ) > 0, the intersection of CC σ with bis τ = R n-k × {0} is therefore (see Figure 9 for an illustration):

empty if all vertices of Φ τ (σ) have height larger than µ C (τ ), -non-empty and non-bounded if some vertices of of Φ τ (σ), but not all, have height larger than µ C (τ ), -non-empty and bounded, if and only if all vertices of Φ τ (σ) have the height smaller than µ C (τ ) > 0.

On Figure 9 bottom, the cones corresponding to the third category are depicted, in blue, together with their non-empty, bounded, intersection (edge) with bis τ . Therefore, since a simplex σ in the link of τ of a regular triangulation belongs to X(τ ) if and only all its vertices are in P τ , we get, with Observation 4, that σ ∈ X(τ ) if and only if the intersection of CC σ with bis τ = R n-k × {0} is non-empty and bounded, as claimed.

Visible convex hulls as lexicographic minimal chain

This section is self-contained and does not rely on previous constructions. Lemma 10 is a key ingredient for the proof of Theorem 1 but is also a result of independent interest: visible convex hulls can be characterized as lexicographic minimum chains under boundary constraints.

Remark 1

The result in Lemma 10 extends to lower convex hulls, since they are equivalent, up to a projective transformation. It extends also directly to regular triangulations, through the lift on paraboloid equivalence between regular triangulations and lower convex hulls. This is already a characterization of regular triangulations as lexicographic minimum chains under boundary constraints, but the total order on simplices given by this direct transposition is not invariant under isometry. Lemmas 8 and 9 will be instrumental in the proof of Lemma 10. Recall (Section 2.1) that the link of a k-simplex in a pure n-dimensional simplicial complex is a pure (n -k -1)-simplicial complex.

Definition 12 (Trace of a chain in a link) Given a k-simplex τ in a simplicial complex K and an n-chain Γ on K, for n > k, we call trace of the n-chain Γ on the link of τ the (n -k -1)-chain Tr τ (Γ ), defined in the link Lk K (τ ) of τ , as follows. For any σ ∈ Lk K (τ ):

Tr τ (Γ )(σ) = def. Γ (τ ∪ σ)
The next lemma is used twice in what follows.

Lemma 8 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 -k -2)-simplex σ is in Tr τ (∂Γ )(σ) if and only if τ ∩ σ = ∅ and τ ∪ σ is in ∂Γ . In 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 τ (Γ ). Note that, in the context of Lemma 9, there exists at least a point x ∈ X that maximizes the distance to O, since X, union of facets, is a compact set. We need to define another order on simplices together with the corresponding induced lexicographic order on chains, respectively denoted ≤ 0 and 0 .

For that, we define the distance from a flat (an affine space) F to 0 as

d 0 (F ) = inf p∈F d(p, 0). If ζ is a non-degenerate k-simplex for some k ≥ 0, define d 0 (ζ) = d 0 (F (ζ)) where F (ζ) is the k-dimensional flat support of ζ.
In order to compare two simplex for the order ≤ 0 , we first compare the distances to 0 of their vertex farthest to 0. If they differ, the simplex whose farthest vertex is farther is greater for ≤ 0 . If they share the same farthest vertex v, then the tie is broken by comparing, among the edges containing v in each simplex, the farthest one to 0, i.e. the one that maximizes d 0 . Again, if the two simplices share also the same farthest edge, we consider the farthest 2-faces in each simplex containing this farthest edge, and so on. More formally:

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, it is defined as follows.

τ -1 (σ) = ∅ and τ 0 (σ) is the vertex of σ farthest from 0.

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 (ζ) (34)
For i = 0, . . . , n -1 we set δ i (σ) = d 0 (τ i (σ)) and we define the comparison < 0 between two (n -1)-simplices σ 1 and σ 2 as a lexicographic order on the sequences (δ i (σ 1 )) i=0,...n-1 and (δ i (σ 2 )) i=0,...n-1 :

σ 1 < 0 σ 2 ⇐⇒ def. ∃k ≥ 0, δ k (σ 1 ) < δ k (σ 2 ) and ∀j, 0 ≤ j < k, δ j (σ 1 ) = δ j (σ 2 ) ( 35
)
which defines an order relation:

σ 1 ≤ 0 σ 2 ⇐⇒ def. σ 1 = σ 2 or σ 1 < 0 σ 2 (36)
Generic condition 2 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 .
Under Condition 2, ≤ 0 is a total order on simplices and, following Definition 3, the order ≤ 0 on simplices induces a lexicographic order 0 on k-chains of K.

Lemma 10 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 full (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 2.

Let X be a (n -1)-chain in K whose (n -1)-simplices are on the boundary of the convex hull of P and are all visible from 0 ∈ R n . Then:

X = min 0 Γ ∈ C n-1 (K), ∂Γ = ∂X . ( 37
)
If n = 1, the boundary operator in (37) 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.

For n = 1 (figure 11), we are given a set of real numbers for P and corresponding singletons for K, so that a 0-chain Γ can be seen as a subsets of P ⊂ R. Since 0 is not in the convex hull, numbers in P are either all positive, or either all negative. The minimal non-zero chain, for lexicographic order 0 , is the chain containing only the vertex x 1 ∈ P with minimal absolute value in P . Replacing the constraint from being non-zero by the stronger constraint for Γ to have odd cardinality, does not change this lexicographic minimum. Moreover, this parity constraint is a linear constraint (over the field Z 2 ). This is why, for n = 1, the boundary constraint ∂Γ = ∂X is the linear operator ∂0 : C n-1 (K) → Z 2 that counts the parity.

P X

Fig. 11 Illustration of Lemma 10 for n = 1. In this case X is a 0-chain, and has therefore no boundary. Fig. 12 Illustration of the recursion in the proof of Lemma 10 for n = 2. In this case X is a 1-chain, and its boundary ∂X is a zero chain made of two vertices. X is a 0-chain made of a single vertex, the red vertex nearest to O on the blue line representing Π. Lemma 10) We first claim that the lemma holds for n = 1. In this case (figure 11) the fact that 0 is not in the convex hull of P means that the 1-dimensional points in P are either all positive, or 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 0 order, which proves the claim.

Proof (Proof of

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

Consider the minimum:

Γ min = min 0 Γ ∈ C n-1 (K), ∂Γ = ∂X (38)
We need to prove that Γ min = X. There exists a unique vertex v in the simplices of ∂X which is farthest from 0. Indeed, existence follows from compactness of ∂X, and unicity from generic condition 2, which in the particular case of vertices says that no pair of vertices lie at the same distance from 0, since in this case, d 0 is merely the distance from the vertex to 0.

Let v be this 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 .

Thanks to Lemma 9, if a point x is a local maximum in X of the distance to 0 one has x ∈ ∂X. It follows that v is also the vertex in the simplices of X which is farthest from 0. Fig. 13 Illustration of the recursion in the proof of Lemma 10 for n = 3. In this case X is a 2-chain, and its boundary ∂X is a 1-chain depicted as the red edges cycle. X is a 1-chain in Π while ∂X is a 0-chain made of the two vertices framed by a little orange squares.

Since v is the vertex in X farthest from 0 and since by definition Γ min 0 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.

Let us briefly give the principle of the induction. We show below that the trace of Γ min in the link of v is the solution of the same minimisation problem (37) with one dimension less, allowing to apply inductively Lemma 10 to show that X and Γ min coincide in the star of v. This allows to remove from X the star of v ((44) below) and iteratively apply the recursion on the remaining farthest vertex of X until X is empty. More formally:

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

∂ Tr v (Γ min ) = Tr v (∂Γ min ) = Tr v (∂X) (39)
In order to define a lexicographic order on chains on the link of v in K, 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)} = def.

Π ∩ uv

where uv denotes the line going through u and v. The map π vΠ is a conical projection on vertices but it extends to a bijection on simplices and chains that does bot contain v that trivially commutes with the boundary operator. By definition of the lexicographic order 0 , 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 (39) or equivalently by:

∂π vΠ (Tr v (Γ min )) = π vΠ (Tr v (∂X)) (40)
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 0 {Γ ∈ C n-1 (K), ∂Γ = ∂X} = min 0 γ ∈ C n-2 π vΠ (Lk K (v)) , ∂γ = π vΠ (Tr v (∂X)) (41) = min 0 γ ∈ C n-2 π vΠ (Lk K (v)) , ∂γ = ∂π vΠ (Tr v (X)) (42)
In the third equality (41) 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. The fourth equality (42) uses (40). Indeed, if F is a k-flat in R n going through v, we have (see Figure 14):

d 0 (π vΠ (F )) = d 0 (F ∩ Π) = d 0 (F ) v -0 (v -0) 2 -d 0 (F ) 2 (43)
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 (43) 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 (42) satisfies the condition of the theorem for n = n -1 which is assumed true by induction.

The recursion is as follows: Hyperplane Π corresponds to R n with n = n -1 and:

n ← n -1 P ← π vΠ P \ {v} K ← π vΠ Lk K (v) X ← π vΠ Tr v (X)
Observes first that, in R k , a (k -1)-simplex with vertices in a point set P is in convex position (i.e. belongs to the convex hull boundary) and is visible from 0 if and only its supporting hyperplane separates P from 0.

Since (n -1)-simplices in X are in convex position and visible from 0, hyperplanes supporting these simplices separate all points of P from 0. Consider in particular such a simplex σ in X which is moreover in the star of v and its associated supporting hyerplane Π σ v.

We have that since Π σ separate P from 0, Π σ ∩ Π = π vΠ (Π σ ), separates P = π vΠ (P \ {v}) from 0 in Π. 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 (42):

γ 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, seeing chains as set of simplices, one has Y ⊂ X, the chain X \Y can equivalently be noted as X -Y when seeing them as vectors over Z 2 . We favor this linear formulation in the equations below. 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 ) (44)
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 1

Recall the definitions of P τ and K τ introduced in section 4.3, page 24, for a k-simplex τ ∈ K P such that Θ(τ ) = τ (in other words such that µ C (τ ) = µ B (τ )):

-P τ is the set of weighted points (P i , µ i ) ∈ P \ τ such that τ ∪ (P i , µ i ) has the same bounding weight µ B (τ ) as τ , -K τ , a subcomplex of the link of τ , is made of all simplices over vertices in P τ with dimension up to (n -k -1).

The next two lemmas establish the connection between the orders lex and 0 and introduce the notation ↓ ρ Γ for a n-chain Γ (46), used in the proof of Theorem 1.

Lemma 11 (Proof in Appendix

G) For σ 1 , σ 2 ∈ K τ , one has: µ C (τ ∪ σ 1 ) ≥ µ C (τ ∪ σ 2 ) ⇐⇒ d 0 (Sh τ (σ 1 )) ≤ d 0 (Sh τ (σ 2 )) (45)
For a n-chain Γ denote by ↓ ρ Γ the chain obtained by removing from Γ all simplices with bounding weight strictly greater than ρ.

↓ ρ Γ = def. {σ ∈ Γ, µ B (σ) ≤ ρ} (46) Lemma 12 (Proof in Appendix H) For two n-chains Γ 1 , Γ 2 ∈ C n (K P ) if Γ 1 = Γ 2 one has: ↓ ρ Γ 1 lex ↓ ρ Γ 2 ⇒ Sh τρ Tr τρ (↓ ρ Γ 1 ) 0 Sh τρ Tr τρ (↓ ρ Γ 2 )
where τ ρ is a simplex such that θ(τ ) = τ and µ B (τ ) = ρ.

Observation 6 (Total orders equivalence) Observes that, since both lex and 0 are total orders under our generic condition, the implication of Lemma 12 gives the equivalence:

↓ ρ Γ 1 lex ↓ ρ Γ 2 ⇐⇒ Sh τρ Tr τρ (↓ ρ Γ 1 ) 0 Sh τρ Tr τρ (↓ ρ Γ 2 )
where τ ρ is a simplex such that θ(τ ) = τ and µ B (τ ) = ρ.

We now have all the tools needed to prove our main theorem.

Proof (Proof of Theorem 1)

We prove Theorem 1 in the case of non-positive weights which then extends to any weights thanks to Observations 3 and 8. As in Proposition 2, denote by Γ reg the chain that defines the regular triangulation of CH (P). As in Theorem 1 denote by β P ∈ C n-1 (K P ) the (n -1)-chain made of simplices belonging to the boundary of CH (P).

Observation 7

The chain Sh τ (Tr τ (↓ Γ reg )) is the set of (n -k -1)-faces of the convex hull of Sh τ (P τ ) visible from the origin 0.

In the remainder of this proof we use the lexicographic order 0 on shadows of (n -k -1)-chains in K τ , defined at the beginning of Section 5. This order is equivalent to the order lex on corresponding n-chains restricted to the set of simplices with bounding weight µ = B (Lemma 12 and Observation 6). This correspondence allows to conclude the proof by applying Lemma 10 that says the chain defined by visible faces of a polytope minimizes the lexicographic order 0 among chains with same boundary.

More formally, thanks to Lemma 12 we have:

↓ Γ 1 lex ↓ Γ 2 ⇒ Sh τ (Tr τ (↓ Γ 1 )) 0 Sh τ (Tr τ (↓ Γ 2 ))
It follows that Sh τ (Tr τ (↓ Γ min )) is the the minimum for order 0 , among all chains in the complex Sh τ (K τ ) that satisfy the constraint (49), or, equivalently:

Sh τ (Tr τ (↓ Γ min )) = min 0 Γ ∈ C n-k-1 (Sh τ (K τ )) | ∂Γ = ∂Sh τ (Tr τ (↓ Γ reg ))
Observation 7 allows us to apply Lemma 10 with:

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

Appendices

A Overview of the proof This section, designed as a complementary roadmap, summarizes the arguments in the proof's main steps, and illustrates them on Figures 15 and16. It is completed by a glossary, Section A.4, that recalls most of the notions used in this overview. The theorem is proven for points with non-positive weights which, thanks to Observation 3, is enough to be true for any weights.

The proof splits into two main steps, (A) and (B), summarized on the flowcharts of figures 15 and 16.

For p large enough, µ B (σ) is also the dominant quantity in • (p) , since µ B (σ) = lim p→∞ w p (σ) and, 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 weights (Lemma 5 in Section 4.1).

As detailed in the proof of Theorem 1 in Section 6, this fact allows us to focus on the link of a k-simplex τ µ = B , inclusion minimal among simplices whose bounding weight µ = B is the largest bounding weight for which some simplex in Γ reg and Γ min differ.

At this point, it remains to compare the traces of Γ reg and Γ min in the link of τ µ = B , and prove that they are identical, to get the contradiction. This comparison is rather trivial for n < 3, but requires the additional constructions of step (B) for n ≥ 3.

A.2 Case n < 3:

For n = 1, for p large enough, the order lex and the order induced by comparing • (p) coincide, so that the result follows immediately from Proposition 2.

For n = 2, the proof is detailed in [START_REF] Vuillamy | Simplification planimétrique et chaînes lexicographiques pour la reconstruction 3D de scènes urbaines[END_REF]Section 4.2.3]. In this case, the two orders differ even for large p. However it can be observed that chains minimum for either • (p) , for p large enough, or for lex (under boundary constraint) contain generically only one simplex σ for each bounding weight µ B (σ) . It results that, in both triangulations, the set of simplices with a given bounding weight is made of a single simplex, acute triangle or longest edge of obtuse triangle, and therefore (with the generic condition) coincide. This with the definition of τ µ = B in step (A) gives the contradiction.

A.3 Step (B):

The proof for n ≥ 3 needs to focus on sets of n-simplices with same bounding weight µ B . Formally, it includes the proof for n = 1 and n = 2 as limit trivial cases.

Under the generic condition, n-simplices sharing the same bounding weight µ B are all cofaces of some simplex τ such that µ B (τ

) = µ C (τ ) = µ B .
For example, in the situation of Figure 3, for a Delaunay triangulation in R 3 , the set of tetrahedra with the same bounding radius R B , under generic condition, is not of the same nature in examples left, middle and right. On the left, since R B (σ) = R C (σ), there is, under generic condition, a single such tetrahedron abcd.

In the middle, τ would be the triangle abc and, denoting by B B (τ ) the unique ball with radius R B enclosing τ , there is exactly one tetrahedron abcq with bounding radius R B , in the full simplicial complex K P , for each point q ∈ B B (τ ) ∩ (P \ {a, b, c}). These vertices are in the link of τ .

On the right, τ would be the edge ab and there is a one-to-one correspondance between tetrahedra abpq with bounding radius R B , in the full simplicial simplices in the link of τ in |Γ reg | whose union with τ does not increases the bounding weight of τ :

{σ ∈ Lk |Γreg| τ | µ B (τ ∪ σ) = µ B (τ )},
and the simplices in the visible convex hull, in R n-k , of the images of vertices by Sh τ . This visible convex hull is a simplicial ball, and therefore,

{σ ∈ Lk K |Γreg | τ | µ B (τ ∪ σ) = µ = B }
is a simplicial complex homeomorphic to a (n -k -1)-ball. This last fact may be of independent interest. For example, on Figure 9, there are 6 tetrahedra in the star of the edge τ in |Γ reg | but only 2 of them share the same bounding radius as τ , and are therefore in {σ ∈ |Γ reg |, µ B (σ) = µ B (τ )} as seen on Figure 9 top where only two tetrahedra, in blue, are included in the bounding sphere. In this case, the corresponding simplicial complex Sh τ Lk {σ∈|Γreg| |µ B (σ)=µ B (τ )} τ , topologically a 1-dimensional ball, is made of the two edges sharing a vertex, in blue, inside the plane bis τ seen on Figure 9 bottom. By induction on the dimension of convex cones and convex polytopes, one shows that this bounded subcomplex of the boundary of a convex polytope visible from the origin can be expressed as the minimum under boundary constraint (Lemma 10 in Section 5) for another lexicographic order denoted 0 .

The lexicographic order 0 on the images by Sh τ is shown (Lemmas 11 and 12 in Section 6) to be equivalent to the order induced by lex on the trace of chains in Lk {σ∈K P |µ B (σ)=µ B (τ )} τ .

This equivalence between orders allows then to conclude (proof of Theorem 1 in Section 6). Indeed, we have shown that the traces of Γ reg and Γ min in Lk {σ∈K P |µ B (σ)=µ B (τ )} τ minimizes the same order under the same boundary constraints. It follows that they coincide, establishing the contradiction with the assumption at the beginning of step (A).

A.4 Glossary

Bisector of a simplex: Given a k-simplex in R n , its bisector bis τ , defined by (22), is the (n -k)-dimensional affine space, set of points with same weighted distance to each vertex of τ . In the case of zero weighs (that is in the case of Delaunay complex), it is the set of point equidistant from each vertex of τ . When τ is a Delaunay (respectively regular triangulation) simplex, it is also the affine space supporting the Voronoi (respectively power diagram) cell dual to τ . Figure 5 shows the line bisector bis τ of an edge τ = ab in R 2 .

Bounding weight µ B (σ) of a simplex σ: The bounding weight µ B (σ) of a simplex σ is a generalization, for weighted points, of the square of the radius of the smallest ball enclosing the simplex R B (σ) 2 . It is the dominant term in the definition of the order on simplices which induces the lexicographic order lex on chains. It is formally defined in Definition 7 and is related to the weights w p (σ) p of simplex σ in the norm • (p) by Lemma 4:

µ B (σ) = lim p→∞ w p (σ)
Full simplicial complex K P over a set of points: Given a set of points P ⊂ R n , the full simplicial complex K P is the simplicial complex made of all possible simplex of dimension less or equal to n with vertices in P. Unlike Delaunay or regular triangulation complexes, it is not embedded in general, as simplices convex hulls overlap as soon as P > n + 1.

Lexicographic order induced by a total order: It is defined formally in Definition 3. A total order ≤ on n-simplices induces a lexicographic order on n-chains. Seeing the two n-chains Γ 1 = Γ 2 with coefficients in Z 2 as sets of n-simplices, we write

Γ 1 Γ 2 if the largest simplex which is in the symmetric difference (Γ 1 ∪ Γ 2 ) \ (Γ 1 ∩ Γ 2 ), belongs to Γ 2 .
Lexicographic order lex : The lexicographic order lex of Theorem 1 is induced by the total order ≤ on simplices. This total order ≤ is given in Section 3.5 for the general case and Section 3.2 gives a more explicit expression for the particular cases of Delaunay triangulations in R 2 and R 3 .

Lexicographic order 0 : The lexicographic order 0 is induced by the total order ≤ 0 defined by ( 35) and (36) in Section 5. According to Lemma 10, visible convex hulls are minimum for order 0 under boundary constraint. Norm • (p) : It is defined in Section 4.1 by ( 13), as:

Γ (p) = def. σ |Γ (σ)|w p (σ) p .
It is a kind of L 1 norm on vector Γ whose coefficient w p (σ) p , for simplex σ, is defined, by [START_REF] Edelsbrunner | Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms[END_REF], as the p th power of the L p norm of function f σ : CH (σ) → R defined in [START_REF] Cohen-Steiner | Lexicographic optimal homologous chains and applications to point cloud triangulations[END_REF].

Restriction ↓ ρ Γ of a chain Γ : For a chain Γ , we denote by ↓ ρ Γ the chain obtained by removing from Γ all simplices with bounding weight strictly greater than ρ:

↓ ρ Γ = def. {σ ∈ Γ, µ B (σ) ≤ ρ}.
Shadow map Sh τ : (Definition 8). Given a k-simplex τ ∈ K P , the shadow map Sh τ is a map that sends the vertices of the link of τ that belong to simplices with same bounding radius as τ :

{{v} ∈ Lk K P τ | µ B (τ ∪ {v}) = µ B (τ )} toward R n-k .
It is a conical projection applied to the images by Φ τ , as illustrated on Figure 9, bottom. It follows a sequence of geometric constructions, notably the bisector bis τ , and the maps π τ and Φ τ , detailed in Sections 4.2 and 4.3.

The simplicial map induced by the shadow map Sh τ realizes a simplicial isomorphism between the full simplicial complex

{σ ∈ Lk K P τ | µ B (τ ∪ σ) = µ B (τ )}
and the corresponding full complex over the vertices images.

Moreover, its restriction to Lk |Γreg| τ , the support of the link of τ in the regular triangulation |Γ reg |, is a simplicial isomorphism between:

{σ ∈ Lk |Γreg| τ | µ B (τ ∪ σ) = µ B (τ )}
and the visible convex hull of the vertices images (Lemma 7 in Section 4.3).

As a consequence, {σ ∈

Lk |Γreg| τ | µ B (τ ∪ σ) = µ B (τ )} is a simplicial (n -k -1)-ball (i.e. its geometric realization is a topological (n -k -1)-ball).
Simplex: (Section 2.1 or [15, First chapter]). A k-simplex is a set of (k + 1) vertices. In particular, a vertex a is a 0-simplex, and edge {a, b}, sometimes denoted ab is a 1-simplex and a triangle {a, b, c}, sometimes denoted abc is a 2-simplex. For example, if τ 1 = ab and τ 2 = cd are edges, then τ 1 ∪ τ 2 is the 3-simplex, or tetrahedron, abcd. To each k-simplex is associated a realization as a topological space, namely the convex hull of k + 1 affinely independent points.

We denote by CH (σ) the convex hull of the vertices of σ.

Simplicial chain: (Section 2.2 or [15, First chapter]). A k-simplicial chain Γ over a simplicial complex K is a vector, over the field Z 2 , defined by associating a coefficient denoted

Γ (σ) ∈ {0, 1} = Z 2 to each k-simplex in K.
It is sometimes convenient to see a k-chain also as the set of k-simplices Γ = {σ | Γ (σ) = 1}. With this convention we allow ourselves to write for example

Γ 1 + Γ 2 = Γ 1 -Γ 2 = (Γ 1 ∪ Γ 2 ) \ (Γ 1 ∩ Γ 2 ).
Simplicial complexes: (Section 2.1 or [15, First chapter]). A set K of simplices is called a simplicial complex if any σ ∈ K has all its faces in K:

σ ∈ K and ∅ = τ ⊆ σ ⇒ τ ∈ K
Given a simplicial complex K, we denote by K [k] the subset of K containing all k-simplices in K.

Support

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

intersection point we can keep track of the change in the number of covering n-simplices of y(t). 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] and the boundary of CH (P).

This point y(t b ) ∈ (x , x) hits the convex hull CH (τ b ) of 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 , CH (σ) is on the inner side of the convex hull supporting halfspace. It follows that, starting from the outer point x , the number of covering simplices becomes the odd number n b just after the first crossing point y(t b ).

Then, when crossing the convex hull CH (τ i ) of any other (n -1)-simplex τ i / ∈ β P , at some point y(t i ), it follows from the condition ∂Γ = β P that the number n i of n-simplices in Γ coface of τ i has to be even. When crossing CH (τ 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
therefore even and the number of covering simplices remains odd along the path and, in particular, is odd at point x.

E Proof of Lemma 4 on page 18

Proof Since the expression [START_REF] Cohen-Steiner | Lexicographic optimal homologous chains and applications to point cloud triangulations[END_REF] 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: This with (53) ends the proof.

f σ (x) =
F Proof of Lemma 9 on page 28

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 of 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(O, y) is convex on f and cannot have an interior local maximum at x. We assume now that x is a vertex of C.

Following for example [START_REF] Federer | Curvature measures[END_REF][START_REF] Rockafellar | 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: u, ∀v ∈ Tan x C, u, v ≤ 0 (54)

Since C is a convex polytope, Tan x C is a convex closed cone and one has [START_REF] Rockafellar | Convex analysis[END_REF]:

Tan x C = (Nor x C) ⊥ = def.
v, ∀u ∈ Nor x C, u, v ≤ 0 (55)

Each facet F i of C containing x is supported by a half-space H i = {y, yx, n i ≤ 0} with outer normal n i , and one has:

Nor x C = i λ i n i ,
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(O, y) is increasing in the direction t i in a neighborhood of x in ∂C, and, with the assumption that x is in the relative interior of X, we have that y → d(O, y) is increasing in the direction t i in a neighborhood of x in X. This gives a a contradiction since x is assumed to be a local maximum of y → d(O, y) in X.

G Proof of Lemma 11 on page 34

Proof Using Definition 7 page 13, one has: {σ ∈ Γ, µ B (σ) = ρ}

We claim that:

(↓ ρ Γ 1 lex ↓ ρ Γ 2 ) ⇒ → ρ Γ 1 lex → ρ Γ 2 (64)
Indeed, by definition of the lexicographic order, if this did not hold, it would imply → It remains to show that the order lex restricted to simplices τ ∪ σ with µ B (τ ∪ σ) = ρ corresponds to the order 0 on the shadow of σ.

By definition of lex , since in (9) one has always µ 0 (τ ∪σ 1 ) = µ 0 (τ ∪σ 2 ) = ρ, it goes like this:

σ 1 < σ 2 ⇐⇒ def. ∃k ≥ 1, µ k (τ ∪ σ 1 ) > µ k (τ ∪ σ 2 )
and ∀j, 0 ≤ j < k, µ j (τ ∪ σ 1 ) = µ j (τ ∪ σ 2 ) (65)

Observe that this expression is similar to (35). For a 0-simplex {v} ∈ K P , the circumweight µ C (τ ∪ {v}) is, according to Lemma 11, 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 (34) and ( 8), Lemma 11 allows to check that the simplex Θ k (σ) of (8) in the star of τ in K P corresponds to the simplex τ k-1 (σ) in (34) in the link of τ :

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

µ k (τ ∪ σ 1 ) ≤ µ k (τ ∪ σ 2 ) ⇐⇒ δ k-1 (σ 1 ) ≥ δ k-1 (σ 2 )
It follows that, for Γ 1 , Γ 2 ∈ C n (K P ) and τ = τ ρ :

→ ρ Γ 1 lex → ρ Γ 2 ⇐⇒ Sh τ Tr τρ (↓ ρ Γ 1 ) 0 Sh τρ Tr τρ (↓ ρ Γ 2 )
which, with claim (64), ends the proof.

I Generic conditions

The generic condition required by the main theorem is Condition 1 of Section 3.4, page 14. Because it applies to weighted points, it relies on the notion of circumweight of a simplex. In case of zero weight, it boils down to requiring that simplices are not degenerate, which means that the vertices are affinely independent, and that two distinct simplices have distinct circumradii. Each forbidden event, either for a simplex to be degenerate, or for a given pair of distinct simplices to have same circumradius corresponds to the zero of a non-zero polynomial on R N , which has therefore measures 0, and whose complement is open and dense. It follows that Condition 1, conjonction of finitely many generic conditions, is generic. Condition 2, in section 5, corresponds to Condition 1 after some geometric transformation and is generic for the same reason.

Looking in detail to Condition 1, we see that it is stronger than the usual generic condition required for Delaunay or regular triangulations. For example, for a Delaunay triangulation in R 2 to be a triangulation of the convex hull of the points, it is usually required that triples are non-degenerate (no triple of points on the same line) and that no set of four points lie on a same circle. This last condition corresponds to our condition that two distinct triangles cannot have the same circumradius, in the particular case of two triangles sharing 2 vertices.

In particular, our stronger condition, for two triangles that may not share any vertex to have same circumradius, is not really necessary for Theorem 1 to hold, at the price of a kind of theoretical symbolic perturbation for the definition of the simplices total order. Since, in practice, non-generic inputs can be managed by symbolic perturbation, relaxing our generic condition would obscure our result without much advantages.

Fig. 3

 3 Fig. 3 Illustration of the definition of Θ(σ) for a tetrahedron σ = abcd in the case of zero weights.

Lemma 3 (

 3 Proof in Appendix D) 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).

Fig. 4 Fig. 5

 45 Fig. 4 Illustration in dimension 2 and zero weights of the constructions of sections 4.2 and 4.3. The two triangles form a Delaunay triangulation of the four points a, b, c, d in the plane because the two red circumcircles are empty. Since both simplices abc and ab share the same blue circle as smallest enclosing disk, one has Θ(abc) = ab and µ B (abc) = µ B (ab).

Figures 4 ,Fig. 6

 46 Figures 4, 5 and 6 illustrate π τ for ambient dimension 2 and dim(τ ) = 1.

Fig. 7

 7 Fig. 7 Illustration in dimension 2 and zero weights of the constructions of sections 4.2 and 4.3. We represent the image by Φτ of τ = ab, c and d.

Figure 9

 9 Figure 9 illustrates π τ for ambient dimension 3 and dim(τ ) = 1.Let o τ = P C (τ ) ∈ bis τ denote the circumcenter of τ (or, for weighted points, the generalized circumcenter as defined in Definition 7, page 13). If(P i , µ i ) ∈ τ , then D ((o τ , µ C (τ )), (P i , µ i )) = 0.Since o τ = π bisτ (P i ) we have:

Fig. 8

 8 Fig. 8 Illustration in dimension 2 and zero weights of the constructions of sections 4.2 and 4.3. The red line between Φτ (τ ) and Φτ (d) (respectively Φτ (c)) corresponds to the red circumcircle of triangle abd (respectively abc) on figure 4: A point is inside a circle if and only its image by Φ is below the corresponding line. The horizontal blue line corresponds to the blue circle on figure 4. The fact that τ belongs to the Delaunay triangulation of a, b, c, d is equivalent to the fact that Φτ (τ ) belongs to the lower convex hull of Φτ ({a, b, c, d}). The fact that µ B (abc) = µ B (ab) is equivalent to the fact that Φτ (c) is below Φτ (τ ). The half-line starting at Φτ (τ ) through Φτ (c) cuts the horizontal axis bisτ at the shadow Shτ (c, 0) of c.

Fig. 9

 9 Fig. 9 Illustration in dimension 3 and zero weights for the definition of bisτ , πτ (top left and right) and Φτ (bottom).

Fig. 10 9 . 9 (

 1099 Fig. 10 Illustration of the shadow polytope (grey area) of Definition 11 corresponding to the example of Figure 9.

For a polytopeLemma 9 (

 9 C, we denote ∂C the boundary of the set C. Proof in Appendix F) Let C ⊂ R n be a polytope and O ∈ R n \ C. Let X ⊂ ∂C be the union of a set of facets of C visible from O. If x ∈ X maximizes the distance to O, then x ∈ ∂X, where ∂X denotes the relative boundary of X in ∂C.

Fig. 14

 14 Fig. 14 Illustration for Equation (43).

∂ 2 BObservation 8

 28 |Γ | of a simplicial chain Γ : The support |Γ | of a simplicial nchain Γ is the n-dimensional simplicial complex made of simplices in Γ with all their faces.Trace of a chain in the link of a simplex: (Definition 12). Given a ksimplex τ ∈ K and a n-chain Γ on K, the trace Tr τ (Γ ) of Γ is a (n -k -1)chain Tr τ (Γ ) defined in the link Lk K (τ ) of τ . For any (n -k -1)-simplex σ ∈ Lk K (τ ), one has:Tr τ (Γ )(σ) = def. Γ (τ ∪ σ)This linear operator commutes with the boundary operator as stated by Lemma 8: Tr τ (Γ ) = Tr τ (∂Γ ) Visible convex hull: Definition 10 formally defines a polytope facet visible from the point 0. Given a finite set of points P ∈ R m in general position (no m + 1 points lie on the same affine (m -1)-space), whose convex hull CH (P ) does not contain the point 0 ∈ R m . The visible convex hull is the (m -1)-simplicial complex embedded in R m corresponding to the subset of the boundary ∂ CH (P ) of CH (P ) "visible" from the point 0. In other word, its image by the embedding in R m is the set of points x ∈ ∂ CH (P ) such that the segment [0, x) does not intersect CH (P ). It is a simplicial ball, i.e. a simplicial complex homeomorphic to a closed (d -1)-ball.Weighted distance:The weighted distance between 2 weighted points, given in Definition 1, generalizes the squared Euclidean distance between ordinary points: D ((P 1 , µ 1 ), (P 2 , µ 2 )) = def.(P 1 -P 2 ) 2 -µ 1 -µ Invariance by global weight translation 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 7 and 1 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 :

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(53)We have from Lemma 2 that P B (σ) ∈ |Θ(σ)| ⊂ CH (σ) 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 (σ) = (Pi,µi)∈Θ(σ) λ i P iOne has by definition of (P C , µ C ):(P i , µ i ) ∈ Θ(σ) ⇒ (P i -P C (Θ(σ))) 2 -µ i = µ C (Θ(σ))and since we know from Lemma 1 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 (σ)) =   (Pi,µi)∈Θ(σ) λ i ((P i -P B (σ)) 2 -µ i )   -0 2 = µ B (σ)

  Tan x C = ρ>0 λ(c -x), λ ≥ 0, c ∈ B(x, ρ) ,where B(x, ρ) denotes the ball centered at x with radius ρ, andNor x C = (Tan x C) ⊥ = def.

(

  P C , µ C ) π τ (τ ) ∪ π τ (σ) = arg min (P, µ) ∈ R n × R ∀(P i , µ i ) ∈ πτ (τ ) ∪ πτ (σ), D ((P, µ), (P i , µ i )) = 0 µ (59)Looking at Definition 7 in light of (28), page 23, in the proof of Lemma 6, we get that:σ ⊃ τ ⇒ µ C (σ) = µ C (π τ (σ)) and P C (σ) = P C (π τ (σ))(60)Since both terms of (45), page 34, are invariant by a global translation, we can assume without loss of generality and in order to make the computations simpler that o τ = 0.H Proof of Lemma 12 page 34Proof In this proof, we denote by → ρ Γ the set of simplices in Γ with bounding weight equal to ρ:→ ρ Γ = def.

ρ Γ 1

 1 =→ ρ Γ 2 and the largest simplex for which → ρ Γ 1 and → ρ Γ 2 differ would be in Γ 1 contradicting ↓ ρ Γ 1 lex ↓ ρ Γ 2 which proves the claim (64). Note that, from Lemma 1 and generic condition 1, page 14, all the simplices in → ρ Γ 1 and → ρ Γ 2 are in the star of a single simplex τ = τ ρ such that µ C (τ ) = µ B (τ ) = ρ.

  ∀i, λ i ≥ 0 (56) and, since O belongs to none of the half-spaces H i : ∀i, O -x, n i > 0 This with (56) gives: ∀u ∈ Nor x C, O -x, u > 0 (57) using (55) we get that O -x is in the interior of -Tan x C i.e.: x -O ∈ (Tan x C) Since x is a vertex of C, Tan x C is the convex hull of Tan x ∂C, therefore (58) implies at there are t 1 , . . . t n+1 ∈ Tan x ∂C and λ 1 , . . . λ n+1 ≥ 0 such that:

	•	(58)
	x -O =

i λ i t i which gives, since O / ∈ C:

According to Proposition 2, Γ reg minimizes Γ → Γ (p) among the chains with boundary β P for any p ≥ 1. In particular, Γ reg minimizes Γ → Γ p for the value p of Lemma 5.

Proposition 2 and Theorem 1 consider a minimum with respect to the same boundary condition while their objective differ. In order to prove Theorem 1, we have to show that both minimum still agree. By contradiction, we assume now that they differ, which means that Γ min = Γ reg where Γ min is the minimal chain of Theorem 1. Consider µ = B to be the largest bounding weight for which some simplex in Γ min and Γ reg differ:

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 5 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 2). We have shown that if they differ, both Γ reg and Γ min must contain at least one simplex with bounding weight µ = B . We know from Lemma 1 and the generic condition 1 that the set of simplices with bounding weight µ = B are all cofaces of some unique dimension min-

where

is defined in (46). In order to simplify the notations, we allow ourselves to replace for the rest of the section ↓ µ = B by ↓ and τ µ = B by τ . It follows from (48) that:

↓ Γ reg and ↓ Γ min have therefore the same boundary and by Lemma 8, their trace also have the same boundary:

Observe that the set of (n -k -1)-simplices in Tr τ (↓ Γ reg ) coincides with the definition of X(τ ) in (33).

Also we have, from item 3 . in Lemma 7, that the set of shadows of simplices in X(τ ), is a chain in Sh τ (K τ ) made of the faces of the convex hull of Sh τ (P τ ) visible from the origin 0. We get the following characterization of Sh τ (Tr τ (↓ Γ reg )):

It is enough to compare the traces of Γ reg and Γ min in the link of τ

A.1 Step (A):

Step (A) corresponds to the beginning of the proof of Theorem 1 in Section 6 and relies on the definitions and lemmas given in Section 4.1. We denote by Γ reg the simplicial n-chain whose support coincides with the regular triangulation, and by Γ min the n-chain minimal for order lex under the boundary constraint ∂Γ = β P . Proving Theorem 1 consists then in proving that Γ min = Γ reg . We assume in step (A), for the sake of contradiction, that Γ min = Γ reg (see Figure 15). Proposition 2 is then established by reusing the observation first made in [START_REF] Chen | Optimal delaunay triangulations[END_REF]: the Delaunay (or regular) triangulation in dimension R n is equivalent to the convex hull of points in R n+1 where each point (x 1 , . . . , x n ) ∈ R n is lifted to a paraboloid as (x 1 , . . . , x n , j x 2 j ) ∈ R n+1 . This implies that the Delaunay triangulation minimizes, among all triangulations, the L p norm of the difference of two functions: the one with the lifted triangulation's simplices as graph and the one with the paraboloid as graph. This characterization as a minimum generalizes from a minimum among triangulations to a minimum among all chains with the convex hull of points as boundary (Proposition 2). It results that Γ reg can be characterized as the chain minimizing the norm • (p) under the boundary constraint ∂Γ = β P .

The statement of Proposition 2 is the same as Theorem 1 except for the order along which the minimum is taken: Γ reg minimizes • (p) while Γ min is minimum for lex (in particular, both statements share the same boundary constraint).

The bounding weight µ B (σ) is the dominant quantity in the definition of the order on simplices which induces the lexicographic order lex on chains. complex K P , and edges p, q ∈ B B (τ ) ∩ (P \ {a, b}). These edges are in the link of τ . Understanding the structure of the set of simplices with same bounding radius and that belong to the regular triangulation requires additional geometric constructions, see Figure 16. Extending the classical lifted paraboloid construction, we introduce, in Sections 4.2 and 4.3, several definitions associated to a k-simplex τ in a n-dimensional regular triangulation. The bisector bis τ together with the maps π τ , and Φ τ , are intermediary constructions allowing to define formally the shadow map Sh τ :

and extend it as a simplicial map that send simplices in: Denote by τ ⊂ σ the set of vertex (P i , µ i ) ∈ σ for which:

This set cannot be empty as, if all inequalities in [START_REF] Chen | Optimal delaunay triangulations[END_REF] where strict, a strictly smaller value of µ would still match the inequality, which would contradict with the arg min in [START_REF] Chen | Optimal delaunay triangulations[END_REF]. One has then τ = ∅ and:

and therefore (P B (σ), µ B (σ)) also meet the condition required for (P B (τ ), µ B (τ )) in ( 6) of Definition 7:

No point (P, µ) with µ < µ B (σ) can satisfies (50) or (51) as it would again similarly contradict the arg min in [START_REF] Chen | Optimal delaunay triangulations[END_REF]. It follows that:

Proof The idea of the proof is to shoot a ray from a point x ∈ CH (P), that does not belong to the convex hull of any (n -1)-simplex, to the outside of the convex hull CH (P) and keep track of the number of covering n-simplices along the ray as it crosses (n -1)-simplices, where, by covering simplices of a point y we mean the n-simplices σ ∈ Γ such that y ∈ CH (σ).

We claim that since x ∈ CH (P)

where [x x] denotes 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 x and (n -2)-simplices in K P , which occurs generically. Then, the negation of condition (52) with x = x t , occurs only as isolated values of t. We can pick a value t for which this does not occur: set x = x t and the claim is proved.

Next, we move a point y(t) = (1 -t)x + tx along segment [x x]. This segment intersect transversally the (n -1)-faces CH (τ ), for τ ∈ K P . At each In this case, as seen in (24), page 22, the coordinates of π τ (τ ) are (0, -µ C (π τ (τ )) = (0, -µ C (τ )) by (60). So that D ((P, µ), π τ (τ )) = 0 gives us:

It follows that among the weighted points (P, µ) that satisfy D ((P, µ), π τ (τ )) = 0, minimizing µ is equivalent to minimizing P 2 . One can reformulate the characterization (59) of (P

Observe that:

So that the definition of (P C , µ C ) (π τ (τ ) ∪ π τ (σ)) given in (62) 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 ( 63), 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:

µ C (τ ) 2 P C (π τ (τ ) ∪ π τ (σ)) so that, using (60) for the second equality:

It follows that the map:

is decreasing.