# Delaunay and Regular Triangulations as Lexicographic Optimal Chains

David Cohen-Steiner, André Lieutier, Julien Vuillamy

► To cite this version:

David Cohen-Steiner, André Lieutier, Julien Vuillamy. Delaunay and Regular Triangulations as Lexicographic Optimal Chains. Discrete and Computational Geometry, 2023, 70, pp.1-50. 10.1007/s00454-023-00485-1 . hal-04119345

HAL Id: hal-04119345

https://inria.hal.science/hal-04119345

Submitted on 6 Jun 2023

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

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

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

Distributed under a Creative Commons Attribution 4.0 International License
# Delaunay and regular triangulations as lexicographic optimal chains

David Cohen-Steiner · André Lieutier · Julien Vuillamy

Received: date / Accepted: date

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

**Keywords** Delaunay · Regular triangulations · Minimal chains · Lexicographic · Simplicial

**Mathematics Subject Classification (2010)** MSC 52C07 · MSC 52C99

## 1 Introduction

Besides their elegant mathematical properties [11, 2, 16], 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 [8].

<footnote>D. Cohen-Steiner
Université Côte d'Azur, France and Inria Sophia Antipolis-Mediterranée, France. E-mail: david.cohen-steiner@inria.com</footnote>

<footnote>A. Lieutier
E-mail: andre.lieutier@gmail.com</footnote>

<footnote>Julien Vuillamy
Dassault Systèmes, France, Université Côte d'Azur, France and Inria Sophia Antipolis-Mediterranée, France
E-mail: julien.vuillamy@3ds.com</footnote>
## 1.1 Related work: regular triangulations and their optimality properties

The usual definition of Delaunay triangulation considers a finite set of points $P \subset \mathbb{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 $\mathbb{R}^n$ in general position, the Delaunay triangulation of $P$ is then defined as the set of $n$-simplices $\sigma \subset P$ whose circumscribed sphere contains no points in $P \setminus \sigma$. Equivalently, it can be defined as the dual of the Voronoi diagram of $P$. Associating a weight $\mu_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 $\mu_i$ are equal.

Delaunay triangulations satisfy several optimality criteria. It has been shown [16] and [3, section 17.3.4] that “Among all triangulations of a set of points in $\mathbb{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 [3, Theorem 17.3.9] asserts that, given a point set $P \subset \mathbb{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 [6]. It is well known [13, 3] that the Delaunay triangulation in $\mathbb{R}^n$ is equivalent to the lower convex hull of points in $\mathbb{R}^n \times \mathbb{R}$ where each point $(x_1, \dots, x_n) \in P \subset \mathbb{R}^n$ is lifted to:

$$ \text{lift}(x_1, \dots, x_n) \stackrel{\text{def.}}{=} \left( x_1, \dots, x_n, \sum_{j=1}^{n} x_j^2 \right) \in \mathcal{P} $$

where $\mathcal{P} \subset \mathbb{R}^{n+1}$ is the graph of the square norm function. Along this correspondence, a $n$-simplex $\{p_0, \dots, p_n\} \subset P$ belongs to the Delaunay triangulation in $\mathbb{R}^n$ if and only if its lifted counterpart $\{\text{lift } p_0, \dots, \text{lift } p_n\}$ belongs to the boundary of the lower convex hull of lift $P \subset \mathcal{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, \dots, x_n), \mu) \in \mathbb{R}^n \times \mathbb{R}$ is now lifted to $(x_1, \dots, x_n, \sum_j x_j^2 - \mu) \in \mathbb{R}^{n+1}$ [13, 3].
Starting from this equivalence, Chen and coauthors [6] observed that Delaunay triangulations minimize, among all triangulations over a given vertex set $\mathbf{P}$, the $L^p$ norm of the difference between the squared norm function and its piecewise-linear interpolation on the triangulation (see (10) below for a formal definition). This variational formulation has been successfully exploited [1, 5, 7] 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.

## 1.2 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 $\mathbf{P} \subset \mathbb{R}^n$, respectively a set of weighted points $\mathbf{P} \subset \mathbb{R}^n \times \mathbb{R}$, in general position, we define a specific total order $\sigma_0 < \dots < \sigma_{N-1}$ on the set of $n$-simplices with vertices in $\mathbf{P}$. This order allows to compare sets of simplices by comparing the sum of simplex weights, where the weight of simplex $\sigma_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 $\mathbb{Z}_2$, the field of integers modulo 2, when the addition is defined as the set-theoretic symmetric difference:

$$ \Gamma_1 + \Gamma_2 = (\Gamma_1 \cup \Gamma_2) \setminus (\Gamma_1 \cap \Gamma_2). $$

The lexicographic comparison of two chains, or, merely, of two sets of simplices, can equivalently be defined as follows. We say that $\Gamma_1$ is less than $\Gamma_2$, in lexicographic order, and we write $\Gamma_1 \sqsubseteq_{lex} \Gamma_2$, if $\Gamma_1 = \Gamma_2$ or if the maximal simplex in their symmetric difference is in $\Gamma_2$. In other words, for $\Gamma_1 \neq \Gamma_2$:

$$ \Gamma_1 \sqsubseteq_{lex} \Gamma_2 \iff \max \{ \sigma \in (\Gamma_1 \cup \Gamma_2) \setminus (\Gamma_1 \cap \Gamma_2) \} \in \Gamma_2 $$

The main result of this work (Theorem 1) asserts that the Delaunay, respectively regular, triangulation of $\mathbf{P}$, is the minimal simplicial chain for the lexicographic order, among chains whose boundary coincides with the boundary of the convex hull of $\mathbf{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 3-dimensional Delaunay, then in Section 3.5 for the general case of Delaunay or regular triangulation in any dimension $n \ge 1$. In the case of Delaunay triangulation in the plane, the comparison $\le$ 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
<figure><img src="image_2.png" /><figcaption>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.</figcaption></figure>

$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) \Rightarrow T_1 \le 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) \text{ and } R_C(T_1) > R_C(T_2) \Rightarrow T_1 \le 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 $\mathbb{Z}_2$ that can be computed in polynomial time, by simple matrix reduction algorithms [10, 18]. 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 [10, 18]. This is illustrated by an example of application in section 1.3. Also, we believe that our algebraic flavored characterization, by offering a novel perspective on a classical notion, may stimulate further theoretical research as well as applications.

## 1.3 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 [10, 18]. When the submanifold is known through a point set sampling, possibly
<figure><img src="image_3.png" /><figcaption>Fig. 2 Our variational formulation, defining Delaunay triangulations when applied to n-chains in ambient $\mathbb{R}^n$, can be extended to k-chains in $\mathbb{R}^n$. This is illustrated here for $k = 2$ and $n = 3$. The boundary constraint $\beta$ of (1) is the set of edges connecting the red dots.</figcaption></figure>

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 $\mathbb{R}^n$ for $k < n$ instead of n-chains in $\mathbb{R}^n$.

The case $n = 3$ and $k = 2$ is illustrated on Figure 2 which shows triangulated surfaces made of the triangles in $\Gamma_{\min}$, the lexicographic minimal 2-chains in $\mathbb{R}^3$ under imposed boundary, where the total order $\le$ on triangles is the one given in Section 1.2:

$$ \Gamma_{\min} = \min_{\subseteq \text{tex}} \{ \Gamma \in \mathcal{C}_2(K), \partial \Gamma = \beta \}. \qquad (1) $$

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

## 1.4 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 $\| \cdot \|_{(p)}$, under boundary constraints (Proposition 2). The weights in the norm $\| \cdot \|_{(p)}$ are parametrized by a real number $p \ge 1$. Lemmas 4 and 5 imply that, informally, for $p$ large enough, a chain minimizing $\| \cdot \|_{(p)}$ under boundary constraints minimizes in particular a lexicographic preorder induced by the comparison of bounding radii $\mu_B$ of simplices.

Sections 4.2 and 4.3 describe a geometric construction that maps the link of a $k$-simplex $\tau$ in the regular triangulation to a polytope in $\mathbb{R}^{n-k}$. It establishes correspondences between properties of the link of $\tau$ 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**$_\tau$ of a simplex $\tau$, the associated maps $\pi_{\text{bis}\tau}$, $\pi_\tau$, $\Phi_\tau$, and **Sh**$_\tau$, 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 $\sqsubseteq_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.

## 2 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 [15].

### 2.1 Simplicial complexes

*Simplicial complexes* For any $k \ge 0$, a *simplex* of dimension $k$, or $k$-simplex, is a set of $k+1$ vertices. If $\tau$ and $\sigma$ are simplices, we say that $\tau$ is a *face* of $\sigma$, or, equivalently, that $\sigma$ is a *coface* of $\tau$, when $\tau \subseteq \sigma$.
A set $K$ of simplices is called a simplicial complex if any $\sigma \in K$ has all its faces in $K$:

$$ (\sigma \in K \text{ and } \emptyset \neq \tau \subseteq \sigma) \Rightarrow \tau \in 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 $\tau \in K$, the star of $\tau$ in $K$, denoted $\text{St}_K(\tau)$ is defined by $\text{St}_K(\tau) = \{\sigma \in K, \sigma \supseteq \tau\}$ and the link of $\tau$ in $K$, denoted $\text{Lk}_K(\tau)$ is defined by $\text{Lk}_K(\tau) = \{\sigma \in K, \sigma \cup \tau \in K \text{ and } \sigma \cap \tau = \emptyset\}$.

When, for $0 \le k < n$, $\tau$ is a $k$-simplex in a pure $n$-dimensional simplicial complex $K$, the link $\text{Lk}_K(\tau)$ of $\tau$ in $K$ is a $(n - k - 1)$-dimensional pure simplicial complex.

*Embedded simplicial complexes and geometric realization* Given a $k$-simplex $\sigma = \{v_0, \dots, v_k\}$, where each vertex $v_i, 0 \le i \le k$ belongs to $\mathbb{R}^N$ for some $N \ge k$ such that the points $\{v_0, \dots, v_k\}$ are affinely independent, the convex hull of $\sigma$, denoted $\mathcal{CH}(\sigma)$, 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 $\mathbb{R}^N$ such that:<fnref n="1" />

1. for any $k$-simplex $\tau \in K$, the points associated to the vertices of $\tau$ are affinely independent,

2. for any pair of simplices $\sigma_1, \sigma_2 \in K$, one has:

$$ \mathcal{CH}(\sigma_1) \cap \mathcal{CH}(\sigma_2) = \mathcal{CH}(\sigma_1 \cap \sigma_2), $$

The geometric realization $\mathcal{G}(K) \subset \mathbb{R}^N$ of $K$ is then defined as:

$$ \mathcal{G}(K) = \bigcup_{\sigma \in K} \mathcal{CH}(\sigma) $$

In the sequel of the paper, we consider several $n$-dimensional simplicial complexes whose vertices belong to $\mathbb{R}^n$. For example, given four points $a, b, c, d$ in general position in $\mathbb{R}^2$, the simplicial complex made of the triangles in the

$$ (\tilde{v}_i)_j = \begin{cases} 1 & \text{if } j = i \\ 0 & \text{else} \end{cases} $$

gives an embedding of $K$ in $\mathbb{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$.

<footnote n="1">¹ If the simplicial complex $K$ contains $N$ vertices $v_1, \dots, v_N$, associating to vertex $v_i$ the point $\tilde{v}_i \in \mathbb{R}^N$ whose $j$th coordinate is:</footnote>
Delaunay triangulation of {$a, b, c, d$}, together with all their faces, is a simplicial complex embedded in $\mathbb{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 $\mathbb{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(\tau)$ of one of its simplex $\tau \in K$. If the geometric realization $\mathcal{G}(K)$ of $K$ is a $n$-manifold, then the geometric realization of $Lk_K(\tau)$, $\mathcal{G}(Lk_K(\tau))$, is a $(n-k-1)$-sphere.

## 2.2 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 $\mathbb{Z}_2 = \mathbb{Z}/2\mathbb{Z}$. Denoting by $K^{[k]}$ the set of $k$-simplices in $K$, a $k$-chain $\Gamma$ with coefficients in $\mathbb{Z}_2$ is a formal sum of $k$-simplices:

$$ \Gamma = \sum_{i} x_i \sigma_i, \text{ with } x_i \in \mathbb{Z}_2 \text{ and } \sigma_i \in K^{[k]} \qquad (2) $$

Interpreting the coefficient $x_i \in \mathbb{Z}_2 = \{0, 1\}$ in front of simplex $\sigma_i$ as indicating the existing of $\sigma_i$ in the chain $\Gamma$, we can view the $k$-chain $\Gamma$ as a set of $k$-simplices: for a $k$-simplex $\sigma$ and a $k$-chain $A$, we write that $\sigma \in \Gamma$ if the coefficient for $\sigma$ in $\Gamma$ 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 $\Gamma$ and a $k$-simplex $\sigma$, we denote by $\Gamma(\sigma) \in \mathbb{Z}_2$ the coefficient of $\sigma$ in $\Gamma$, in other words:

$$ \Gamma(\sigma) = 1_{\mathbb{Z}_2} \iff \sigma \in \Gamma. $$

We denote $C_k(K)$ the vector space over the field $\mathbb{Z}_2$ of $k$-chains in the complex $K$.

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

**Boundary operator.** In what follows, a $k$-simplex $\sigma$ can also be interpreted as the $k$-chain containing only the $k$-simplex $\sigma$, which is consistent with the notation in (2). 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 $\sigma = \{v_0, \dots, v_k\}$, the boundary operator $\partial_k$ is the linear operator defined as:

$$ \partial_k : C_k(K) \to C_{k-1}(K) \\ \partial_k \sigma = \sum_{\text{def.}}^{k} [v_0, \dots, \hat{v}_i, \dots v_k] $$
where the symbol $\hat{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 $\Gamma$ and $\Gamma'$ are homologous if their difference (or equivalently their sum) is a boundary, in other words, if $\Gamma - \Gamma' = \partial_{k+1}B$, for some (k + 1)-chain $B$.

## 2.3 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, \mu_1), (P_2, \mu_2) \in \mathbb{R}^n \times \mathbb{R}$ their weighted distance is defined as:

$$ D((P_1, \mu_1), (P_2, \mu_2))_{\text{def.}} = (P_1 - P_2)^2 - \mu_1 - \mu_2 \quad (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 $\mathcal{T}$ of the set of weighted points $\mathbf{P} = \{(P_1, \mu_1), \dots, (P_N, \mu_N)\} \subset \mathbb{R}^n \times \mathbb{R}$, $N \ge n+1$, is a triangulation of the convex hull of $\{P_1, \dots, P_N\}$ taking its vertices in $\{P_1, \dots, P_N\}$ such that for any simplex $\sigma \in \mathcal{T}$, denoting $(\mathbf{P}_C(\sigma), \mu_C(\sigma))$ (Definition 7) the generalized circumsphere of $\sigma$, then:

$$ (P_i, \mu_i) \in \mathbf{P} \setminus \sigma \Rightarrow D((\mathbf{P}_C(\sigma), \mu_C(\sigma)), (P_i, \mu_i)) > 0 \quad (4) $$

Definition 4 is equivalent to the definition of a Delaunay triangulation when all weights are equal. Notice the strict inequality in (4), 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.

## 2.4 Lexicographic order

We assume now a total order on the k-simplices of $K$, $\sigma_1 < \dots < \sigma_N$, where $N = \dim C_k(K)$. From this order, we define a lexicographic total order on k-chains. Recall that with coefficients in $\mathbb{Z}_2$ for k-chains $\Gamma_1, \Gamma_2 \in C_k(K)$, we can use interchangeably vector and set-theoretic operations: $\Gamma_1 + \Gamma_2 = \Gamma_1 - \Gamma_2 = (\Gamma_1 \cup \Gamma_2) \setminus (\Gamma_1 \cap \Gamma_2)$.

**Definition 3 (Lexicographic Order on chains)** Assume there is a total order $\le$ on the set of k-simplices of $K$. For $\Gamma_1, \Gamma_2 \in C_k(K)$:

$$ \Gamma_1 \subseteq_{lex} \Gamma_2 \iff_{\text{def.}} \begin{cases} \Gamma_1 = \Gamma_2 \\ \text{or} \\ \max \{\sigma \in \Gamma_1 + \Gamma_2\} \in \Gamma_2 \end{cases} $$
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 $\sigma_0 < \sigma_1 < \dots < \sigma_{N-1}$, we assign the weight $2^i$ to simplex $\sigma_i$. We can then define the norm of a $d$-chain $\Gamma = \sum_j c_j \sigma_j$ were $c_j \in \mathbb{Z}_2$ as:

$$ \|\Gamma\|_* = \left\| \sum_j c_j \sigma_j \right\|_* = \sum_j |c_j| 2^j $$

where $|\cdot|: \mathbb{Z}_2 \to \{0,1\} \subset \mathbb{R}$ assigns respective real numbers 0 and 1 to their corresponding elements in $\mathbb{Z}_2 = \{0_{\mathbb{Z}_2}, 1_{\mathbb{Z}_2}\}$, i.e. $|0_{\mathbb{Z}_2}| = 0$ and $|1_{\mathbb{Z}_2}| = 1$. Another way of saying this is to associate to each $k$-chain $\Gamma \in 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 $\sigma_j$ in $\Gamma$. Then $\|\Gamma\|_*$ is the value of the integer number. With this convention one has:

$$ \Gamma_1 \subseteq_{lex} \Gamma_2 \iff \|\Gamma_1\|_* \le \|\Gamma_2\|_* $$

# 3 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.

## 3.1 Generic configurations

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

**Definition 4 (Generic property)** We say that a property on a space of configuration parametrized by $\mathbb{R}^N$ satisfied on $\mathcal{G} \subseteq \mathbb{R}^N$ is *generic*, if $\mathcal{G}$ is an open dense subset whose complement has Lebesgue measure zero.

Note that the conjunction of finitely many generic conditions is generic. In the case of the Delaunay triangulation of $m$ points in $\mathbb{R}^n$, the configuration space has dimension $N = mn$, and, for regular triangulations of $m$ weighted points in $\mathbb{R}^n \times \mathbb{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 [12]). 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 $\le$ on simplices for Delaunay triangulations in $\mathbb{R}^2$ and $\mathbb{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 \le T_2 \iff \begin{cases} T_1 = T_2 \\ \text{or} \\ R_B(T_1)^2 < R_B(T_2)^2 \\ \text{or} \\ R_B(T_1)^2 = R_B(T_2)^2 \text{ and } R_C(T_1)^2 > R_C(T_2)^2 \end{cases} $$

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 $\mu_0(T) = R_B(T)^2$ and $\mu_1(T) = R_C(T)^2$.

**3-dimensional Delaunay triangulations** Given a non-degenerate tetrahedron $\sigma = abcd$ in $\mathbb{R}^3$, it must belong to one of the three categories illustrated on Figure 3. This category depends on the dimension of $\Theta(\sigma)$, which is, under generic condition, the unique lowest dimensional face of $\sigma$ with the same bounding radius as $\sigma$. Equivalently, $\Theta(\sigma)$ is the unique face of $\sigma$ such that $R_B(\sigma) = R_C(\Theta(\sigma))$.

For all three categories, we define $\mu_0(\sigma)$ as the squared bounding radius of the simplex $\sigma$: $\mu_0(\sigma) = R_B(\sigma)^2$.

For the second category, in the middle of Figure 3, corresponding to $\Theta(\sigma) = abc$, we define moreover $\mu_1(\sigma) = R_C(\sigma)^2$ which is the squared radius of the circumscribing sphere.
$\sigma = abcd$

<figure><img src="image_4.png" /><figcaption>**Fig. 3** Illustration of the definition of $\Theta(\sigma)$ for a tetrahedron $\sigma = abcd$ in the case of zero weights.</figcaption></figure>

For the third category, on the right of Figure 3, corresponding to $\Theta(\sigma) = ab$, we define $\mu_1(\sigma) = \min(\mathrm{R}_C(abc), \mathrm{R}_C(abd))^2$ and $\mu_2(\sigma) = \mathrm{R}_C(\sigma)^2$.

The total order $\le$ on tetrahedra is then defined as:

$$ \sigma_1 \le \sigma_2 \iff \left\{ \begin{array}{ll} \sigma_1 = \sigma_2 & \\ \text{or} & \\ \mu_0(\sigma_1) < \mu_0(\sigma_2) & \\ \text{or} & \\ \mu_0(\sigma_1) = \mu_0(\sigma_2) \text{ and } \mu_1(\sigma_1) > \mu_1(\sigma_2) & \\ \text{or} & \\ \mu_0(\sigma_1) = \mu_0(\sigma_2) \text{ and } \mu_1(\sigma_1) = \mu_1(\sigma_2) \text{ and } \mu_2(\sigma_1) > \mu_2(\sigma_2) & \end{array} \right. $$

Note that $\mu_1$ and $\mu_2$ are not defined for all kinds of tetrahedra. However, the equality configurations requiring the definitions of the quantities $\mu_1$ and $\mu_2$ only arise when the category of the triangles allows to define these quantities. As an example, if the tetrahedron $\sigma_1$ is from the first category ($\Theta(\sigma) = abcd$), then $\mu_0(\sigma_1) = R_B(\sigma_1) = R_C(\sigma_1)$. Under our generic condition, there cannot be another simplex with same circumradius as $\sigma_1$, and therefore, no tetrahedron with same bounding radius. It follows that in this case $\sigma_1$ is the only tetrahedron with bounding radius $R_B(\sigma_1): \sigma_1 \ne \sigma_2 \Rightarrow R_B(\sigma_1) \ne R_B(\sigma_2)$.

### 3.3 The theorem

We consider a set $\mathbf{P} = \{(P_1, \mu_1), \dots, (P_N, \mu_N)\} \subset \mathbb{R}^n \times \mathbb{R}$ of weighted points in $n$-dimensional Euclidean space. A weighted point $(P, 0)$ is seen as a usual point $P \in \mathbb{R}^n$, while, when $\mu > 0$, it is associated to the sphere centered at $P$ with radius $r = \sqrt{\mu}$.

The aim of this paper is to prove Theorem 1 below, where the relation $\sqsubseteq_{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 $\mathbf{P}$, the $n$-dimensional full simplicial complex over $\mathbf{P}$, denoted $K_{\mathbf{P}}$, is the simplicial complex made of all possible simplices up to dimension $n$ with vertices in $\mathbf{P}$.

Recall that, as explained in Section 2.2, a chain with coefficients in $\mathbb{Z}_2$ is identified to the set of simplices for which the coefficient is 1.

**Theorem 1** Let $\mathbf{P} = \{(P_1, \mu_1), \dots, (P_N, \mu_N)\} \subset \mathbb{R}^n \times \mathbb{R}$, with $N \ge n+1$, be weighted points in general position and $K_{\mathbf{P}}$ the $n$-dimensional full simplicial complex over $\mathbf{P}$. Denote by $\beta_{\mathbf{P}} \in C_{n-1}(K_{\mathbf{P}})$ the $(n-1)$-chain, set of simplices belonging to the boundary of the convex hull $CH(\mathbf{P})$.

Then the simplicial complex $|\Gamma_{\min}|$ support of

$$ \Gamma_{\min} = \min_{\subseteq lex} \{ \Gamma \in C_n(K_{\mathbf{P}}), \partial \Gamma = \beta_{\mathbf{P}} \} $$

is the regular triangulation of $\mathbf{P}$.

When all the weights $\mu_i$ are equal, the regular triangulation (Definition 2) is the Delaunay triangulation.

Obviously, replacing in Theorem 1 the full simplicial complex $K_{\mathbf{P}}$ by any complex containing the regular triangulation would again give this triangulation as a minimum.

### 3.4 Generic condition and simplex order, the formal definition

**Definition 6 (Degenerate simplex)** A $k$-simplex $\sigma = \{(P_0, \mu_0), \dots, (P_k, \mu_k)\}$ is said to be degenerate if the set $\{P_0, \dots, 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 circum-radius and smallest enclosing ball radius, to sets of weighted points.

**Definition 7 ($P_C, \mu_C, P_B, \mu_B$)** Given a non-degenerate $k$-simplex $\sigma \subset \mathbf{P}$ with $0 \le k \le n$, the generalized circumsphere and smallest enclosing ball of $\sigma$ are the weighted points $(P_C, \mu_C)(\sigma)$ and $(P_B, \mu_B)(\sigma)$ respectively defined as:

$$ \mu_C(\sigma) = \min_{\text{def.}} \{ \mu \in \mathbb{R}, \exists P \in \mathbb{R}^n, \forall (P_i, \mu_i) \in \sigma, D((P, \mu), (P_i, \mu_i)) = 0 \} \quad (5) $$

$$ \mu_B(\sigma) = \min_{\text{def.}} \{ \mu \in \mathbb{R}, \exists P \in \mathbb{R}^n, \forall (P_i, \mu_i) \in \sigma, D((P, \mu), (P_i, \mu_i)) \le 0 \} \quad (6) $$

$P_C(\sigma)$ (respectively $P_B(\sigma)$) is the unique point $P$ that realizes the minimum in Equation (5) (respectively (6)).
Note that, since $\sigma$ is non-degenerate,

$$ \{(P, \mu), \forall (P_i, \mu_i) \in \sigma, D((P, \mu), (P_i, \mu_i)) = 0\} \neq \emptyset, $$

so that the minimum in (5) is well defined and finite.

The weights $\mu_C(\sigma)$ and $\mu_B(\sigma)$ are called respectively circumweight and bounding weight of $\sigma$.

In the Delaunay case where weights are zero, $\mu_C(\sigma)$ and $\mu_B(\sigma)$ correspond respectively to the square of the circumradius and the square of the radius of the smallest ball enclosing $\sigma$, as depicted on Figure 1, while $P_C(\sigma)$ and $P_B(\sigma)$ 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 $\mathbf{P} = \{(P_1, \mu_1), \dots, (P_N, \mu_N)\} \subset \mathbb{R}^n \times \mathbb{R}$ is in general position if it does not contain any degenerate $n$-simplex, and if, for a $k$-simplex $\sigma$ and a $k'$-simplex $\sigma'$ in $K_{\mathbf{P}}$ with $2 \le k, k' \le n$, one has:

$$ \mu_C(\sigma) = \mu_C(\sigma') \Rightarrow \sigma = \sigma' \qquad (7) $$

We have the following observation deduced from Definitions 1 and 7:

**Observation 2** If the weights of all points in $\mathbf{P}$ are assumed non-positive, then, under the generic condition 1, one has $\mu_C(\tau) > 0$ and $\mu_B(\tau) > 0$ for any simplex $\tau$.

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

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

**Lemma 1 (Proof in Appendix C)** Under generic condition 1 on $\mathbf{P}$, for any simplex $\sigma$, there exists a unique inclusion minimal face $\Theta(\sigma)$ of $\sigma$ such that $(P_B, \mu_B)(\sigma) = (P_C, \mu_C)(\Theta(\sigma))$. Moreover one has $(P_C, \mu_C)(\Theta(\sigma)) = (P_B, \mu_B)(\Theta(\sigma))$.

Figure 3 illustrates the possibilities for $\Theta(\sigma)$ in the case $n = 3$ and zero weights. In general, $\Theta(\sigma)$ 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 $\sigma \in K_{\mathbf{P}}$, one has $P_B(\sigma) \in \mathcal{CH}(\Theta(\sigma))$.

*Proof* We claim first that, for any simplex $\sigma$, one has $P_B(\sigma) \in \mathcal{CH}(\sigma)$. If $\sigma = \{(P_0, \mu_0), \dots, (P_k, \mu_k)\}$, $\mathcal{CH}(\sigma)$ is the convex hull of $\{P_0, \dots, P_k\}$. If $P \notin \mathcal{CH}(\sigma)$ the projection of $P$ on $\mathcal{CH}(\sigma)$ decreases the weighted distance from $P$ to all the vertices of $\sigma$, which shows that $(P, \mu)$ cannot realize the arg min in (6). This proves the claim. Since by definition of $\Theta(\sigma)$ (Lemma 1) one has $P_B(\sigma) = P_B(\Theta(\sigma))$, the lemma follows by applying the claim to the simplex $\Theta(\sigma)$.
3.5 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 $\mathbb{R}^2$ and $\mathbb{R}^3$.

For a $n$-simplex $\sigma$ and $k$ such that $0 \le k \le \dim(\sigma) - \dim(\Theta(\sigma))$ we define the $(k + \dim(\Theta(\sigma)))$-dimensional face $\Theta_k(\sigma)$ as follows.

For $k = 0$, $\Theta_0(\sigma) = \Theta(\sigma)$, where $\Theta(\sigma)$ is defined in Lemma 1.

For $k > 0$, $\Theta_k(\sigma)$ is the $(\dim(\Theta_{k-1}(\sigma)) + 1)$-dimensional coface of $\Theta_{k-1}(\sigma)$ with minimal circumradius:

$$ \Theta_k(\sigma) = \underset{\dim(\tau)=\dim(\Theta_{k-1}(\sigma))+1}{\operatorname{arg min}} \mu_C(\tau) \qquad (8) $$

and $\mu_k(\sigma)$ is the circumweight of $\Theta_k(\sigma)$: $\mu_k(\sigma) = \mu_C(\Theta_k(\sigma))$. In particular, $\mu_0(\sigma) = \mu_C(\Theta(\sigma)) = \mu_B(\sigma)$ (by Lemma 1) and if $k = \dim(\sigma) - \dim(\Theta(\sigma))$ then $\mu_k(\sigma) = \mu_C(\sigma)$.

Observe that, thanks to generic condition 1 and Lemma 1, one has, for two $n$-simplices $\sigma_1, \sigma_2$: $\mu_B(\sigma_1) = \mu_B(\sigma_2) \Rightarrow \Theta(\sigma_1) = \Theta(\sigma_2)$. Therefore, if $\mu_B(\sigma_1) = \mu_B(\sigma_2)$, $\mu_k(\sigma_1)$ and $\mu_k(\sigma_2)$ are defined for the same range of values of $k$.

We define the following order relation on $n$-simplices (recall that $\mu_0(\sigma) = \mu_B(\sigma)$):

$$ \sigma_1 \le \sigma_2 \iff_{\text{def.}} \sigma_1 = \sigma_2 \quad \text{or} \quad \left\{ \begin{array}{ll} \mu_0(\sigma_1) < \mu_0(\sigma_2) & \text{or} \\ \exists k \ge 1, \mu_k(\sigma_1) > \mu_k(\sigma_2) & \\ \text{and } \forall j, 0 \le j < k, \mu_j(\sigma_1) = \mu_j(\sigma_2) & \end{array} \right. \qquad (9) $$

One can check that when $\mathbf{P}$ is in general position, the relation $\le$ 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 = \mu_B(T_i) = \mu_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 = \mu_C(T_i) = \mu_1(T_i)$.

By Definition 3, and under generic Condition 1, the total order $\le$ on $n$-simplices induces a lexicographic total order $\sqsubseteq_{\text{lex}}$ on the $n$-chains of $K_{\mathbf{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: \forall i, \mu_i \leftarrow \mu_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.
# 4 Some geometric properties of regular triangulations

## 4.1 Lifts of weighted points and p-norms

Given a weighted point $(P, \mu) \in \mathbb{R}^n \times \mathbb{R}$, its lift with respect to the origin $O \in \mathbb{R}^n$, denoted by lift$(P, \mu)$, is a point in $\mathbb{R}^n \times \mathbb{R}$ given by:

$$ \text{lift}(P, \mu)_{\text{def.}} = ((P - O), (P - O)^2 - \mu), $$

and, for a set of weighted points $\mathbf{P} = \{(P_1, \mu_1), \dots, (P_N, \mu_N)\} \subset \mathbb{R}^n \times \mathbb{R}$, lift$(\mathbf{P}) = \{\text{lift}(P_1, \mu_1), \dots, \text{lift}(P_N, \mu_N)\} \subset \mathbb{R}^n \times \mathbb{R}$.

Similarly to Delaunay triangulations, it is a well known fact that simplices of the regular triangulation of $\mathbf{P}$ are in one-to-one correspondence with the lower convex hull of lift$(\mathbf{P})$:

**Proposition 1** A simplex $\sigma$ is in the regular triangulation of $\mathbf{P}$ if and only if lift($\sigma$) is a simplex on the lower convex hull of lift($\mathbf{P}$).

Based on this lifted paraboloid formulation, the idea of variational formulation for Delaunay triangulations has emerged [6]. This idea has been exploited further in order to optimize triangulations in [5, 1]. 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_{\sigma}: \mathcal{CH}(\sigma) \to \mathbb{R}$ where $\sigma = \{(P_0, \mu_0), \dots, (P_k, \mu_k)\}$ as the difference between the linear interpolation of the height of the lifted vertices and the function $x \to (x - O)^2$. More precisely, for a point $x \in \mathcal{CH}(\sigma)$ with barycentric coordinates $\lambda_i \ge 0$, $\sum_i \lambda_i = 1$, we have $x = \sum_i \lambda_i P_i$ and:

$$ f_{\sigma}: x \mapsto f_{\sigma}(x) = \left( \sum_{i} \lambda_{i}((P_{i}-O)^{2}-\mu_{i}) \right) - (x-O)^{2} \quad (10) $$

A short computation shows that the function $f_{\sigma}$, expressed in terms of barycentric coordinates, is invariant by isometry (translation, rotation or symmetry on $\sigma$). In particular $f_{\sigma}(x)$ does not depend on the origin $O$ of the lift.

It follows from Proposition 1 that, if $\sigma_{\text{reg}}$ is a simplex containing $x$ in the regular triangulation of $\mathbf{P}$, for any other simplex $\sigma$ containing $x$ with vertices in $\mathbf{P}$:

$$ f_{\sigma_{\text{reg}}}(x) \le f_{\sigma}(x) \quad (11) $$

In the particular case where all weights $\mu_i$ are non-positive, the convexity of $x \mapsto x^2$ says that the expression of $f_{\sigma}(x)$ in (10) is never negative and in this case (11) implies that defining the weight $w_p$ of a n-simplex $\sigma$ as:

$$ w_p(\sigma)_{\text{def.}} = \|f_{\sigma}\|_p = \left( \int_{\mathcal{CH}(\sigma)} f_{\sigma}(x)^p dx \right)^{\frac{1}{p}} \quad (12) $$
allows to characterize the regular triangulation as the one induced by the chain $\Gamma_{\text{reg}}$ that, among all chains with boundary $\beta_{\mathbf{P}}$, minimizes:

$$ \Gamma \to \|\Gamma\|_{(p)} = \sum_{\sigma \text{ def.}} |\Gamma(\sigma)| w_p(\sigma)^p \quad (13) $$

In this last equation, the notation $|\Gamma(\sigma)|$ instead of $\Gamma(\sigma)$ is there since $\Gamma(\sigma) \in \mathbb{Z}_2$ and the sum is in $\mathbb{R}$. For this reason, we used the map $|\cdot|: \mathbb{Z}_2 \to \{0, 1\} \subset \mathbb{R}$, that assigns respective real numbers 0 and 1 to their corresponding elements in $\mathbb{Z}_2 = \{0_{\mathbb{Z}_2}, 1_{\mathbb{Z}_2}\}$, i.e. $|0_{\mathbb{Z}_2}| = 0$ and $|1_{\mathbb{Z}_2}| = 1$.

Formally, we have the following Proposition 2 that characterizes regular triangulations as a linear programming problem over $\mathbb{Z}_2$.

**Proposition 2** Let $\mathbf{P} = \{(P_1, \mu_1), \dots, (P_N, \mu_N)\} \subset \mathbb{R}^n \times \mathbb{R}$, with $N \ge n+1$ be in general position with non-positive weights, and let $K_{\mathbf{P}}$ be the $n$-dimensional full simplicial complex over $\mathbf{P}$.

Denote by $\beta_{\mathbf{P}} \in C_{n-1}(K_{\mathbf{P}})$ the $(n-1)$-chain made of simplices belonging to the boundary of $\mathcal{CH}(\mathbf{P})$ and by $\Gamma_{\text{reg}}$ the $n$-chain defined by the set of $n$-simplices in the regular triangulation of $\mathbf{P}$. Then, for any $p \in [1, \infty)$, one has:

$$ \Gamma_{\text{reg}} = \arg \min_{\substack{\Gamma \in C_{n}(K_{\mathbf{P}}) \\ \partial \Gamma = \beta_{\mathbf{P}}}} \|\Gamma\|_{(p)} \quad (14) $$

The proof of this proposition requires the next lemma. We consider points in the convex hull of $\mathbf{P}$ that do not belong to the convex hull of any $(n-1)$-simplex in $K_{\mathbf{P}}$, i.e. $x \in \mathcal{CH}(\mathbf{P}) \setminus \bigcup_{\sigma \in K_{\mathbf{P}}^{[n-1]}} \mathcal{CH}(\sigma)$. Note that $\bigcup_{\sigma \in K_{\mathbf{P}}^{[n-1]}} \mathcal{CH}(\sigma)$, finite union of convex hulls of $(n-1)$-simplices in $\mathbb{R}^n$, has Lebesgue measure 0.

**Lemma 3 (Proof in Appendix D)** Given $\mathbf{P} = \{P_1, \dots, P_N\} \subset \mathbb{R}^n$, with $N \ge n+1$, in general position, denote by $\beta_{\mathbf{P}} \in C_{n-1}(K_{\mathbf{P}})$ the $(n-1)$-chain made of simplices belonging to the boundary of $\mathcal{CH}(\mathbf{P})$. Let $\Gamma \in C_n(K_{\mathbf{P}})$ be such that:

$$ \partial \Gamma = \beta_{\mathbf{P}} $$

If $x \in \mathcal{CH}(\mathbf{P})$ does not belong to the convex hull of any $(n-1)$-simplex, then there is an odd number of $n$-simplices $\sigma \in \Gamma$ such that $x \in \mathcal{CH}(\sigma)$.

*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 $\mathcal{CH}(\mathbf{P})$ are shared by exactly two $n$-simplices, while only those in $\beta_{\mathbf{P}}$ have a single $n$-coface, we have:

$$ \partial \Gamma_{\text{reg}} = \beta_{\mathbf{P}} $$

We claim now that:

$$ \partial \Gamma = \beta_{\mathbf{P}} \Rightarrow \|\Gamma_{\text{reg}}\|_{(p)} \le \|\Gamma\|_{(p)} \quad (15) $$
Indeed, (12) and (13) gives:

$$ \|\Gamma\|_{(p)} = \sum_{\sigma \in \Gamma} \int_{\mathcal{CH}(\sigma)} f_{\sigma}(x)^p dx = \int_{\mathcal{CH}(\mathbf{P})} \sum_{\substack{\sigma \in \Gamma \\ \mathcal{CH}(\sigma) \ni x}} f_{\sigma}(x)^p dx $$

We get:

$$ \|\Gamma\|_{(p)} = \int_{\mathcal{CH}(\mathbf{P})} \bigcup_{\sigma \in K_{\mathbf{P}}^{[n-1]}} \mathcal{CH}(\sigma) \sum_{\substack{\sigma \in \Gamma \\ \mathcal{CH}(\sigma) \ni x}} f_{\sigma}(x)^p dx \quad (16) $$

From the equivalence between regular triangulations and convex hull on lifted points we know that if $\sigma_{\text{reg}} \in \Gamma_{\text{reg}}$, then for any $n$-simplex in $\sigma \in K$:

$$ x \in \mathcal{CH}(\sigma) \cap \mathcal{CH}(\sigma_{\text{reg}}) \Rightarrow f_{\sigma_{\text{reg}}}(x) \le f_{\sigma}(x) \quad (17) $$

According to Lemma 3, in (16), there is an odd number of simplex $\sigma \in \Gamma$ satisfying $\mathcal{CH}(\sigma) \ni x$ in the condition. It follows that the condition has to hold for at least one simplex $\sigma$.

Therefore (17) gives:

$$ x \in \mathcal{CH}(\sigma_{\text{reg}}) \Rightarrow f_{\sigma_{\text{reg}}}(x)^p \le \sum_{\substack{\sigma \in \Gamma \\ \mathcal{CH}(\sigma) \ni x}} f_{\sigma}(x)^p \quad (18) $$

Since for $x \in \mathcal{CH}(\mathbf{P}) \setminus \bigcup_{\sigma \in K_{\mathbf{P}}^{[n-1]}} \mathcal{CH}(\sigma)$ there is exactly one simplex $\sigma_{\text{reg}}$ such that $\mathcal{CH}(\sigma_{\text{reg}}) \ni x$, (18) can be rewritten as:

$$ \sum_{\substack{\sigma \in \Gamma_{\text{reg}} \\ \mathcal{CH}(\sigma) \ni x}} f_{\sigma}(x)^p \le \sum_{\substack{\sigma \in \Gamma \\ \mathcal{CH}(\sigma) \ni x}} f_{\sigma}(x)^p \quad (19) $$

which, together with (16) gives the claim (15).

Now, if some $n$-simplex $\sigma \in \Gamma$ with $\mathcal{CH}(\sigma) \ni x$, for some $x \in \mathcal{CH}(\mathbf{P}) \setminus \bigcup_{\sigma \in K_{\mathbf{P}}^{[n-1]}} \mathcal{CH}(\sigma)$, is not Delaunay, then

$$ \sum_{\substack{\sigma \in \Gamma_{\text{reg}} \\ \mathcal{CH}(\sigma) \ni x}} f_{\sigma}(x)^p = f_{\sigma_{\text{reg}}}(x)^p < \sum_{\substack{\sigma \in \Gamma \\ \mathcal{CH}(\sigma) \ni x}} f_{\sigma}(x)^p $$

and since the function is continuous, this implies $\|\Gamma\|_{(p)} > \|\Gamma_{\text{reg}}\|_{(p)}$.

**Lemma 4 (Proof in Appendix E) One has:**

$$ \sup_{x \in \mathcal{CH}(\sigma)} f_{\sigma}(x) = \mu_B(\sigma) \quad (20) $$

The following is an immediate consequence used in the proof of Lemma 5:

$$ \lim_{p \to \infty} w_p(\sigma) = w_{\infty}(\sigma) = \|f_{\sigma}\|_{\infty} = \sup_{x \in \mathcal{CH}(\sigma)} f_{\sigma}(x) = \mu_B(\sigma) \quad (21) $$
**Lemma 5** Let $\mathbf{P} = \{(P_1, \mu_1), \dots, (P_N, \mu_N)\} \subset \mathbb{R}^n \times \mathbb{R}$, with $N \ge n + 1$, be in general position with non-positive weights. Let $K_{\mathbf{P}}$ be the corresponding $n$-dimensional full simplicial complex. For $p$ large enough, the weight $w_p(\sigma)^p$ of any $n$-simplex $\sigma \in K_{\mathbf{P}}$, is larger than the sum of the weights of all $n$-simplices in $K_{\mathbf{P}}$ with smaller bounding weight $\mu_B$. In other words, denoting by $K_{\mathbf{P}}^{[n]}$ the set of $n$-simplices in $K_{\mathbf{P}}$:

$$ \exists p^*, \forall p \ge p^*, \forall \sigma \in K_{\mathbf{P}}^{[n]}, \quad w_p(\sigma)^p > \sum_{\tau \in K_{\mathbf{P}}^{[n]}, \mu_B(\tau) < \mu_B(\sigma)} w_p(\tau)^p $$

*Proof* Consider the smallest ratio between two bounding weights (respectively squared radii for the Delaunay case) of $n$-simplices in $K_{\mathbf{P}}$:

$$ \iota = \min_{\substack{\sigma_1, \sigma_2 \in K_{\mathbf{P}}^{[n]} \\ \mu_B(\sigma_1) < \mu_B(\sigma_2)}} \frac{\mu_B(\sigma_2)}{\mu_B(\sigma_1)} $$

One has $\iota > 1$. Choose $\iota'$ such that $1 < \iota' < \iota$. For any $n$-simplex $\sigma \in K_{\mathbf{P}}^{[n]}$ we have from (21):

$$ \lim_{p \to \infty} w_p(\sigma) = \mu_B(\sigma), $$

it follows that, since there is only finitely many simplices in $K_{\mathbf{P}}^{[n]}$, that there exists some $p_0$ large enough such that for any $p > p_0$ one has:

$$ \forall \sigma_1, \sigma_2 \in K_{\mathbf{P}}^{[n]}, \mu_B(\sigma_1) < \mu_B(\sigma_2) \Rightarrow \frac{w_p(\sigma_2)}{w_p(\sigma_1)} > \iota' $$

Let $\mathcal{N}$ be total number of $n$-simplices in $K_{\mathbf{P}}$. Taking:

$$ p^* = \max \left( p_0, \left\lceil \frac{\log \mathcal{N}}{\log \iota'} \right\rceil \right) $$

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 $\tau$. However, before that, we need to introduce geometrical constructions that give an explicit representation of this link (Sections 4.2 and 4.3).

## 4.2 Projection on the bisector of a simplex

In this section, we establish a condition for a simplex $\tau$ 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 $\tau$, we denote by $\mathbf{bis}_\tau$ the $(n-k)$-dimensional affine space bisector of $\tau$, formally defined as:

$$ \mathbf{bis}_{\tau} = \underset{\text{def.}}{\left\{ x \in \mathbb{R}^n \mid \forall v_1, v_2 \in \tau, D((x, 0), v_1) = D((x, 0), v_2) \right\}.} \quad (22) $$
<figure><img src="image_5.png" /><figcaption>**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 $\Theta(abc) = ab$ and $\mu_B(abc) = \mu_B(ab)$.</figcaption></figure>

<figure><img src="image_6.png" /><figcaption>**Fig. 5** Illustration in dimension 2 and zero weights of the constructions of sections 4.2 and 4.3. We are interested in the link of the edge $\tau = ab$. We start by projecting the points on the bisector $\mathbf{bis}_\tau$ of $\tau$. The projection $\pi_{\mathbf{bis}_\tau}(a) = \pi_{\mathbf{bis}_\tau}(b) = \pi_{\mathbf{bis}_\tau}(\tau)$ is the center $o_\tau$ of the circumcircle of $\tau$ which here is also the smallest enclosing circle of $\tau$ as $\Theta(\tau) = \tau$.</figcaption></figure>

In the particular case where $\tau$ is a vertex, i.e. $\dim(\tau) = 0$, one has $\mathbf{bis}_\tau = \mathbb{R}^n$.

Let $x \mapsto \pi_{\mathbf{bis}_\tau}(x)$ and $x \mapsto d(x, \mathbf{bis}_\tau) = d(x, \pi_{\mathbf{bis}_\tau}(x))$ denote respectively the orthogonal projection on and the minimal distance to $\mathbf{bis}_\tau$. We define a projection $\pi_\tau : \mathbf{P} \to \mathbf{bis}_\tau \times \mathbb{R}$ as follows:

$$ \pi_{\tau}(P, \mu) = \underset{\text{def.}}{(\pi_{\mathbf{bis}_{\tau}}(P), \mu - d(P, \mathbf{bis}_{\tau})^2)}. \qquad (23) $$

Figures 4, 5 and 6 illustrate $\pi_\tau$ for ambient dimension 2 and $\dim(\tau) = 1$.
<figure><img src="image_7.png" /><figcaption>Fig. 6 Illustration in dimension 2 and zero weights of the constructions of sections 4.2 and 4.3. The horizontal axis is still the bisector $\mathbf{bis}_\tau$ of $\tau$, but the vertical axis is now the weight axis. We represent the image by $\pi_\tau$ of $\tau = ab, c$ and $d$. Note that $\pi_\tau(\tau) = \pi_\tau(\{a, b\}) = \pi_\tau(a) = \pi_\tau(b)$ is a single point.</figcaption></figure>

<figure><img src="image_8.png" /><figcaption>Fig. 7 Illustration in dimension 2 and zero weights of the constructions of sections 4.2 and 4.3. We represent the image by $\Phi_\tau$ of $\tau = ab, c$ and $d$.</figcaption></figure>

Figure 9 illustrates $\pi_\tau$ for ambient dimension 3 and $\dim(\tau) = 1$.

Let $o_\tau = P_C(\tau) \in \mathbf{bis}_\tau$ denote the circumcenter of $\tau$ (or, for weighted points, the generalized circumcenter as defined in Definition 7, page 13). If $(P_i, \mu_i) \in \tau$, then $D((o_\tau, \mu_C(\tau)), (P_i, \mu_i)) = 0$.

Since $o_\tau = \pi_{\mathbf{bis}_\tau}(P_i)$ we have:

$$ (P_i - o_\tau)^2 - \mu_i - \mu_C(\tau) = d(P, \mathbf{bis}_\tau)^2 - \mu_i - \mu_C(\tau) = 0 $$
<figure><img src="image_9.png" /><figcaption>**Fig. 8** Illustration in dimension 2 and zero weights of the constructions of sections 4.2 and 4.3. The red line between $\Phi_{\tau}(\tau)$ and $\Phi_{\tau}(d)$ (respectively $\Phi_{\tau}(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 $\Phi$ is below the corresponding line. The horizontal blue line corresponds to the blue circle on figure 4. The fact that $\tau$ belongs to the Delaunay triangulation of $a, b, c, d$ is equivalent to the fact that $\Phi_{\tau}(\tau)$ belongs to the lower convex hull of $\Phi_{\tau}(\{a, b, c, d\})$. The fact that $\mu_{B}(abc) = \mu_{B}(ab)$ is equivalent to the fact that $\Phi_{\tau}(c)$ is below $\Phi_{\tau}(\tau)$. The half-line starting at $\Phi_{\tau}(\tau)$ through $\Phi_{\tau}(c)$ cuts the horizontal axis **bis**$_{τ}$ at the shadow $\mathbf{Sh}_{\tau}(c, 0)$ of c.</figcaption></figure>

It follows that if we denote $\mu(\pi_{\tau}(P_{i}, \mu_{i}))$ the weight of $\pi_{\tau}(P_{i}, \mu_{i})$, one has:

$$ \mu(\pi_{\tau}(P_{i}, \mu_{i})) = \mu_{i} - d(P, \mathbf{bis}_{\tau})^{2} = -\mu_{C}(\tau) $$

Therefore, $\pi_{\tau}$ sends all vertices of $\tau$ to a single weighted point:

$$ (P_{i}, \mu_{i}) \in \tau \Rightarrow \pi_{\tau}(P_{i}, \mu_{i}) = (o_{\tau}, -\mu_{C}(\tau)) \quad (24) $$

**Lemma 6** Let $\mathbf{P}$ be in general position, $\tau \in K_{\mathbf{P}}$ a k-simplex and $\sigma \in K_{\mathbf{P}}$ a coface of $\tau$. Then $\sigma$ is in the regular triangulation of $\mathbf{P}$ if and only if $\pi_{\tau}(\sigma)$ is a coface of the vertex $\{(o_{\tau}, -\mu_{C}(\tau))\} = \pi_{\tau}(\tau)$ in the regular triangulation of $\pi_{\tau}(\mathbf{P})$.

*Proof* Under our generic condition, $\sigma$ is in the regular triangulation of $\mathbf{P}$ if and only if there is a weighted point $(\mathbf{P}_{C}(\sigma), \mu_{C}(\sigma))$ such that:

$$ \forall (P_i, \mu_i) \in \sigma, \quad \mathrm{D}((\mathbf{P}_C(\sigma), \mu_C(\sigma)), (P_i, \mu_i)) = 0 \quad (25) $$

$$ \forall (P_i, \mu_i) \in \mathbf{P} \setminus \sigma, \quad \mathrm{D}((\mathbf{P}_C(\sigma), \mu_C(\sigma)), (P_i, \mu_i)) > 0 \quad (26) $$

Observe that, since $\tau \subset \sigma$, (25) implies:

$$ \forall (P_i, \mu_i) \in \tau, \mathrm{D}((\mathbf{P}_C(\sigma), 0), (P_i, \mu_i)) = \mu_C(\sigma) $$

This and the definition (22) of bisector show that $\mathbf{P}_{C}(\sigma)$ must be on the bisector of $\tau$:

$$ \mathbf{P}_C(\sigma) \in \mathbf{bis}_\tau \quad (27) $$
<figure><img src="image_10.png" /><figcaption>**Fig. 9** Illustration in dimension 3 and zero weights for the definition of **bis**<sub>τ</sub>, π<sub>τ</sub> (top left and right) and Φ<sub>τ</sub> (bottom).</figcaption></figure>

We get, for $(P_i, \mu_i) \in \mathbf{P}$:

$$
\begin{align*}
& D\left( (\mathbf{P}_C(\sigma), \boldsymbol{\mu}_C(\sigma)), (P_i, \mu_i) \right) \\
&= \left( \mathbf{P}_C(\sigma) - P_i \right)^2 - \boldsymbol{\mu}_C(\sigma) - \mu_i \\
&= \left( \pi_{\text{bis}_\tau}(P_i) - \mathbf{P}_C(\sigma) \right)^2 + d(P_i, \mathbf{bis}_\tau)^2 - \boldsymbol{\mu}_C(\sigma) - \mu_i \\
&= D_{\text{bis}_\tau} \left( (\mathbf{P}_C(\sigma), \boldsymbol{\mu}_C(\sigma)), (\pi_{\text{bis}_\tau}(P_i), \mu_i - d(P_i, \mathbf{bis}_\tau)^2) \right) \\
&= D_{\text{bis}_\tau} \left( (\mathbf{P}_C(\sigma), \boldsymbol{\mu}_C(\sigma)), \pi_\tau(P_i, \mu_i) \right) \tag{28}
\end{align*}
$$

In the last two lines, the weighted distance is denoted $D_{\text{bis}_{\tau}}$ instead of $D$ in
order to stress that, thanks to (27), it occurs on weighted point of $\text{bis}_{\tau} \times \mathbb{R}$
rather than $\mathbb{R}^n \times \mathbb{R}$. Therefore (25) and (26) are equivalent to:

$$ \begin{gathered} \forall (P_i, \mu_i) \in \sigma, \quad \mathrm{D}_{\mathrm{bis}_{\tau}}((\mathbf{P}_C(\sigma), \boldsymbol{\mu}_C(\sigma)), \pi_{\tau}(P_i, \mu_i)) = 0 \\ \forall (P_i, \mu_i) \in \mathbf{P} \setminus \sigma, \quad \mathrm{D}_{\mathrm{bis}_{\tau}}((\mathbf{P}_C(\sigma), \boldsymbol{\mu}_C(\sigma)), \pi_{\tau}(P_i, \mu_i)) > 0 \end{gathered} $$

which precisely means that $\pi_{\tau}(\sigma)$ is a coface of the vertex $\pi_{\tau}(\tau) = \{(o_{\tau}, -\boldsymbol{\mu}_C(\tau))\}$ in the regular triangulation of $\pi_{\tau}(\mathbf{P})$.

An immediate consequence of Lemma 6 is:

**Corollary 1** The projection $\pi_{\tau}$ preserves the structure of the regular triangulation around $\tau$, more precisely:

1. the simplex $\tau$ is in the regular triangulation of $\mathbf{P}$ if and only if the vertex $\pi_{\tau}(\tau) = \{(o_{\tau}, -\boldsymbol{\mu}_C(\tau))\}$ is a vertex of the regular triangulation of $\pi_{\tau}(\mathbf{P})$,

2. if $\tau$ is in the regular triangulation of $\mathbf{P}$, $\pi_{\tau}$ induces a simplicial isomorphism between the link of $\tau$ in the regular triangulation of $\mathbf{P}$ and the link of vertex $\pi_{\tau}(\tau)$ in the regular triangulation of $\pi_{\tau}(\mathbf{P})$.

## 4.3 Polytope and shadow associated to a link in a regular triangulation

In this section, we study the link of a $k$-simplex $\tau$ in the regular triangulation of $\mathbf{P}$ that satisfies:

$$ (\mathbf{P}_B, \boldsymbol{\mu}_B)(\tau) = (\mathbf{P}_C, \boldsymbol{\mu}_C)(\tau) \qquad (29) $$

Equivalently, we assume $\Theta(\tau) = \tau$ and in this case both generalized smallest enclosing sphere and generalized circumsphere of $\tau$ coincide so that $o_{\tau}$ is also the center of the generalized smallest ball containing $\tau$.

We know, from Proposition 1 and Corollary 1(2.), that the link of $\tau$ in the regular triangulation is isomorphic to the link of lift($\pi_{\tau}(\tau)$) on the boundary of the lower convex hull of lift($\pi_{\tau}(\mathbf{P})$). We consider the lift with the origin at $o_{\tau}$, in other words, the image of a vertex $(P, \mu) \in \mathbf{P}$ is:

$$ \begin{aligned} \Phi_{\tau}(P, \mu) &= \underset{\mathrm{def.}}{\mathrm{lift}}(\pi_{\tau}(P, \mu)) \\ &= (\pi_{\mathrm{bis}_{\tau}}(P) - o_{\tau}, (\pi_{\mathrm{bis}_{\tau}}(P) - o_{\tau})^2 - \mu + d(P, \mathrm{bis}_{\tau})^2) \\ &= (\pi_{\mathrm{bis}_{\tau}}(P) - o_{\tau}, (P - o_{\tau})^2 - \mu) \in \mathbb{R}^{n-k} \times \mathbb{R} \end{aligned} $$

The construction of $\Phi_{\tau}$ is illustrated on Figure 7 in dimension 2 and Figure 9, bottom, in dimension 3.

Observe that the image by $\Phi_{\tau}$ of all vertices of simplex $\tau$ coincide. Therefore the image of $\tau$ is a single vertex:

$$ \Phi_{\tau}(\tau) = \{(0, \boldsymbol{\mu}_C(\tau))\} \subset \mathbb{R}^{n-k} \times \mathbb{R} $$

Call $P_{\tau}$ the set of weighted points in $(P_i, \mu_i) \in \mathbf{P} \setminus \tau$ such that $\tau \cup (P_i, \mu_i)$ has the same bounding weight as $\tau$. In the case of the Delaunay triangulation, $P_{\tau}$
corresponds to the set of points in **P** (strictly) inside the smallest ball enclosing $\tau$. Formally, using the assumption (29), we introduce the following subset of vertices in the link of $\tau$:

$$ P_{\tau} = \underset{\text{def.}}{\{ (P_i, \mu_i) \in \mathbf{P} \setminus \tau, \mathrm{D}((\mathbf{P}_C(\tau), \boldsymbol{\mu}_C(\tau)), (P_i, \mu_i)) < 0 \}} \quad (30) $$

Denote by $K_{\tau}$ the $(n-k-1)$-dimensional simplicial complex made of all simplices over vertices in $P_{\tau}$ with dimension up to $(n-k-1)$. Observe that, for any weighted point $(P, \mu)$, one has:

$$ \begin{gathered} \mathrm{D}((\mathbf{P}_C(\tau), \boldsymbol{\mu}_C(\tau)), (P, \mu)) < 0 \\ \iff (\pi_{\mathbf{bis}_{\tau}}(P) - o_{\tau})^2 - \mu + d(\mathbf{P}, \mathbf{bis}_{\tau})^2 < \boldsymbol{\mu}_C(\tau) \end{gathered} \quad (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:

$$ \mathrm{Height}(\Phi_{\tau}(P, \mu)) = (P - o_{\tau})^2 - \mu \quad (32) $$

We have assumed the weights to be non-positive, $\mu \le 0$, and since under our generic conditions we have $\pi_{\mathbf{bis}_{\tau}}(P) - o_{\tau} \ne 0$, (32) implies that $v \in P_{\tau} \Rightarrow \mathrm{Height}(\Phi_{\tau}(v, \mu)) > 0$ and, using observation 2, (31) can be rephrased as:

**Observation 4** A vertex belongs to $P_{\tau}$ if and only if the height of its image by $\Phi_{\tau}$ is strictly less than $\boldsymbol{\mu}_C(\tau) > 0$:

$$ v \in P_{\tau} \iff 0 < \mathrm{Height}(\Phi_{\tau}(v)) < \boldsymbol{\mu}_C(\tau) $$

This observation allows to define the following conical projection:

**Definition 8 (Shadow)** Let $v$ be a vertex in $P_{\tau}$. The shadow $\mathbf{Sh}_{\tau}(v)$ of $v$ is a point in the $(n-k)$-dimensional Euclidean space $\mathbf{bis}_{\tau}$ defined as the intersection of the half-line starting at $(0, \boldsymbol{\mu}_C(\tau))$ and going through $\Phi_{\tau}(v)$ with the space $\mathbf{bis}_{\tau}$.

$$ \mathbf{Sh}_{\tau}(P, \mu) = \underset{\text{def.}}{\frac{\boldsymbol{\mu}_C(\tau)}{\boldsymbol{\mu}_C(\tau) - \mathrm{Height}(\Phi_{\tau}(P, \mu))}} (\pi_{\mathbf{bis}_{\tau}}(P) - o_{\tau}) $$

The shadow of a simplex $\sigma \in K_{\tau}$ is a simplex in $\mathbf{bis}_{\tau}$ whose vertices are the shadows of vertices of $\sigma$.

The construction of $\mathbf{Sh}_{\tau}$ is illustrated on Figure 8 in dimension 2 and Figure 9, bottom, in dimension 3.

Let $\Gamma_{\mathrm{reg}}$ be the $n$-chain containing the $n$-simplices of the regular triangulation of $\mathbf{P}$ and $|\Gamma_{\mathrm{reg}}|$ the corresponding simplicial complex. Denote by $X(\tau) \in \mathcal{C}_{n-k-1}(K_{\tau})$ the $(n-k-1)$-chain in the link of $\tau$ made of simplices $\sigma \in K_{\tau}$ such that $\tau \cup \sigma \in |\Gamma_{\mathrm{reg}}|$:

$$ \begin{align} X(\tau) &= \{\sigma \in K_{\tau}, \dim(\sigma) = n-k-1, \tau \cup \sigma \in \Gamma_{\mathrm{reg}}\} \tag{33} \\ &= \{\sigma \in \mathrm{Lk}_{|\Gamma_{\mathrm{reg}}|} \tau \mid \boldsymbol{\mu}_B(\tau \cup \sigma) = \boldsymbol{\mu}_B(\tau)\} \nonumber \end{align} $$

$\mathbf{Sh}_{\tau}(X(\tau))$ will play a key role for the proof of Theorem 1 in section 6.
<figure><img src="image_11.png" /><figcaption>**Fig. 10** Illustration of the shadow polytope (grey area) of Definition 11 corresponding to the example of Figure 9.</figcaption></figure>

**Definition 9 (Polytope and convex cone)** In the following, we call polytope a finite intersection of closed half spaces $\cap_i H_i$. The convex cone of a polytope at a point $p$ on the boundary of the polytope is the intersection of all such $H_i$ whose boundary contains $p$.

**Definition 10 (Polytope facet visible from the point 0)** We say that a facet $f$ of a polytope is visible from the point 0, or visible for short, if the closed half-space $H$ containing the polytope and whose boundary is the supporting plane of $f$ does not contains 0.

**Definition 11 (Shadow Polytope)** The (possibly empty) intersection of the convex cone of the lower convex hull of $\Phi_{\tau}(\mathbf{P})$ at $\Phi_{\tau}(\tau) = (0, \boldsymbol{\mu}_{C}(\tau))$ with $\mathbf{bis}_{\tau} = \mathbb{R}^{n-k} \times \{0\}$ is called shadow polytope of $\tau$.

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 $\Phi_{\tau}(\mathbf{P})$ at $(0, \boldsymbol{\mu}_{C}(\tau))$, the intersection $H_j \cap \mathbf{bis}_{\tau}$ is a $(n-k)$-dimensional half-space in $\mathbf{bis}_{\tau}$. The shadow polytope is precisely defined as the intersection of all such half-spaces $H_j \cap \mathbf{bis}_{\tau}$. Since each $H_j$ is a upper half-space and since by observation 4 one has $\boldsymbol{\mu}_{C}(\tau) > 0$, $H_j$ does not contains $(0,0)$, which implies that $H_j \cap \mathbf{bis}_{\tau}$ does not contain the point $o_{\tau}$ in $\mathbf{bis}_{\tau}$. It follows that:

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

**Lemma 7** Let $\mathbf{P}$ be in general position with non-positive weights.

1. $\tau$ is in the regular triangulation of $\mathbf{P}$ if and only if $\Phi_{\tau}(\tau) = (0, \boldsymbol{\mu}_{C}(\tau))$ is an extremal point of the convex hull of $\Phi_{\tau}(\mathbf{P})$.

2. When $\tau$ is in the regular triangulation of $\mathbf{P}$, its link is isomorphic to the link of the vertex $\Phi_{\tau}(\tau) = (0, \boldsymbol{\mu}_{C}(\tau))$ in the simplicial complex corresponding to the boundary of the lower convex hull of $\Phi_{\tau}(\mathbf{P})$.
3. When $\tau$ is in the regular triangulation of $\mathbf{P}$, $\mathbf{Sh}_\tau$ induces a bijection between the simplices in $X(\tau)$ 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 $\Phi_\tau(\mathbf{P})$ at $\Phi_\tau(\tau) = (0, \mu_C(\tau))$ are in one-to-one correspondence with the link of $\tau$ in the regular triangulation. If $\sigma$ is a simplex in the link of $\tau$ in the regular triangulation, denote by $CC_\sigma$ the convex cone in $\mathbb{R}^{n-k} \times \mathbb{R}$ with apex $\Phi_\tau(\tau) = (0, \mu_C(\tau))$ and through $CH(\Phi_\tau(\sigma))$:

$$CC_\sigma = \{(0, \mu_C(\tau)) + \lambda x \mid x \in CH(\Phi_\tau(\sigma)), \lambda \ge 0\}.$$

Since $\mu_C(\tau) > 0$, the intersection of $CC_\sigma$ with $\mathbf{bis}_\tau = \mathbb{R}^{n-k} \times \{0\}$ is therefore (see Figure 9 for an illustration):

- empty if all vertices of $\Phi_\tau(\sigma)$ have height larger than $\mu_C(\tau)$,

- non-empty and non-bounded if some vertices of $\Phi_\tau(\sigma)$, but not all, have height larger than $\mu_C(\tau)$,

- non-empty and bounded, if and only if all vertices of $\Phi_\tau(\sigma)$ have the height smaller than $\mu_C(\tau) > 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 $\mathbf{bis}_\tau$.

Therefore, since a simplex $\sigma$ in the link of $\tau$ of a regular triangulation belongs to $X(\tau)$ if and only all its vertices are in $P_\tau$, we get, with Observation 4, that $\sigma \in X(\tau)$ if and only if the intersection of $CC_\sigma$ with $\mathbf{bis}_\tau = \mathbb{R}^{n-k} \times \{0\}$ is non-empty and bounded, as claimed.

## 5 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 $\tau$ in a simplicial complex K and an n-chain $\Gamma$ on K, for $n > k$, we call trace of the n-chain $\Gamma$ on the link of $\tau$ the $(n-k-1)$-chain $\text{Tr}_{\tau}(\Gamma)$, defined in the link $\text{Lk}_K(\tau)$ of $\tau$, as follows. For any $\sigma \in \text{Lk}_K(\tau)$:

$$ \text{Tr}_{\tau}(\Gamma)(\sigma) = \underset{\text{def.}}{\Gamma}(\tau \cup \sigma) $$

The next lemma is used twice in what follows.

**Lemma 8** Given a k-simplex $\tau$ in a simplicial complex K and a n-chain $\Gamma$ on K for $n > k$, one has:

$$ \partial \text{Tr}_{\tau}(\Gamma) = \text{Tr}_{\tau}(\partial \Gamma) $$

*Proof* We need to prove that for any simplex $\sigma$ in the link of $\tau$, one has:

$$ \partial \text{Tr}_{\tau}(\Gamma)(\sigma) = \text{Tr}_{\tau}(\partial \Gamma)(\sigma) $$

We have by definition that a $(n-k-2)$-simplex $\sigma$ is in $\text{Tr}_{\tau}(\partial \Gamma)(\sigma)$ if and only if $\tau \cap \sigma = \emptyset$ and $\tau \cup \sigma$ is in $\partial \Gamma$. In other words, $\tau \cup \sigma$ has an odd number of n-cofaces in the chain $\Gamma$. This in turn means that $\sigma$ has an odd number of $(n-k)$-cofaces in the trace of $\Gamma$ in the link of $\tau$, i.e. $\sigma \in \partial \text{Tr}_{\tau}(\Gamma)$.

For a polytope C, we denote $\partial C$ the boundary of the set C.

**Lemma 9 (Proof in Appendix F)** Let $C \subset \mathbb{R}^n$ be a polytope and $O \in \mathbb{R}^n \setminus C$. Let $X \subset \partial C$ be the union of a set of facets of C visible from O. If $x \in X$ maximizes the distance to O, then $x \in \partial X$, where $\partial X$ denotes the relative boundary of X in $\partial C$.

Note that, in the context of Lemma 9, there exists at least a point $x \in 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 $\leq_0$ and $\sqsubseteq_0$.

For that, we define the distance from a flat (an affine space) F to 0 as $d_0(F) = \inf_{p \in F} d(p, 0)$. If $\zeta$ is a non-degenerate k-simplex for some $k \geq 0$, define $d_0(\zeta) = d_0(F(\zeta))$ where $F(\zeta)$ is the k-dimensional flat support of $\zeta$. In order to compare two simplex for the order $\leq_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 $\leq_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 $\sigma$ in $\mathbb{R}^n$ that does not contain 0 a dimension increasing sequence of faces $\emptyset = \tau_{-1}(\sigma) \subset \tau_0(\sigma) \subset \dots \subset \tau_{n-1}(\sigma) = \sigma$ with $\dim(\tau_i) = i$. Under a simple generic condition, it is defined as follows.

$$ \tau_{-1}(\sigma) = \emptyset \text{ and } \tau_0(\sigma) \text{ is the vertex of } \sigma \text{ farthest from } 0. $$
For $i \ge 0$, $\tau_i(\sigma)$ is the coface of dimension $i$ of $\tau_{i-1}(\sigma)$ whose supporting $i$-flat is farthest from 0:

$$ \tau_i(\sigma) = \arg \max_{\substack{\zeta \supset \tau_{i-1}(\sigma) \\ \dim(\zeta) = i}} d_0(\zeta) \quad (34) $$

For $i = 0, \dots, n-1$ we set $\delta_i(\sigma) = d_0(\tau_i(\sigma))$ and we define the comparison $<_0$ between two $(n-1)$-simplices $\sigma_1$ and $\sigma_2$ as a lexicographic order on the sequences $(\delta_i(\sigma_1))_{i=0,\dots,n-1}$ and $(\delta_i(\sigma_2))_{i=0,\dots,n-1}$:

$$ \sigma_1 <_0 \sigma_2 \iff_{\text{def.}} \left\{ \begin{array}{l} \exists k \ge 0, \delta_k(\sigma_1) < \delta_k(\sigma_2) \\ \text{and } \forall j, 0 \le j < k, \delta_j(\sigma_1) = \delta_j(\sigma_2) \end{array} \right. \quad (35) $$

which defines an order relation:

$$ \sigma_1 \le_0 \sigma_2 \iff_{\text{def.}} \sigma_1 = \sigma_2 \quad \text{or} \quad \sigma_1 <_0 \sigma_2 \quad (36) $$

**Generic condition 2** Let $K$ be a $(n-1)$-dimensional simplicial complex. For any pair of simplices $\sigma_1, \sigma_2 \in K$: $\dim(\sigma_1) = \dim(\sigma_2) = k$ and $d_0(\sigma_1) = d_0(\sigma_2) \Rightarrow \sigma_1 = \sigma_2$.

Under Condition 2, $\le_0$ is a total order on simplices and, following Definition 3, the order $\le_0$ on simplices induces a lexicographic order $\sqsubseteq_0$ on $k$-chains of $K$.

**Lemma 10** Let $P$ be a set of points in $\mathbb{R}^n$ such that $0 \in \mathbb{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 \in \mathbb{R}^n$. Then:

$$ X = \min_{\sqsubseteq_0} \{ \Gamma \in \mathcal{C}_{n-1}(K), \partial\Gamma = \partial X \}. \quad (37) $$

If $n=1$, the boundary operator in (37) is meant as the boundary operator of reduced homology, i.e the linear operator $\tilde{\partial}_0 : \mathcal{C}_{n-1}(K) \to \mathbb{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 $\Gamma$ can be seen as a subsets of $P \subset \mathbb{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 $\sqsubseteq_0$, is the chain containing only the vertex $x_1 \in P$ with minimal absolute value in $P$. Replacing the constraint from being non-zero by the stronger constraint for $\Gamma$ to have odd cardinality, does not change this lexicographic minimum. Moreover, this parity constraint is a linear constraint (over the field $\mathbb{Z}_2$). This is why, for $n=1$, the boundary constraint $\partial\Gamma = \partial X$ is the linear operator $\tilde{\partial}_0 : \mathcal{C}_{n-1}(K) \to \mathbb{Z}_2$ that counts the parity.
<figure><img src="image_12.png" /><figcaption>Fig. 11 Illustration of Lemma 10 for $n = 1$. In this case $X$ is a 0-chain, and has therefore no boundary.</figcaption></figure>

<figure><img src="image_13.png" /><figcaption>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 $\partial 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 $\Pi$.</figcaption></figure>

*Proof (Proof of 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 $\Box_0$ order, which proves the claim.

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

Consider the minimum:

$$ \Gamma_{\min} = \min_{\Box_0} \{ \Gamma \in C_{n-1}(K), \partial \Gamma = \partial X \} \qquad (38) $$

We need to prove that $\Gamma_{\min} = X$.

There exists a unique vertex $v$ in the simplices of $\partial X$ which is farthest from $0$. Indeed, existence follows from compactness of $\partial 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 $\partial X$ which is farthest from $0$. Since $v$ is a vertex in at least one simplex in $\partial X = \partial \Gamma_{\min}$, it must be a vertex in some simplex in $\Gamma_{\min}$.

Thanks to Lemma 9, if a point $x$ is a local maximum in $X$ of the distance to $0$ one has $x \in \partial X$. It follows that $v$ is also the vertex in the simplices of $X$ which is farthest from $0$.
<figure><img src="image_14.png" /><figcaption>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 $\partial X$ is a 1-chain depicted as the red edges cycle. $X'$ is a 1-chain in $\Pi$ while $\partial X'$ is a 0-chain made of the two vertices framed by a little orange squares.</figcaption></figure>

Since $v$ is the vertex in $X$ farthest from 0 and since by definition $\Gamma_{\min} \subseteq_0 X$, we know that $\Gamma_{\min}$ does not contain any vertex farther from the origin than $v$, therefore $v$ is also the vertex in the simplices of $\Gamma_{\min}$ farthest from 0.

Let us briefly give the principle of the induction. We show below that the trace of $\Gamma_{\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 $\Gamma_{\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 $\partial \Gamma_{\min} = \partial X$, Lemma 8 implies that:

$$ \partial \mathrm{Tr}_v(\Gamma_{\min}) = \mathrm{Tr}_v(\partial \Gamma_{\min}) = \mathrm{Tr}_v(\partial X) \quad (39) $$

In order to define a lexicographic order on chains on the link of $v$ in $K$, we consider the hyperplane $\Pi$ containing 0 and orthogonal to the line $0v$. We associate to any $(n-2)$-simplex $\eta \in L_k(K(v))$ the $(n-2)$ simplex $\pi_{v\Pi}(\eta)$, conical projection of $\eta$ on $\Pi$ with center $v$. In other words, if $u$ is a vertex of $\eta$:

$$ \{\pi_{v\Pi}(u)\}_{\mathrm{def.}} = \Pi \cap uv $$

where $uv$ denotes the line going through $u$ and $v$. The map $\pi_{v\Pi}$ is a conical projection on vertices but it extends to a bijection on simplices and chains that does not contain $v$ that trivially commutes with the boundary operator.
<figure><img src="image_15.png" /><figcaption>Fig. 14 Illustration for Equation (43).</figcaption></figure>

By definition of the lexicographic order $\sqsubseteq_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 $\Gamma_{\min}$, the restriction of $\Gamma_{\min}$ to the star of $v$ must be minimum under the constraint $\partial\Gamma = \partial X$. The constraint $\partial\Gamma = \partial X$ for the restriction of $\Gamma_{\min}$ to the star of $v$ is equivalent to the constraint given by equation (39) or equivalently by:

$$ \partial\pi_{v\Pi}(\mathrm{Tr}_v(\Gamma_{\min})) = \pi_{v\Pi}(\mathrm{Tr}_v(\partial X)) \quad (40) $$

and the minimization on the restriction of the $(n-1)$-chain $\Gamma_{\min}$ to the star of $v$ can equivalently be expressed as the minimization of the $(n-2)$-chain $\gamma_{\min} = \pi_{v\Pi}(\mathrm{Tr}_v(\Gamma_{\min}))$ under the constraint $\partial\gamma_{\min} = \pi_{v\Pi}(\mathrm{Tr}_v(\partial X))$, we have then:

$$ \begin{aligned} \gamma_{\min} &= \pi_{v\Pi}(\mathrm{Tr}_v(\Gamma_{\min})) \\ &= \pi_{v\Pi} \left( \mathrm{Tr}_v \left( \min_{\sqsubseteq_0} \{\Gamma \in \mathcal{C}_{n-1}(K), \partial\Gamma = \partial X\} \right) \right) \\ &= \min_{\sqsubseteq_0} \left\{ \gamma \in \mathcal{C}_{n-2}(\pi_{v\Pi}(\mathrm{Lk}_K(v))), \partial\gamma = \pi_{v\Pi}(\mathrm{Tr}_v(\partial X)) \right\} \end{aligned} \quad (41) $$

$$ = \min_{\sqsubseteq_0} \left\{ \gamma \in \mathcal{C}_{n-2}(\pi_{v\Pi}(\mathrm{Lk}_K(v))), \partial\gamma = \partial\pi_{v\Pi}(\mathrm{Tr}_v(X)) \right\} \quad (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 $\pi_{v\Pi}$ of the link of $v$ are compatible. The fourth equality (42) uses (40).
Indeed, if $F$ is a $k$-flat in $\mathbb{R}^n$ going through $v$, we have (see Figure 14):

$$d_0(\pi_{v\Pi}(F)) = d_0(F \cap \Pi) = \frac{d_0(F)\|v-0\|}{\sqrt{(v-0)^2 - d_0(F)^2}} \quad (43)$$

with the convention $d_0(\pi_{v\Pi}(F)) = +\infty$ in the non-generic case where $F \cap \Pi = \emptyset$ (the denominator vanishes in this case while since $v \in F$ one has $F \cap \Pi \neq \emptyset \Rightarrow d_0(F) < \|v-0\|$).

As seen on (43) $d_0(F) \mapsto d_0(\pi_{v\Pi}(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 $\Pi$ corresponds to $\mathbb{R}^{n'}$ with $n' = n - 1$ and:

$$\begin{aligned} n' &\leftarrow n - 1 \\ P' &\leftarrow \pi_{v\Pi}(P \setminus \{v\}) \\ K' &\leftarrow \pi_{v\Pi}(\mathrm{Lk}_K(v)) \\ X' &\leftarrow \pi_{v\Pi}(\mathrm{Tr}_v(X)) \end{aligned}$$

Observes first that, in $\mathbb{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 $\sigma$ in $X$ which is moreover in the star of $v$ and its associated supporting hyperplane $\Pi_\sigma \ni v$.

We have that since $\Pi_\sigma$ separate $P$ from 0, $\Pi_\sigma \cap \Pi = \pi_{v\Pi}(\Pi_\sigma)$, separates $P' = \pi_{v\Pi}(P \setminus \{v\})$ from 0 in $\Pi$. It follows that the $(n' - 1)$-simplices in $X' = \pi_{v\Pi}(\mathrm{Tr}_v(X))$ are in convex position and are visible from 0.

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

$$\gamma_{\min} = \pi_{v\Pi}(\mathrm{Tr}_v(\Gamma_{\min})) = \pi_{v\Pi}(\mathrm{Tr}_v(X))$$

It follows that the faces in the star of $v$ corresponding to $\mathrm{Tr}_v(\Gamma_{\min})$ belong to $X$. Call $Y$ the $(n-1)$-chain made of these simplices in the star of $v$. We have both $Y \subset X$ and $Y \subset \Gamma_{\min}$.

Since, seeing chains as set of simplices, one has $Y \subset X$, the chain $X \setminus Y$ can equivalently be noted as $X - Y$ when seeing them as vectors over $\mathbb{Z}_2$. We favor this linear formulation in the equations below. Since $v$ is the vertex farthest from 0 in both $X$ and in $\Gamma_{\min}$ one has by definition of the lexicographic order:

$$\begin{aligned} \Gamma_{\min} &= \min_{\subseteq \mathrm{tex}} \{ \Gamma \in \mathcal{C}_{n-1}(K), \partial \Gamma = \partial X \} \\ &= Y + \min_{\subseteq \mathrm{tex}} \{ \Gamma \in \mathcal{C}_{n-1}(K), \partial \Gamma = \partial(X - Y) \} \end{aligned} \quad (44)$$

So, by considering the new problem $X \leftarrow (X - Y)$ and iterating as long as $X$ is not empty, we get our final result $\Gamma_{\min} = X$.
## 6 Proof of Theorem 1

Recall the definitions of $P_\tau$ and $K_\tau$ introduced in section 4.3, page 24, for a $k$-simplex $\tau \in K_P$ such that $\Theta(\tau) = \tau$ (in other words such that $\mu_C(\tau) = \mu_B(\tau)$):

- $P_\tau$ is the set of weighted points $(P_i, \mu_i) \in P \setminus \tau$ such that $\tau \cup (P_i, \mu_i)$ has the same bounding weight $\mu_B(\tau)$ as $\tau$,

- $K_\tau$, a subcomplex of the link of $\tau$, is made of all simplices over vertices in $P_\tau$ with dimension up to $(n-k-1)$.

The next two lemmas establish the connection between the orders $\sqsubseteq_{lex}$ and $\sqsubseteq_0$ and introduce the notation $\downarrow_\rho \Gamma$ for a $n$-chain $\Gamma$ (46), used in the proof of Theorem 1.

**Lemma 11 (Proof in Appendix G) For $\sigma_1, \sigma_2 \in K_\tau$, one has:**

$$ \mu_C(\tau \cup \sigma_1) \geq \mu_C(\tau \cup \sigma_2) \iff d_0(\mathbf{Sh}_\tau(\sigma_1)) \leq d_0(\mathbf{Sh}_\tau(\sigma_2)) \quad (45) $$

For a $n$-chain $\Gamma$ denote by $\downarrow_\rho \Gamma$ the chain obtained by removing from $\Gamma$ all simplices with bounding weight strictly greater than $\rho$.

$$ \downarrow_{\rho} \Gamma =_{\text{def.}} \{ \sigma \in \Gamma, \mu_B(\sigma) \leq \rho \} \quad (46) $$

**Lemma 12 (Proof in Appendix H) For two $n$-chains $\Gamma_1, \Gamma_2 \in C_n(K_P)$ if**
$\Gamma_1 \neq \Gamma_2$ **one has:**

$$ \begin{gathered} \downarrow_{\rho} \Gamma_1 \sqsubseteq_{lex} \downarrow_{\rho} \Gamma_2 \\ \Rightarrow \mathbf{Sh}_{\tau_{\rho}} (\mathrm{Tr}_{\tau_{\rho}} (\downarrow_{\rho} \Gamma_1)) \sqsubseteq_0 \mathbf{Sh}_{\tau_{\rho}} (\mathrm{Tr}_{\tau_{\rho}} (\downarrow_{\rho} \Gamma_2)) \end{gathered} $$

where $\tau_\rho$ is a simplex such that $\theta(\tau) = \tau$ and $\mu_B(\tau) = \rho$.

**Observation 6 (Total orders equivalence) Observes that, since both $\sqsubseteq_{lex}$ and $\sqsubseteq_0$ are total orders under our generic condition, the implication of Lemma 12 gives the equivalence:**

$$ \downarrow_{\rho} \Gamma_1 \sqsubseteq_{lex} \downarrow_{\rho} \Gamma_2 \iff \mathbf{Sh}_{\tau_{\rho}} (\mathrm{Tr}_{\tau_{\rho}} (\downarrow_{\rho} \Gamma_1)) \sqsubseteq_0 \mathbf{Sh}_{\tau_{\rho}} (\mathrm{Tr}_{\tau_{\rho}} (\downarrow_{\rho} \Gamma_2)) $$

where $\tau_\rho$ is a simplex such that $\theta(\tau) = \tau$ and $\mu_B(\tau) = \rho$.

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 $\Gamma_{\mathrm{reg}}$ the chain that defines the regular triangulation of $CH(P)$. As in Theorem 1 denote by $\beta_P \in C_{n-1}(K_P)$ the $(n-1)$-chain made of simplices belonging to the boundary of $CH(P)$.
According to Proposition 2, $\Gamma_{\text{reg}}$ minimizes $\Gamma \mapsto \|\Gamma\|_{(p)}$ among the chains with boundary $\beta_P$ for any $p \ge 1$. In particular, $\Gamma_{\text{reg}}$ minimizes $\Gamma \mapsto \|\Gamma\|_{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 $\Gamma_{\min} \neq \Gamma_{\text{reg}}$ where $\Gamma_{\min}$ is the minimal chain of Theorem 1. Consider $\mu_B^\pm$ to be the largest bounding weight for which some simplex in $\Gamma_{\min}$ and $\Gamma_{\text{reg}}$ differ:

$$ \mu_B^\pm \stackrel{\text{def.}}{=} \max\{\mu_B(\sigma), \sigma \in \Gamma_{\min} + \Gamma_{\text{reg}}\} \quad (47) $$

There must be at least one simplex with bounding weight $\mu_B^\pm$ in $\Gamma_{\text{reg}}$ as otherwise, by definition of $\mu_B^\pm$, there would be a simplex with radius $\mu_B^\pm$ in $\Gamma_{\min}$ and this would give $\Gamma_{\text{reg}} \subseteq \Gamma_{\min}$ with $\Gamma_{\text{reg}} \neq \Gamma_{\min}$ and since $\partial\Gamma_{\text{reg}} = \partial\Gamma_{\min} = \beta_P$ this contradicts the definition of $\Gamma_{\min}$.

Similarly, it follows from Lemma 5 that if there was no simplex with bounding weight $\mu_B^\pm$ in $\Gamma_{\min}$, one would have $\|\Gamma_{\min}\|_{p^*} < \|\Gamma_{\text{reg}}\|_{p^*}$ and $\partial\Gamma_{\text{reg}} = \partial\Gamma_{\min}$. A contradiction with the minimality of $\Gamma_{\text{reg}}$ for norm $\|\cdot\|_{p^*}$ (Proposition 2). We have shown that if they differ, both $\Gamma_{\text{reg}}$ and $\Gamma_{\min}$ must contain at least one simplex with bounding weight $\mu_B^\pm$.

We know from Lemma 1 and the generic condition 1 that the set of simplices with bounding weight $\mu_B^\pm$ are all cofaces of some unique dimension minimal simplex $\tau_{\mu_B^\pm}$. If $\dim(\tau_{\mu_B^\pm}) = n$, $\tau_{\mu_B^\pm}$ is the unique simplex in $K_P$ whose bounding weight is $\mu_B^\pm$. But then $\Gamma_{\text{reg}}$ and $\Gamma_{\min}$ coincide on simplices with bounding weight $\mu_B^\pm$, a contradiction with the definition of $\mu_B^\pm$.

Assume now that $\dim(\tau_{\mu_B^\pm}) = k < n$. By definition of $\mu_B^\pm$ one has:

$$ \downarrow_{\mu_B^\pm} \Gamma_{\text{reg}} - \downarrow_{\mu_B^\pm} \Gamma_{\min} = \Gamma_{\text{reg}} - \Gamma_{\min} \quad (48) $$

where $\downarrow_{\mu_B^\pm}$ is defined in (46). In order to simplify the notations, we allow ourselves to replace for the rest of the section $\downarrow_{\mu_B^\pm}$ by $\downarrow$ and $\tau_{\mu_B^\pm}$ by $\tau$. It follows from (48) that:

$$ \partial(\downarrow \Gamma_{\text{reg}} - \downarrow \Gamma_{\min}) = \partial \Gamma_{\text{reg}} - \partial \Gamma_{\min} = \beta_P - \beta_P = 0 $$

$\downarrow \Gamma_{\text{reg}}$ and $\downarrow \Gamma_{\min}$ have therefore the same boundary and by Lemma 8, their trace also have the same boundary:

$$ \partial \operatorname{Tr}_{\tau}(\downarrow \Gamma_{\min}) = \partial \operatorname{Tr}_{\tau}(\downarrow \Gamma_{\text{reg}}) \quad (49) $$

Observe that the set of $(n-k-1)$-simplices in $\operatorname{Tr}_{\tau}(\downarrow \Gamma_{\text{reg}})$ coincides with the definition of $X(\tau)$ in (33).

Also we have, from item 3. in Lemma 7, that the set of shadows of simplices in $X(\tau)$, is a chain in $\mathbf{Sh}_{\tau}(K_{\tau})$ made of the faces of the convex hull of $\mathbf{Sh}_{\tau}(P_{\tau})$ visible from the origin 0. We get the following characterization of $\mathbf{Sh}_{\tau}(\operatorname{Tr}_{\tau}(\downarrow \Gamma_{\text{reg}})):
**Observation 7** The chain $\mathbf{Sh}_\tau(\mathrm{Tr}_\tau(\downarrow \Gamma_{\mathrm{reg}}))$ is the set of $(n-k-1)$-faces of the convex hull of $\mathbf{Sh}_\tau(P_\tau)$ visible from the origin 0.

In the remainder of this proof we use the lexicographic order $\sqsubseteq_0$ on shadows of $(n-k-1)$-chains in $K_\tau$, defined at the beginning of Section 5. This order is equivalent to the order $\sqsubseteq_{lex}$ on corresponding $n$-chains restricted to the set of simplices with bounding weight $\mu_B^\pm$ (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 $\sqsubseteq_0$ among chains with same boundary.

More formally, thanks to Lemma 12 we have:

$$ \downarrow \Gamma_1 \sqsubseteq_{lex} \Gamma_2 \Rightarrow \mathbf{Sh}_\tau(\mathrm{Tr}_\tau(\downarrow \Gamma_1)) \sqsubseteq_0 \mathbf{Sh}_\tau(\mathrm{Tr}_\tau(\downarrow \Gamma_2)) $$

It follows that $\mathbf{Sh}_\tau(\mathrm{Tr}_\tau(\downarrow \Gamma_{\mathrm{min}}))$ is the minimum for order $\sqsubseteq_0$, among all chains in the complex $\mathbf{Sh}_\tau(K_\tau)$ that satisfy the constraint (49), or, equivalently:

$$ \mathbf{Sh}_\tau(\mathrm{Tr}_\tau(\downarrow \Gamma_{\mathrm{min}})) = \min_{\sqsubseteq_0} \{ \Gamma' \in C_{n-k-1}(\mathbf{Sh}_\tau(K_\tau)) \mid \partial \Gamma' = \partial \mathbf{Sh}_\tau(\mathrm{Tr}_\tau(\downarrow \Gamma_{\mathrm{reg}})) \} $$

Observation 7 allows us to apply Lemma 10 with:

$$ \begin{align*} & n \leftarrow n-k \\ & X \leftarrow \mathbf{Sh}_\tau(\mathrm{Tr}_\tau(\downarrow \Gamma_{\mathrm{reg}})) = \mathbf{Sh}_\tau(X(\tau)) \\ & P \leftarrow \mathbf{Sh}_\tau(P_\tau) \\ & K \leftarrow \mathbf{Sh}_\tau(K_\tau) \end{align*} $$

implying:

$$ \mathbf{Sh}_\tau(\mathrm{Tr}_\tau(\downarrow \Gamma_{\mathrm{min}})) = \mathbf{Sh}_\tau(\mathrm{Tr}_\tau(\downarrow \Gamma_{\mathrm{reg}})) $$

In other words, $\Gamma_{\mathrm{min}}$ and $\Gamma_{\mathrm{reg}}$ coincide on simplices with bounding weight $\mu_B^\pm$, a contradiction with the definition (47) of $\mu_B^\pm$.

## References

1. Alliez P, Cohen-Steiner D, Yvinec M, Desbrun M (2005) Variational tetrahedral meshing. In: ACM SIGGRAPH 2005 Courses, ACM, p 10

2. Aurenhammer F (1991) Voronoi diagrams – a survey of a fundamental geometric data structure. ACM Computing Surveys (CSUR) 23(3):345–405

3. Boissonnat JD, Yvinec M (1998) Algorithmic geometry. Cambridge university press

4. Boissonnat JD, Chazal F, Yvinec M (2018) Geometric and topological inference, vol 57. Cambridge University Press

5. Chen L, Holst M (2011) Efficient mesh optimization schemes based on optimal delaunay triangulations. Computer Methods in Applied Mechanics and Engineering 200(9-12):967–984
6. Chen L, Xu Jc (2004) Optimal delaunay triangulations. Journal of Com- putational Mathematics pp 299–308

7. Chen Z, Wang W, Lévy B, Liu L, Sun F (2014) Revisiting optimal de- launay triangulation for 3d graded mesh generation. SIAM Journal on Scientific Computing 36(3):A930–A954

8. Cheng SW, Dey TK, Shewchuk J (2012) Delaunay mesh generation. CRC Press

9. Cohen-Steiner D, Lieutier A, Vuillamy J (2019) Lexicographic optimal chains and manifold triangulations. Research Report HAL: hal-02391190

10. Cohen-Steiner D, Lieutier A, Vuillamy J (2020) Lexicographic optimal homologous chains and applications to point cloud triangulations. In: 36th International Symposium on Computational Geometry (SoCG 2020), Schloss Dagstuhl-Leibniz-Zentrum für Informatik

11. Delaunay B (1934) Sur la sphere vide. Izv Akad Nauk SSSR, Otdelenie Matematicheskii i Estestvennyka Nauk 7:793–800

12. Edelsbrunner H, Mücke EP (1990) Simulation of simplicity: a technique to cope with degenerate cases in geometric algorithms. ACM Transactions on Graphics (tog) 9(1):66–104

13. Edelsbrunner H, Shah NR (1996) Incremental topological flipping works for regular triangulations. Algorithmica 15(3):223–241

14. Federer H (1959) Curvature measures. Transactions of the American Mathematical Society 93(3):418–491

15. Munkres JR (2018) Elements of algebraic topology. CRC press

16. Rajan V (1994) Optimality of the Delaunay triangulation in $\mathbb{R}^d$. Discrete & Computational Geometry 12(2):189–202

17. Rockafellar RT (1970) Convex analysis, vol 28. Princeton university press

18. Vuillamy J (2021) Simplification planimétrique et chaînes lexicographiques pour la reconstruction 3D de scènes urbaines. PhD thesis, Université Côte d'Azur

# 7 Appendices

## A Overview of the proof

This section, designed as a complementary roadmap, summarizes the argu- ments in the proof's main steps, and illustrates them on Figures 15 and 16. 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.
<figure><img src="image_16.png" /><figcaption>Fig. 15 Flow chart of the main steps of part (A) of the proof of Theorem 1</figcaption></figure>

### 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 $\Gamma_{\text{reg}}$ the simplicial $n$-chain whose support coincides with the regular triangulation, and by $\Gamma_{\min}$ the $n$-chain minimal for order $\sqsubseteq_{\text{lex}}$ under the boundary constraint $\partial\Gamma = \beta_{\mathbf{P}}$. Proving Theorem 1 consists then in proving that $\Gamma_{\min} = \Gamma_{\text{reg}}$.

We assume in step (A), for the sake of contradiction, that $\Gamma_{\min} \neq \Gamma_{\text{reg}}$ (see Figure 15).

Proposition 2 is then established by reusing the observation first made in [6]: the Delaunay (or regular) triangulation in dimension $\mathbb{R}^n$ is equivalent to the convex hull of points in $\mathbb{R}^{n+1}$ where each point $(x_1, \dots, x_n) \in \mathbb{R}^n$ is lifted to a paraboloid as $(x_1, \dots, x_n, \sum_j x_j^2) \in \mathbb{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 $\Gamma_{\text{reg}}$ can be characterized as the chain minimizing the norm $\| \cdot \|_{(p)}$ under the boundary constraint $\partial\Gamma = \beta_{\mathbf{P}}$.

The statement of Proposition 2 is the same as Theorem 1 except for the order along which the minimum is taken: $\Gamma_{\text{reg}}$ minimizes $\| \cdot \|_{(p)}$ while $\Gamma_{\min}$ is minimum for $\sqsubseteq_{\text{lex}}$ (in particular, both statements share the same boundary constraint).

The bounding weight $\mu_B(\sigma)$ is the dominant quantity in the definition of the order on simplices which induces the lexicographic order $\sqsubseteq_{\text{lex}}$ on chains.
For $p$ large enough, $\boldsymbol{\mu}_B(\sigma)$ is also the dominant quantity in $\|\cdot\|_{(p)}$, since $\boldsymbol{\mu}_B(\sigma) = \lim_{p\to\infty} w_p(\sigma)$ and, for $p$ large enough, the weight $w_p(\sigma)^p$ of any single simplex $\sigma$ in the $\|\cdot\|_{(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 $\tau_{\boldsymbol{\mu}_B^\pm}$, inclusion minimal among simplices whose bounding weight $\boldsymbol{\mu}_B^\pm$ is the largest bounding weight for which some simplex in $\Gamma_{\text{reg}}$ and $\Gamma_{\text{min}}$ differ.

At this point, it remains to compare the traces of $\Gamma_{\text{reg}}$ and $\Gamma_{\text{min}}$ in the link of $\tau_{\boldsymbol{\mu}_B^\pm}$, 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 \ge 3$.

## A.2 Case $n < 3$:

For $n=1$, for $p$ large enough, the order $\preceq_{lex}$ and the order induced by comparing $\|\cdot\|_{(p)}$ coincide, so that the result follows immediately from Proposition 2.

For $n=2$, the proof is detailed in [18, 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 $\|\cdot\|_{(p)}$, for $p$ large enough, or for $\preceq_{lex}$ (under boundary constraint) contain generically only one simplex $\sigma$ for each bounding weight $\boldsymbol{\mu}_B(\sigma)$. 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 $\tau_{\boldsymbol{\mu}_B^\pm}$ in step (A) gives the contradiction.

## A.3 Step (B):

The proof for $n \ge 3$ needs to focus on sets of $n$-simplices with same bounding weight $\boldsymbol{\mu}_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 $\boldsymbol{\mu}_B$ are all cofaces of some simplex $\tau$ such that $\boldsymbol{\mu}_B(\tau) = \boldsymbol{\mu}_C(\tau) = \boldsymbol{\mu}_B$.

For example, in the situation of Figure 3, for a Delaunay triangulation in $\mathbb{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(\sigma) = R_C(\sigma)$, there is, under generic condition, a single such tetrahedron abcd.

In the middle, $\tau$ would be the triangle abc and, denoting by $B_B(\tau)$ the unique ball with radius $R_B$ enclosing $\tau$, there is exactly one tetrahedron abcq with bounding radius $R_B$, in the full simplicial complex $K_P$, for each point $q \in B_B(\tau) \cap (P \setminus \{a, b, c\})$. These vertices are in the link of $\tau$.

On the right, $\tau$ would be the edge ab and there is a one-to-one correspondence between tetrahedra abpq with bounding radius $R_B$, in the full simplicial
<figure><img src="image_17.png" /><figcaption>Fig. 16 Flow chart of the main steps of part (B) of the proof of Theorem 1. In this part, one focuses on the subset of the link of the k-simplex $\tau_{\mu_B^\pm}$ defined in step (A), with same bounding radius (or bounding weight) as $\tau_{\mu_B^\pm}$.</figcaption></figure>

complex $K_P$, and edges $p, q \in B_B(\tau) \cap (P \setminus \{a, b\})$. These edges are in the link of $\tau$.

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 $\tau$ in a n-dimensional regular triangulation. The bisector bis$_\tau$ together with the maps $\pi_\tau$, and $\Phi_\tau$, are intermediary constructions allowing to define formally the shadow map Sh$_\tau$:

$$ \mathbf{Sh}_{\tau}: \{\{v\} \in \mathrm{Lk}_{K_P} \tau \mid \mu_B(\tau \cup \{v\}) = \mu_B(\tau)\} \to \mathbb{R}^{n-k} $$

and extend it as a simplicial map that send simplices in:

$$ \{\sigma \in \mathrm{Lk}_{K_P} \tau \mid \mu_B(\tau \cup \sigma) = \mu_B(\tau)\} $$

toward the full simplicial complex over the images of vertices by Sh$_\tau$.

Noting $\tau$ for the k-simplex $\tau_{\mu_B^\pm}$ defined in step (A), with $\mu_B(\tau) = \mu_B^\pm$, the map Sh$_\tau$, allows to compare the traces of $\Gamma_{\mathrm{reg}}$ and $\Gamma_{\mathrm{min}}$ in the link of $\tau = \tau_{\mu_B^\pm}$.

Indeed, denoting $|\Gamma_{\mathrm{reg}}| \subset K_P$ the simplicial complex containing the n-simplices of the regular triangulation of P, the simplicial map induced by Sh$_\tau$ then defines a simplicial isomorphism (Lemma 7 in Section 4.3) between
simplices in the link of $\tau$ in $|\Gamma_{\text{reg}}|$ whose union with $\tau$ does not increases the bounding weight of $\tau$:

$$ \{\sigma \in \text{Lk}_{|\Gamma_{\text{reg}}|} \tau \mid \mu_B(\tau \cup \sigma) = \mu_B(\tau)\}, $$

and the simplices in the visible convex hull, in $\mathbb{R}^{n-k}$, of the images of vertices by $\mathbf{Sh}_{\tau}$. This visible convex hull is a simplicial ball, and therefore,

$$ \{\sigma \in \text{Lk}_{K_{|\Gamma_{\text{reg}}|}} \tau \mid \mu_B(\tau \cup \sigma) = \mu_B^{\neq}\} $$

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 $\tau$ in $|\Gamma_{\text{reg}}|$ but only 2 of them share the same bounding radius as $\tau$, and are therefore in $\{\sigma \in |\Gamma_{\text{reg}}|, \mu_B(\sigma) = \mu_B(\tau)\}$ as seen on Figure 9 top right where only two tetrahedra, in blue, are included in the bounding sphere. In this case, the corresponding simplicial complex $\mathbf{Sh}_{\tau}$ ($\text{Lk}_{\{\sigma \in |\Gamma_{\text{reg}}}|, |\mu_B(\sigma) = \mu_B(\tau)|} \tau$), topologically a 1-dimensional ball, is made of the two edges sharing a vertex, in blue, inside the plane $\mathbf{bis}_{\tau}$ 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 $\sqsubseteq_0$.

The lexicographic order $\sqsubseteq_0$ on the images by $\mathbf{Sh}_{\tau}$ is shown (Lemmas 11 and 12 in Section 6) to be equivalent to the order induced by $\sqsubseteq_{lex}$ on the trace of chains in $\text{Lk}_{\{\sigma \in K_P | \mu_B(\sigma) = \mu_B(\tau)\}} \tau$.

This equivalence between orders allows then to conclude (proof of Theorem 1 in Section 6). Indeed, we have shown that the traces of $\Gamma_{\text{reg}}$ and $\Gamma_{\text{min}}$ in $\text{Lk}_{\{\sigma \in K_P | \mu_B(\sigma) = \mu_B(\tau)\}} \tau$ 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 $\mathbb{R}^n$, its bisector $\mathbf{bis}_{\tau}$, defined by (22), is the $(n-k)$-dimensional affine space, set of points with same weighted distance to each vertex of $\tau$. 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 $\tau$. When $\tau$ is a Delaunay (respectively regular triangulation) simplex, it is also the affine space supporting the Voronoi (respectively power diagram) cell dual to $\tau$. Figure 5 shows the line bisector $\mathbf{bis}_{\tau}$ of an edge $\tau = ab$ in $\mathbb{R}^2$.

**Bounding weight $\mu_B(\sigma)$ of a simplex $\sigma$**: The bounding weight $\mu_B(\sigma)$ of a simplex $\sigma$ is a generalization, for weighted points, of the square of the radius of the smallest ball enclosing the simplex $R_B(\sigma)^2$. It is the dominant term in the definition of the order on simplices which induces the lexicographic order $\sqsubseteq_{lex}$.
on chains. It is formally defined in Definition 7 and is related to the weights $w_p(\sigma)^p$ of simplex $\sigma$ in the norm $\| \cdot \|_{(p)}$ by Lemma 4:

$$ \mu_B(\sigma) = \lim_{p \to \infty} w_p(\sigma) $$

**Full simplicial complex $K_P$ over a set of points:** Given a set of points $P \subset \mathbb{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 $\mathbb{P} > n + 1$.

**Lexicographic order induced by a total order:** It is defined formally in Definition 3. A total order $\le$ on $n$-simplices induces a lexicographic order $\sqsubseteq$ on $n$-chains. Seeing the two $n$-chains $\Gamma_1 \neq \Gamma_2$ with coefficients in $\mathbb{Z}_2$ as sets of $n$-simplices, we write $\Gamma_1 \sqsubseteq \Gamma_2$ if the largest simplex which is in the symmetric difference $(\Gamma_1 \cup \Gamma_2) \setminus (\Gamma_1 \cap \Gamma_2)$, belongs to $\Gamma_2$.

**Lexicographic order $\sqsubseteq_{lex}$:** The lexicographic order $\sqsubseteq_{lex}$ of Theorem 1 is induced by the total order $\le$ on simplices. This total order $\le$ 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 $\mathbb{R}^2$ and $\mathbb{R}^3$.

**Lexicographic order $\sqsubseteq_0$:** The lexicographic order $\sqsubseteq_0$ is induced by the total order $\le_0$ defined by (35) and (36) in Section 5. According to Lemma 10, visible convex hulls are minimum for order $\sqsubseteq_0$ under boundary constraint.

**Norm $\| \cdot \|_{(p)}$:** It is defined in Section 4.1 by (13), as:

$$ \| \Gamma \|_{(p)} = \inf_{\sigma} \sum_{\sigma} |\Gamma(\sigma)| w_p(\sigma)^p. $$

It is a kind of $L^1$ norm on vector $\Gamma$ whose coefficient $w_p(\sigma)^p$, for simplex $\sigma$, is defined, by (12), as the $p^{th}$ power of the $L^p$ norm of function $f_\sigma : \mathcal{CH}(\sigma) \to \mathbb{R}$ defined in (10).

**Restriction $\downarrow_\rho \Gamma$ of a chain $\Gamma$:** For a chain $\Gamma$, we denote by $\downarrow_\rho \Gamma$ the chain obtained by removing from $\Gamma$ all simplices with bounding weight strictly greater than $\rho$: $\downarrow_\rho \Gamma = \{\sigma \in \Gamma, \mu_B(\sigma) \le \rho\}$.

**Shadow map $\mathrm{Sh}_\tau$: (Definition 8).** Given a $k$-simplex $\tau \in K_P$, the shadow map $\mathrm{Sh}_\tau$ is a map that sends the vertices of the link of $\tau$ that belong to simplices with same bounding radius as $\tau$:

$$ \{\{v\} \in \mathrm{Lk}_{K_P} \tau \mid \mu_B(\tau \cup \{v\}) = \mu_B(\tau)\} $$

toward $\mathbb{R}^{n-k}$.

It is a conical projection applied to the images by $\Phi_\tau$, as illustrated on Figure 9, bottom. It follows a sequence of geometric constructions, notably the bisector $\mathrm{bis}_\tau$, and the maps $\pi_\tau$ and $\Phi_\tau$, detailed in Sections 4.2 and 4.3.
The simplicial map induced by the shadow map $\mathbf{Sh}_\tau$ realizes a simplicial isomorphism between the full simplicial complex

$$ \{\sigma \in \mathrm{Lk}_{K_P} \tau \mid \mu_B(\tau \cup \sigma) = \mu_B(\tau)\} $$

and the corresponding full complex over the vertices images.

Moreover, its restriction to $\mathrm{Lk}_{|\Gamma_{\mathrm{reg}}|} \tau$, the support of the link of $\tau$ in the regular triangulation $|\Gamma_{\mathrm{reg}}|$, is a simplicial isomorphism between:

$$ \{\sigma \in \mathrm{Lk}_{|\Gamma_{\mathrm{reg}}|} \tau \mid \mu_B(\tau \cup \sigma) = \mu_B(\tau)\} $$

and the visible convex hull of the vertices images (Lemma 7 in Section 4.3).

As a consequence, $\{\sigma \in \mathrm{Lk}_{|\Gamma_{\mathrm{reg}}|} \tau \mid \mu_B(\tau \cup \sigma) = \mu_B(\tau)\}$ 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 $\tau_1 = ab$ and $\tau_2 = cd$ are edges, then $\tau_1 \cup \tau_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 $\mathcal{CH}(\sigma)$ the convex hull of the vertices of $\sigma$.

**Simplicial chain:** (Section 2.2 or [15, First chapter]). A $k$-simplicial chain $\Gamma$ over a simplicial complex $K$ is a vector, over the field $\mathbb{Z}_2$, defined by associating a coefficient denoted $\Gamma(\sigma) \in \{0, 1\} = \mathbb{Z}_2$ to each $k$-simplex in $K$. It is sometimes convenient to see a $k$-chain also as the set of $k$-simplices $\Gamma = \{\sigma \mid \Gamma(\sigma) = 1\}$. With this convention we allow ourselves to write for example $\Gamma_1 + \Gamma_2 = \Gamma_1 - \Gamma_2 = (\Gamma_1 \cup \Gamma_2) \setminus (\Gamma_1 \cap \Gamma_2)$.

**Simplicial complexes:** (Section 2.1 or [15, First chapter]). A set $K$ of simplices is called a simplicial complex if any $\sigma \in K$ has all its faces in $K$:

$$ (\sigma \in K \text{ and } \emptyset \neq \tau \subseteq \sigma) \Rightarrow \tau \in K $$

Given a simplicial complex $K$, we denote by $K^{[k]}$ the subset of $K$ containing all $k$-simplices in $K$.

**Support $|\Gamma|$ of a simplicial chain $\Gamma$:** The support $|\Gamma|$ of a simplicial $n$-chain $\Gamma$ is the $n$-dimensional simplicial complex made of simplices in $\Gamma$ with all their faces.

**Trace of a chain in the link of a simplex:** (Definition 12). Given a $k$-simplex $\tau \in K$ and a $n$-chain $\Gamma$ on $K$, the trace $\mathrm{Tr}_\tau(\Gamma)$ of $\Gamma$ is a $(n-k-1)$-chain $\mathrm{Tr}_\tau(\Gamma)$ defined in the link $\mathrm{Lk}_K(\tau)$ of $\tau$. For any $(n-k-1)$-simplex $\sigma \in \mathrm{Lk}_K(\tau)$, one has:

$$ \mathrm{Tr}_\tau(\Gamma)(\sigma) = \underset{\mathrm{def.}}{\Gamma(\tau \cup \sigma)} $$
This linear operator commutes with the boundary operator as stated by Lemma 8:

$$ \partial \mathrm{Tr}_{\tau}(\Gamma) = \mathrm{Tr}_{\tau}(\partial \Gamma) $$

**Visible convex hull:** Definition 10 formally defines a polytope facet **visible** from the point 0. Given a finite set of points $P \in \mathbb{R}^m$ in general position (no $m+1$ points lie on the same affine $(m-1)$-space), whose convex hull $\mathcal{CH}(P)$ does not contain the point $0 \in \mathbb{R}^m$. The **visible convex hull** is the $(m-1)$-simplicial complex embedded in $\mathbb{R}^m$ corresponding to the subset of the boundary $\partial \mathcal{CH}(P)$ of $\mathcal{CH}(P)$ “visible” from the point 0. In other word, its image by the embedding in $\mathbb{R}^m$ is the set of points $x \in \partial \mathcal{CH}(P)$ such that the segment $[0, x)$ does not intersect $\mathcal{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, \mu_1), (P_2, \mu_2)) = \underset{\text{def.}}{(P_1 - P_2)^2 - \mu_1 - \mu_2} $$

B Invariance by global weight translation

**Observation 8** Let $\psi_{\lambda}: \mathbb{R}^n \times \mathbb{R} \to \mathbb{R}^n \times \mathbb{R}$, be the transformation that shifts the weight by $\lambda$:

$$ \psi_{\lambda}(P, \mu) = (P, \mu + \lambda) $$

Let $\sigma \in K_P$ be a simplex, from definitions 7 and 1 we have:

$$ P_C(\psi_{\lambda}(\sigma)) = P_C(\sigma) \quad \text{and} \quad \mu_C(\psi_{\lambda}(\sigma)) = \mu_C(\sigma) - \lambda $$

$$ P_B(\psi_{\lambda}(\sigma)) = P_B(\sigma) \quad \text{and} \quad \mu_B(\psi_{\lambda}(\sigma)) = \mu_B(\sigma) - \lambda $$

It follows that a global shift by a constant value $\lambda$ results in an opposite shift on the weights of generalized circumcenters. It therefore preserves the relative order between simplices weights $\mu_C$ and $\mu_B$:

$$ \mu_C(\sigma_1) \le \mu_C(\sigma_2) \iff \mu_C(\psi_{\lambda}(\sigma_1)) \le \mu_C(\psi_{\lambda}(\sigma_2)) $$

and the same relation holds for $\mu_B$. Since the order $\le$ between simplices (9) defined in section 3.5 relies entirely on comparisons on $\mu_C$ and $\mu_B$, this total order is preserved by a global weight translation.
C Proof of Lemma 1 on page 14

Figure 3 page 12 illustrates the possibilities for $\Theta(\sigma)$ in the case $n = 3$ and zero weights.

*Proof* Recall relation (6) in Definition 7 on page 13.

Denote by $\tau \subset \sigma$ the set of vertex $(P_i, \mu_i) \in \sigma$ for which:

$$D((\mathbf{P}_B(\sigma), \mu_B(\sigma)), (P_i, \mu_i)) = 0$$

This set cannot be empty as, if all inequalities in (6) where strict, a strictly smaller value of $\mu$ would still match the inequality, which would contradict with the arg min in (6). One has then $\tau \neq \emptyset$ and:

$$\forall (P_i, \mu_i) \in \tau, D((\mathbf{P}_B(\sigma), \mu_B(\sigma)), (P_i, \mu_i)) = 0 \quad (50)$$

and therefore $(\mathbf{P}_B(\sigma), \mu_B(\sigma))$ also meet the condition required for $(\mathbf{P}_B(\tau), \mu_B(\tau))$ in (6) of Definition 7:

$$\forall (P_i, \mu_i) \in \tau, D((\mathbf{P}_B(\sigma), \mu_B(\sigma)), (P_i, \mu_i)) \le 0 \quad (51)$$

No point $(P, \mu)$ with $\mu < \mu_B(\sigma)$ can satisfies (50) or (51) as it would again similarly contradict the arg min in (6). It follows that:

$$(\mathbf{P}_B, \mu_B)(\sigma) = (\mathbf{P}_B, \mu_B)(\tau) = (\mathbf{P}_C, \mu_C)(\tau)$$

D Proof of Lemma 3 on page 17

*Proof* The idea of the proof is to shoot a ray from a point $x \in \mathcal{CH}(\mathbf{P})$, that does not belong to the convex hull of any $(n-1)$-simplex, to the outside of the convex hull $\mathcal{CH}(\mathbf{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 $\sigma \in \Gamma$ such that $y \in \mathcal{CH}(\sigma)$.

We claim that since $x \in \mathcal{CH}(\mathbf{P}) \setminus \bigcup_{\sigma \in K_{\mathbf{P}}^{[n-1]}} \mathcal{CH}(\sigma)$ there is $x_* \in \mathbb{R}^n \setminus \mathcal{CH}(\mathbf{P})$ such that:

$$[x_* x] \cap \bigcup_{\sigma \in K_{\mathbf{P}}^{[n-2]}} \mathcal{CH}(\sigma) = \emptyset \quad (52)$$

where $[x_* x]$ denotes the line segment in $\mathbb{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] \cap \mathcal{CH}(\mathbf{P}) = \emptyset$ 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_{\mathbf{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 $\mathcal{CH}(\tau)$, for $\tau \in K_{\mathbf{P}}$. At each
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_\star$ since $x_\star \notin \mathcal{CH}(\mathbf{P})$. Since $\mathcal{CH}(\mathbf{P}) \cap [x_\star x]$ is convex there is a single intersection point $y(t_b)$ between $[x_\star x]$ and the boundary of $\mathcal{CH}(\mathbf{P})$.

This point $y(t_b) \in (x_\star, x)$ hits the convex hull $\mathcal{CH}(\tau_b)$ of a $(n-1)$-simplex $\tau_b \in \beta_{\mathbf{P}}$, face of the convex hull boundary. Since $\partial\Gamma = \beta_{\mathbf{P}}$, we know that $\tau_b$ is shared by an odd number $n_b$ of $n$-simplices in $\Gamma$. By definition of the convex hull, and since $\mathbf{P}$ is in general position, for each $n$-simplex $\sigma$ coface of $\tau_b$, $\mathcal{CH}(\sigma)$ is on the inner side of the convex hull supporting halfspace. It follows that, starting from the outer point $x_\star$, 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 $\mathcal{CH}(\tau_i)$ of any other $(n-1)$-simplex $\tau_i \notin \beta_{\mathbf{P}}$, at some point $y(t_i)$, it follows from the condition $\partial\Gamma = \beta_{\mathbf{P}}$ that the number $n_i$ of $n$-simplices in $\Gamma$ coface of $\tau_i$ has to be even. When crossing $\mathcal{CH}(\tau_i)$, along $[x_\star x]$, point $y(t_i)$ exits $k^-$, and enters $k^+$ $n$-simplices in $\Gamma$, 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 (10) does not depend on the origin $O$, let us choose this origin to be $O = \mathbf{P}_B(\sigma)$. With barycentric coordinates based on the vertices $P_i, i = 0, k$ of $\sigma$, i.e. $\lambda_i \ge 0$, $\sum_i \lambda_i = 1$ such that $x = \sum_i \lambda_i P_i$, the expression of $f_\sigma$ is:

$$f_\sigma(x) = \left( \sum_i \lambda_i ((P_i - \mathbf{P}_B(\sigma))^2 - \mu_i) \right) - (x - \mathbf{P}_B(\sigma))^2$$

one has $(P_i - \mathbf{P}_B(\sigma))^2 - \mu_i - \mathbf{\mu}_B(\sigma) = \mathrm{D}((\mathbf{P}_B(\sigma), \mathbf{\mu}_B(\sigma)), (P_i, \mu_i)) \le 0$ so that $(P_i - \mathbf{P}_B(\sigma))^2 - \mu_i \le \mathbf{\mu}_B(\sigma)$ and it follows that:

$$\forall x, f_{\sigma}(x) \le \mathbf{\mu}_{B}(\sigma) - (x - \mathbf{P}_{B}(\sigma))^2 \quad (53)$$

We have from Lemma 2 that $\mathbf{P}_B(\sigma) \in |\Theta(\sigma)| \subset \mathcal{CH}(\sigma)$ so that, in the expression of $\mathbf{P}_B(\sigma)$ as a barycenter of vertices of $\sigma$, only coefficients $\lambda_i$ corresponding to vertices of $\Theta(\sigma) \subset \sigma$ are non-zero:

$$\mathbf{P}_B(\sigma) = \sum_{(P_i, \mu_i) \in \Theta(\sigma)} \lambda_i P_i$$
One has by definition of $(\mathbf{P}_C, \mu_C)$:

$$ (P_i, \mu_i) \in \Theta(\sigma) \Rightarrow (P_i - \mathbf{P}_C(\Theta(\sigma)))^2 - \mu_i = \mu_C(\Theta(\sigma)) $$

and since we know from Lemma 1 that:

$$ (\mathbf{P}_B, \mu_B)(\sigma) = (\mathbf{P}_B, \mu_B)(\Theta(\sigma)) = (\mathbf{P}_C, \mu_C)(\Theta(\sigma)) $$

one gets:

$$ (P_i, \mu_i) \in \Theta(\sigma) \Rightarrow (P_i - \mathbf{P}_B(\sigma))^2 - \mu_i = \mu_B(\sigma) $$

and:

$$ f_{\sigma}(\mathbf{P}_B(\sigma)) = \left( \sum_{(P_i, \mu_i) \in \Theta(\sigma)} \lambda_i ((P_i - \mathbf{P}_B(\sigma))^2 - \mu_i) \right) - 0^2 = \mu_B(\sigma) $$

This with (53) ends the proof.

## 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 $\rho > 0$ such that $B(x, \rho) \cap X = B(x, \rho) \cap \partial 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 $\partial C$ with $\dim f \ge 1$. Then we have a contradiction since the function $y \mapsto 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 [14, 17], denote by $\text{Tan}_x C$ and $\text{Nor}_x C$ respectively the tangent and normal cone to $C$ at $x$. In case of a closed polytope they can be expressed as:

$$ \text{Tan}_x C = \bigcap_{\rho>0} \{\lambda(c-x), \lambda \ge 0, c \in \mathcal{B}(x, \rho)\}, $$

where $\mathcal{B}(x, \rho)$ denotes the ball centered at $x$ with radius $\rho$, and

$$ \text{Nor}_x C = (\text{Tan}_x C)^{\perp} = \underset{\text{def.}}{\{u, \forall v \in \text{Tan}_x C, \langle u, v \rangle \le 0\}} \quad (54) $$

Since $C$ is a convex polytope, $\text{Tan}_x C$ is a convex closed cone and one has [17]:

$$ \text{Nor}_x C = (\text{Nor}_x C)^{\perp} = \underset{\text{def.}}{\{v, \forall u \in \text{Nor}_x C, \langle u, v \rangle \le 0\}} \quad (55) $$

Each facet $F_i$ of $C$ containing $x$ is supported by a half-space $H_i = \{y, \langle y - x, n_i \rangle \le 0\}$ with outer normal $n_i$, and one has:

$$ \text{Nor}_x C = \left\{ \sum_i \lambda_i n_i, \forall i, \lambda_i \ge 0 \right\} \quad (56) $$
and, since $O$ belongs to none of the half-spaces $H_i$:

$$ \forall i, \langle O - x, n_i \rangle > 0 $$

This with (56) gives:

$$ \forall u \in \mathrm{Nor}_x C, \langle O - x, u \rangle > 0 \qquad (57) $$

using (55) we get that $O - x$ is in the interior of $-\mathrm{Tan}_x C$ i.e.:

$$ x - O \in (\mathrm{Tan}_x C)^{\circ} \qquad (58) $$

Since $x$ is a vertex of $C$, $\mathrm{Tan}_x C$ is the convex hull of $\mathrm{Tan}_x \partial C$, therefore (58) implies at there are $t_1, \dots, t_{n+1} \in \mathrm{Tan}_x \partial C$ and $\lambda_1, \dots, \lambda_{n+1} \ge 0$ such that:

$$ x - O = \sum_{i} \lambda_{i} t_{i} $$

which gives, since $O \notin C$:

$$ 0 < \langle x - O, x - O \rangle = \langle x - O, \sum_{i} \lambda_{i} t_{i} \rangle = \sum_{i} \lambda_{i} \langle x - O, t_{i} \rangle $$

Since all the $\lambda_i$ are not negative, there must be at least one $i$ for which:

$$ \langle x - O, t_i \rangle > 0 $$

This precisely means that $y \mapsto d(O, y)$ is increasing in the direction $t_i$ in a neighborhood of $x$ in $\partial C$, and, with the assumption that $x$ is in the relative interior of $X$, we have that $y \mapsto d(O, y)$ is increasing in the direction $t_i$ in a neighborhood of $x$ in $X$. This gives a contradiction since $x$ is assumed to be a local maximum of $y \mapsto d(O, y)$ in $X$.

G Proof of Lemma 11 on page 34

*Proof* Using Definition 7 page 13, one has:

$$ \begin{array}{l} (\mathbf{P}_C, \mu_C)(\pi_\tau(\tau) \cup \pi_\tau(\sigma)) = \underset{(P, \mu) \in \mathbb{R}^n \times \mathbb{R}}{\arg\min} \mu \qquad (59) \\ \forall (P_i, \mu_i) \in \pi_\tau(\tau) \cup \pi_\tau(\sigma), \\ \mathrm{D}((P, \mu), (P_i, \mu_i)) = 0 \end{array} $$

Looking at Definition 7 in light of (28), page 23, in the proof of Lemma 6, we get that:

$$ \sigma \supset \tau \Rightarrow \mu_C(\sigma) = \mu_C(\pi_\tau(\sigma)) \text{ and } \mathbf{P}_C(\sigma) = \mathbf{P}_C(\pi_\tau(\sigma)) \qquad (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_\tau = 0$.
In this case, as seen in (24), page 22, the coordinates of $\pi_{\tau}(\tau)$ are $(0, -\boldsymbol{\mu}_{C}(\pi_{\tau}(\tau)) = (0, -\boldsymbol{\mu}_{C}(\tau))$ by (60). So that $D((P, \mu), \pi_{\tau}(\tau)) = 0$ gives us:

$$ \mu = P^2 + \boldsymbol{\mu}_{C}(\tau) \qquad (61) $$

It follows that among the weighted points $(P, \mu)$ that satisfy $D((P, \mu), \pi_{\tau}(\tau)) = 0$, minimizing $\mu$ is equivalent to minimizing $P^2$.

One can reformulate the characterization (59) of $(\mathbf{P}_C, \boldsymbol{\mu}_C)(\pi_{\tau}(\tau) \cup \sigma)) = (\mathbf{P}_C, \boldsymbol{\mu}_C)(\pi_{\tau}(\tau) \cup \pi_{\tau}(\sigma))$ as:

$$ (\mathbf{P}_C, \boldsymbol{\mu}_C)(\pi_{\tau}(\tau) \cup \pi_{\tau}(\sigma)) = \begin{array}{l} \underset{(P, \mu) \in \mathbb{R}^n \times \mathbb{R}}{\arg \min} \quad P^2 \qquad (62) \\ \forall (P_i, \mu_i) \in \pi_{\tau}(\tau) \cup \pi_{\tau}(\sigma), \\ D((P, \mu), (P_i, \mu_i)) = 0 \end{array} $$

For $(P, \mu) \in \mathbb{R}^{n-k} \times \mathbb{R}$, define the hyperplane $\Pi_{(P,\mu)}$ in $\mathbb{R}^{n-k} \times \mathbb{R}$ as:

$$ (X, z) \in \Pi_{(P, \mu)} \iff_{\text{def.}} z = \mu - P^2 + 2\langle P, X \rangle \qquad (63) $$

Observe that:

$$ D((P, \mu), (P_i, \mu_i)) = 0 \iff \text{lift}(P_i, \mu_i) \in \Pi_{(P, \mu)} $$

So that the definition of $(\mathbf{P}_C, \boldsymbol{\mu}_C)(\pi_{\tau}(\tau) \cup \pi_{\tau}(\sigma))$ given in (62) can be equivalently formulated as $\Pi_{(\mathbf{P}_C, \boldsymbol{\mu}_C)}$ being the hyperplane in $\mathbb{R}^{n-k} \times \mathbb{R}$ that minimizes $\mathbf{P}_C^2$ among all hyperplanes containing both $\text{lift}(\pi_{\tau}(\tau))$ and all the points in $\text{lift}(\pi_{\tau}(\sigma))$.

But, as seen on (63), $2\|\mathbf{P}_C\|$ is the slope of the hyperplane $\Pi_{(\mathbf{P}_C, \boldsymbol{\mu}_C)}$ so that $\Pi_{(P,\mu)}$ is the hyperplane with minimal slope going through $\Phi_{\tau}(\tau) = \text{lift}(\pi_{\tau}(\tau))$ and all the points in $\Phi_{\tau}(\sigma) = \text{lift}(\pi_{\tau}(\sigma))$. This slope $2\|\mathbf{P}_C\|$ is also the slope of the unique $(\text{dim}(\sigma) + 1)$-dimensional affine space $F$ going through $\Phi_{\tau}(\tau) = \text{lift}(\pi_{\tau}(\tau)) = (0, \boldsymbol{\mu}_C(\tau))$ and all the points in $\Phi_{\tau}(\sigma) = \text{lift}(\pi_{\tau}(\sigma))$. Since $F \cap \mathbb{R}^{n-k} \times \{0\}$ is the affine space supporting $\mathbf{Sh}_{\tau}(\sigma)$, one has:

$$ d_0(\mathbf{Sh}_{\tau}(\sigma)) = \frac{\boldsymbol{\mu}_C(\tau)}{2\|\mathbf{P}_C(\pi_{\tau}(\tau) \cup \pi_{\tau}(\sigma))\|} $$

so that, using (60) for the second equality:

$$ d_0(\mathbf{Sh}_{\tau}(\sigma)) = \frac{\boldsymbol{\mu}_C(\tau)}{2\sqrt{\boldsymbol{\mu}_C(\pi_{\tau}(\tau) \cup \pi_{\tau}(\sigma)) - \boldsymbol{\mu}_C(\tau)}} = \frac{\boldsymbol{\mu}_C(\tau)}{2\sqrt{\boldsymbol{\mu}_C(\tau \cup \sigma) - \boldsymbol{\mu}_C(\tau)}} $$

It follows that the map:

$$ \boldsymbol{\mu}_C(\tau \cup \sigma) \to d_0(\mathbf{Sh}_{\tau}(\sigma)) $$

is decreasing.
H Proof of Lemma 12 page 34

*Proof* In this proof, we denote by $\xrightarrow{\rho} \Gamma$ the set of simplices in $\Gamma$ with bounding weight equal to $\rho$:

$$ \xrightarrow{\rho} \Gamma \stackrel{\text{def.}}{=} \{\sigma \in \Gamma, \mu_B(\sigma) = \rho\} $$

We claim that:

$$ (\downarrow_{\rho} \Gamma_1 \sqsubseteq_{lex} \downarrow_{\rho} \Gamma_2) \Rightarrow \left( \xrightarrow{\rho} \Gamma_1 \sqsubseteq_{lex} \xrightarrow{\rho} \Gamma_2 \right) \qquad (64) $$

Indeed, by definition of the lexicographic order, if this did not hold, it would imply $\xrightarrow{\rho} \Gamma_1 \neq \xrightarrow{\rho} \Gamma_2$ and the largest simplex for which $\xrightarrow{\rho} \Gamma_1$ and $\xrightarrow{\rho} \Gamma_2$ differ would be in $\Gamma_1$ contradicting $\downarrow_{\rho} \Gamma_1 \sqsubseteq_{lex} \downarrow_{\rho} \Gamma_2$ which proves the claim (64).

Note that, from Lemma 1 and generic condition 1, page 14, all the simplices in $\xrightarrow{\rho} \Gamma_1$ and $\xrightarrow{\rho} \Gamma_2$ are in the star of a single simplex $\tau = \tau_{\rho}$ such that $\mu_C(\tau) = \mu_B(\tau) = \rho$.

It remains to show that the order $\sqsubseteq_{lex}$ restricted to simplices $\tau \cup \sigma$ with $\mu_B(\tau \cup \sigma) = \rho$ corresponds to the order $\sqsubseteq_0$ on the shadow of $\sigma$.

By definition of $\sqsubseteq_{lex}$, since in (9) one has always $\mu_0(\tau \cup \sigma_1) = \mu_0(\tau \cup \sigma_2) = \rho$, it goes like this:

$$ \sigma_1 < \sigma_2 \iff_{\text{def.}} \left\{ \begin{array}{l} \exists k \ge 1, \mu_k(\tau \cup \sigma_1) > \mu_k(\tau \cup \sigma_2) \\ \text{and } \forall j, 0 \le j < k, \mu_j(\tau \cup \sigma_1) = \mu_j(\tau \cup \sigma_2) \end{array} \right. \qquad (65) $$

Observe that this expression is similar to (35).

For a 0-simplex $\{v\} \in K_P$, the circumweight $\mu_C(\tau \cup \{v\})$ is, according to Lemma 11, a decreasing function of the distance $d_0(\text{Sh}_{\tau}(\eta))$ between its shadow and the origin. It follows that for a $(n-k-1)$-simplex $\sigma \in K_P$, the vertex $v$ for which the circumweight $\mu_C(\tau \cup \{v\})$ is minimal has its shadow $\text{Sh}_{\tau}(v)$ maximizing the distance to the origin. This minimal circumweight is $\mu_1(\tau \cup \{v\})$ while this maximal distance is $\delta_0(\sigma)$.

More generally, looking at (34) and (8), Lemma 11 allows to check that the simplex $\Theta_k(\sigma)$ of (8) in the star of $\tau$ in $K_P$ corresponds to the simplex $\tau_{k-1}(\sigma)$ in (34) in the link of $\tau$:

$$ \Theta_k(\sigma) = \tau \cup \tau_{k-1}(\sigma) $$

So that for $\sigma_1, \sigma_2 \in K_P$ referring to (35) and (65):

$$ \mu_k(\tau \cup \sigma_1) \le \mu_k(\tau \cup \sigma_2) \iff \delta_{k-1}(\sigma_1) \ge \delta_{k-1}(\sigma_2) $$

It follows that, for $\Gamma_1, \Gamma_2 \in C_n(K_P)$ and $\tau = \tau_{\rho}$:

$$ \xrightarrow{\rho} \Gamma_1 \sqsubseteq_{lex} \xrightarrow{\rho} \Gamma_2 \iff \left\{ \begin{array}{l} \text{Sh}_{\tau} (\text{Tr}_{\tau_{\rho}} (\downarrow_{\rho} \Gamma_1)) \\ \sqsubseteq_0 \text{Sh}_{\tau_{\rho}} (\text{Tr}_{\tau_{\rho}} (\downarrow_{\rho} \Gamma_2)) \end{array} \right. $$

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 $\mathbb{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 $\mathbb{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.