Aruni Choudhary

Mathijs Siargey Kachanovich

Mathijs Wintraecken

Wintraecken 2017 Coxeter

Coxeter triangulations have good quality

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

Introduction 1.Objectives and motivation

Well shaped simplices are of importance for various fields of application such as finite element methods and manifold meshing [START_REF] Babuška | On the angle condition in the finite element method[END_REF][START_REF] Cheng | Manifold reconstruction from point samples[END_REF][START_REF] Cheng | Delaunay mesh generation[END_REF][START_REF] Jamet | Estimations d'erreur pour des éléments finis droits presque dégénérés[END_REF][START_REF] Křížek | On the maximum angle condition for linear tetrahedral elements[END_REF][START_REF] Lighton | The hypercircle in mathematical physics[END_REF]. Poorly-shaped simplices may induce various problems in finite element method, such as large discretization errors or ill-conditioned stiffness matrices. A simplex is well shaped if its quality is good, which can be expressed in terms of various quality measures. Some examples of quality measures are: the ratio between minimal height and maximal edge length ratio called thickness [START_REF] James R Munkres | Elementary differential topology[END_REF][START_REF] Stephen | Stable finite elements for problems with wild coefficients[END_REF], the ratio between volume and a power of the maximal edge length called fatness [START_REF] Whitney | Geometric integration theory[END_REF], and the inradius-circumradius ratio [START_REF] Cavendish | An apporach to automatic three-dimensional finite element mesh generation[END_REF]. Bounds on dihedral angles can also be included in the list of quality measures. We stress that there are many other quality measures in use and authors often find useful to introduce measures that are specific to whatever problem they study. Finding triangulations, even in Euclidean space, of which all simplices have good quality is a non-trivial exercise in arbitrary dimension.

In this paper we shall discuss Coxeter triangulations.

Definition 1.1. A monohedral 1 triangulation is called Coxeter triangulation if all its d-simplices can be obtained by consecutive reflections through facets of the d-simplices in the triangulation.

To our knowledge, these are the triangulations with the best quality in arbitrary dimension. In particular, all dihedral angles of simplices in Coxeter triangulations are 45 • , 60 • or 90 • , with the exception of the so-called G2 triangulation of the plane where we also can find an angle of 30 • . This is a clear sign of the exceptional quality of the simplices involved. Our goal is to exhibit the extraordinary properties of Coxeter triangulations and promote their use in the Computational Geometry community.

The self-similarity and symmetry are another of the attractive points of Coxeter triangulations. Upon the first introduction, an unprepared reader might expect that the vertex sets of such triangulations form lattices, however it is not necessarily true, as we show in Section 5.

We are also interested in the stronger requirement of protection [START_REF] Boissonnat | The stability of Delaunay Triangulations[END_REF], which is specific to Delaunay triangulations. For a point set to have a unique well defined Delaunay triangulation in the Euclidean space R d one demands that there are no d + 2 co-spherical points such that the interior of the sphere is empty in a vertex set. Protection requires not only that there is no other vertex on the (empty) circumsphere of d + 1 vertices, but that any other vertex is at distance δ away from the circumsphere. It has been proven that protection guarantees good quality [START_REF] Boissonnat | The stability of Delaunay Triangulations[END_REF]. Some algorithms were introduced for the construction of a protected set, such as the perturbation-based algorithms in [START_REF] Boissonnat | Delaunay stability via perturbations[END_REF] and [START_REF] Boissonnat | A Probabilistic Approach to Reducing Algebraic Complexity of Delaunay Triangulations[END_REF]. Both of these algorithms take a general ε-net in R d as input and output a δ-protected net with δ of the order just Ω(2 -d 2 ε). An example of the d-dimensional Coxeter triangulation Ãd provides us another extremity. As we will see in the following, this highly-structured triangulation is Delaunay with protection O( 1 d 2 ε). This protection value is the greatest in a general d-dimensional Delaunay triangulation we know.

Related work

The notion of Coxeter triangulations was introduced to the computational geometry community by Dobkin, Wilks, Levy and Thurston in [START_REF] David P Dobkin | Contour tracing by piecewise linear approximations[END_REF], where they tackled the problem of contour-tracing in R d . The choice of Coxeter triangulations was motivated by the following requirements:

• It should be easy to find the simplex that shares a facet with a given simplex.

• It should be possible to label the vertices of all the simplices at the same time with indices 0, . . . , d, in such a way that each of the d + 1 vertices of a d-simplex has a different label.

• The triangulations should be homogeneous, meaning that all simplices are congruent.

• All simplices should be isotropic, meaning that they should be roughly the same in all directions.

Thanks to the definition, this is exactly what Coxeter triangulations do. After comparing the inradiuscircumradius ratio of the simplices in the triangulations they chose the Ãd Coxeter triangulation as the underlying triangulation for their contour-tracing algorithm.

Adams, Baek and Davis [START_REF] Adams | Fast High-Dimensional Filtering Using the Permutohedral Lattice[END_REF] chose the vertex set of Ãd Coxeter triangulation, also known as the permutahedral lattice, to accelerate the high-dimensional Gaussian filtering algorithm. This choice was again motivated by the fact that the triangulation has congruent and isotropic simplices.

The Ãd Coxeter triangulation was also used to approximate the Rips filtration of n points in R d in a recent work by Choudhary, Kerber and Raghvendra [START_REF] Choudhary | Polynomial-sized Topological Approximations using the Permutahedron[END_REF]. The authors arrived at an approximation scheme that achieved a significant reduction in size of the complex. The improvement came primarily from the fact that the permutahedral lattice is very well protected.

Coxeter triangulations also played an important role in [START_REF] Bogdanov | Delaunay triangulations on orientable surfaces of low genus[END_REF][START_REF] Iordanov | Implementing Delaunay triangulations of the Bolza surface[END_REF].

The Coxeter triangulations we study are intricately linked with root systems and root lattices. Delaunay triangulations of the root lattices have been studied by Conway and Sloane [START_REF] Conway | Sphere-packings, Lattices, and Groups[END_REF] and Moody and Patera [START_REF] Robert | Voronoi and Delaunay cells of root lattices: classification of their faces and facets by Coxeter-Dynkin diagrams[END_REF]. These triangulations are different from the ones we study: the vertex sets we use are not necessarily lattices.

The three-dimensional Coxeter triangulation Ã3 has attracted attention in the 3D mesh generation community for the high-quality of its simplices. The vertex set of this triangulation is also known as the body-centred cubic lattice, or bcc lattice, and its tetrahedron is sometimes referred as Sommerville's type II tetrahedron (after [START_REF] Dmy Sommerville | Space-filling tetrahedra in Euclidean space[END_REF]) or simply bcc-tetrahedron. This tetrahedron has been shown in [START_REF] David | Filling space with tetrahedra[END_REF] to be the best-conditioned space-filling tetrahedron out of all space-filling tetrahedra used in the 3D mesh community by a number of conditioning measures. This work led to the use of the bcc lattice in the isosurface stuffing algorithm [START_REF] Labelle | Isosurface stuffing: fast tetrahedral meshes with good dihedral angles[END_REF].

Other examples of the use of the bcc lattice include the optimal sampling in image processing [START_REF] Theußl | Optimal regular volume sampling[END_REF] and improving on the marching tetrahedra algorithm for isosurface extraction [START_REF] Graham M Treece | Regularised marching tetrahedra: improved iso-surface extraction[END_REF]. In both papers the main reason behind the choice of the bcc lattice was its sparse covering. This makes the sampling algorithm achieve the same accuracy as the usual cubic lattice with about 29.3% fewer samples.

Lastly, an observation that a bcc tetrahedron can be divided into eight half-sized bcc tetrahedra was used to make a variation of the octree algorithm [START_REF] David | Graded tetrahedral finite element meshes[END_REF].

Contribution

In this paper we give explicit expressions of a number of quality measures of Coxeter triangulations for all dimensions, presented in Section 5. This is an extension of the work by Dobkin et al. [START_REF] David P Dobkin | Contour tracing by piecewise linear approximations[END_REF] who presented a table of the values of the inradius-circumradius ratio for the Coxeter triangulations up to dimension 8. We also provide explicit measures of the corresponding simplices in Appendix B, allowing the reader to compute quality measures other than the ones listed.

In Section 3, we state the theorem of optimality of the regular d-simplex for each of the chosen quality measures. This theorem gives us right to work with normalized versions of these quality measures.

In Section 4, we established a criterion to identify if any given monohedral triangulation is Delaunay. We also give a presentation of the theory of root systems in Appendix A. This presentation mostly follows the lecture notes of Jaap Top (in Dutch) [START_REF] Top | Dynkin diagrammen en Wortelsystemen[END_REF] and a classical book by Humphreys [START_REF] Humphreys | Reflection groups and Coxeter groups[END_REF] for the part on affine Weyl groups.

Future work

The simplex qualities, defined in Definition 3.1, of the four families of Coxeter triangulations behave as O(1/ √ d) in terms of dimension. We conjecture that this quality is optimal for a general space-filling triangulation in R d . In addition, the d-dimensional Coxeter triangulation Ãd has the relative Delaunay protection O(1/d 2 ). We further conjecture that it is optimal for a general space-filling triangulation in R d . These conjectures are motivated by the extraordinary lower and upper bounds on the dihedral angles of simplices in Coxeter triangulations, they are precisely 45 • , 60 • or 90 • for the four families. Moreover the circumcentre of the simplices of Ãd lie very far inside the simplex.

Brief introduction to Coxeter triangulations

In this section we will give all the information about Coxeter triangulations, necessary for the understanding of the later sections. For the extended introduction we refer the reader to Appendix A, but also to the pioneering paper on reflection groups by Coxeter [START_REF] Harold | Discrete groups generated by reflections[END_REF] and the classical book on Lie groups and algebras by Bourbaki [START_REF] Bourbaki | Lie groups and Lie algebras[END_REF]. Another classical reference book is "Sphere packings, Lattices, and Groups" by Conway and Sloane [START_REF] Conway | Sphere-packings, Lattices, and Groups[END_REF], upon which we draw for our geometric analysis of triangulations in Appendix B.

As we see in Appendices A.4 and A.5, the definition of Coxeter triangulations restricts the possible dihedral angles of the corresponding simplices. Indeed, the only possible dihedral angles are π 2 , π 3 , π 4 and π 6 . This information can be represented in a graph. Definition 2.1. Let T be a Coxeter triangulation in R d and σ ∈ T be its d-simplex. The Coxeter diagram of σ consists of a graph with the following data. For each facet τ of σ we insert one vertex. For every pair (τ, τ ) of facets in σ we define a number m(τ, τ ) ∈ {2, 3, 4, 6}, such that the dihedral angle ϕ between τ and τ satisfies ϕ = π m(τ,τ ) . We then insert an edge between τ and τ and write the number m(τ, τ ) next to it. We further follow the convention not to draw an edge labelled 2 and not denote the label 3 next to an edge.

The Coxeter diagram of T is the Coxeter diagram of any of its simplices.

There are exactly four families of Coxeter diagrams and five exceptional diagrams.

Theorem 2.2. The complete list of Coxeter diagrams is given in Figure 1. The vertices of simplices that correspond to these Coxeter diagrams up to similarity transformations are given in Table 1.

Ãd , d 2 ... Bd , d 3
All three two-dimensional Coxeter triangulations are presented in Figure 2. Figure 3 illustrates the simplices of the three-dimensional Coxeter triangulations with vertices placed in vertices, centres of edges, centres of faces and at the centre of a cube.

Quality definitions

The quality measures we are interested in, we call aspect ratio, fatness, thickness and radius ratio. Their formal definitions are as follows: Definition 3.1. Let h(σ) denote the minimal height, r(σ) the inradius, R(σ) the circumradius, vol(σ) the volume and L(σ) the maximal edge length of a given d-simplex σ.

• The aspect ratio of σ is the ratio of its minimal height to the diameter of its circumscribed ball: α(σ) = h(σ) 2R(σ) .

• The fatness of σ is the ratio of its volume to its maximal edge length taken to the power d:

Θ(σ) = vol(σ) L(σ) d .
• The thickness of σ is the ratio of its minimal height to its maximal edge length:

θ(σ) = h(σ) L(σ) . Ãd , given in R d+1 , d ≥ 2 u 0 = 0 {d+1} u k = (-d+1-k d+1 ) {k} , ( k d+1 ) {d+1-k} , ∀k ∈ {1, . . . , d} Bd , given in R d , d ≥ 3 u 0 = 0 {d} u 1 = 1, 0 {d-1} u k = 1 2 {k} , 0 {d-k} , ∀k ∈ {2, . . . , d} Cd , given in R d , d ≥ 2 u k = 1 2 {k} , 0 {d-k} , ∀k ∈ {0, . . . , d} Dd , given in R d , d ≥ 4 u 0 = 0 {d} u 1 = 1, 0 {d-1} u k = 1 2 {k} , 0 {d-k} , ∀k ∈ {2, . . . , d -2} u d-1 = 1 2 {d-1} , -1 2 u d = 1 2 {d} Ẽ6 , given in R 8 u 0 = 0 {8} u 1 = 0 {5} , -2 3 {2} , 2 3 u 2 = 1 4 {5} , -1 4 {2} , 1 4 u 3 = -1 4 , 1 4 {4} , -5 12
{2} , 5 12
u 4 = 0 {2} , 1 3 {3} , -1 3 {2} , 1 3 u 5 = 0 {3} , 1 2 {2} , -1 3 {2} , 1 3 u 6 = 0 {4} , 1, -1 3 {2} , 1 3 Ẽ7 , given in R 8 u 0 = 0 {8} u 1 = 0 {6} , 1 2 , -1 2 u 2 = -1 4 {6} , 1 2 , -1 2 u 3 = 1 6 , -1 6 {5} , 1 2 , -1 2 u 4 = 0 {2} , -1 4 {4} , 1 2 , -1 2 u 5 = 0 {3} , -1 3 {3} , 1 2 , -1 2 u 6 = 0 {4} , -1 2 {2} , 1 2 , -1 2 u 7 = 0 {5} , -1, 1 2 , -1 2 Ẽ8 , given in R 8 u 0 = 0 {8} u 1 = 0 {7} , 1 u 2 = 1 6 {7} , 5 6 u 3 = -1 8 , 1 8
{6} , 7 8 u 4 = 0 {2} , 1 6
{5} , 5 6 u 5 = 0 {3} , 1 5
{4} , 4 5 u 6 = 0 {4} , 1 4
{3} , 3 4 u 7 = 0 {5} , 1 3
{2} , 2 3 u 8 = 0 {6} , 1 2 {2} F4 , given in R 4 u 0 = (0, 0, 0, 0) u 1 = 1 2 , 1 2 , 0, 0 u 2 = 2 3 , 1 3 , 1 3 , 0 u 3 = 3 4 , 1 4 , 1 4 , 1 4 u 4 = (1, 0, 0, 0) G2 , given in R 2 u 0 = (0, 0) u 1 = (1, 0) u 2 = 1, √ 3
Table 1: Vertices of a simplex per Coxeter diagram type. Although a partial list has been provided by Conway and Sloane [START_REF] Conway | Sphere-packings, Lattices, and Groups[END_REF] we are not aware of any complete explicit overview. We believe that such a list will be of essential for many practitioners. The powers in point coordinates correspond to duplications of the same coordinate, for example ( • The radius ratio of σ is the ratio of its inradius to its circumradius:

1 2 {3} , -1 2 ) is the same as ( 1 2 , 1 2 , 1 2 , - 1 2 ).
ρ(σ) = r(σ) R(σ) .
To be able to compare the presented quality measures between themselves, we will normalize them by their respective maximum value. As we show in Appendix C, all of these quality measures are maximized by regular simplices.

Theorem 3.2. Out of all d-dimensional simplices, the regular d-simplex has the highest aspect ratio, fatness, thickness and radius ratio.

For a quality measure κ we will define the normalized quality measure κ, such that for each d-simplex σ, κ(σ) = κ(σ) κ(∆) , where ∆ is the regular d-simplex. Theorem 3.2 ensure that the quality measures ρ, α, θ and Θ take their values in [0, 1] surjectively.

Delaunay criterion for Coxeter triangulations

Many of the provably good mesh generation algorithms are based on Delaunay triangulations [START_REF] Cheng | Delaunay mesh generation[END_REF]. This motivated us to investigate if Coxeter triangulations have the Delaunay property. In order to establish that, we need several criteria for triangulations to be (or not to be) Delaunay.

Definition 4.1. A simplex is called self-centred if it contains its circumcentre inside or on the boundary.

We have that: By definition, all Coxeter triangulations are monohedral. This means that it is sufficient to check if one simplex in the triangulation is self-centred to conclude that the triangulation is Delaunay. The proof of Lemma 4.4 can be found in Appendix D. All Coxeter triangulations are monohedral, therefore all simplices have the same circumradius. So trivially all the simplices have the maximum circumradius in the triangulation. This observation along with Lemma 4.4 leads us to conclude that if a simplex in a Coxeter triangulation is not self-centred, then the triangulation is not Delaunay. By combining this with Corollary 4.3 yields: Theorem 4.5. A Coxeter triangulation is Delaunay if and only if its simplices are self-centred.

Because some of the triangulations that interest us here are Delaunay, we will also look at their protection value. The protection δ of a Delaunay triangulation T is the infimum over the d-simplices of the triangulation: δ = inf σ∈T δ(σ).

We define the relative protection δ(σ) of a given d-simplex σ to be the ratio of the protection to its circumscribed radius: δ(σ) = δ(σ) R(σ) . The relative protection δ of a Delaunay triangulation T is the infimum over the d-simplices of the triangulation: δ = inf σ∈T δ(σ).

In the spirit of Theorem 4.5, we can easily spot if a Coxeter triangulation is not protected with the help of the following lemma: Lemma 4.7. A Delaunay triangulation where the simplex with maximal circumradius contains the circumcentre on its boundary is not protected.

We prove this lemma in Appendix D. Again, by using the fact that Coxeter triangulations are monohedral, we derive from the previous lemma the following theorem: Theorem 4.8. If a simplex of a Coxeter triangulation contains the circumcentre on its boundary, then the triangulation is non-protected Delaunay.

Finally, one can slightly modify Lemma 8 and Theorem 5 in [START_REF] Vt Rajan | Optimality of the Delaunay triangulation in R d[END_REF] by replacing all non-strict inequalities to strict inequalities to get a criterion for a non-zero protection: Theorem 4.9. If a simplex of a Coxeter triangulation contains the circumcentre strictly inside, then the triangulation is Delaunay with a non-zero protection.

Main result

In this section we present a summarized table with explicit expressions of quality measures of Coxeter triangulations. In addition to that we also identify which Coxeter triangulations are Delaunay and give their protection values. Finally, we identify which Coxeter triangulations have vertex sets with lattice structure.

Theorem 5.1. The normalized fatness, aspect ratio, thickness and radius ratio of simplices in Coxeter triangulations, as well as Delaunay property are:

Fatness Θ1/d Aspect Ratio α Thickness θ Radius Ratio ρ Delaunay? Ãd , d odd 2 3/2 ( √ d+1) 1+2/d 6d (d+1)(d+2) 2 √ d d+1 6d (d+1)(d+2) Ãd , d even 2 3/2 ( √ d+1) 1-2/d √ d(d+2) 2 √ d+2
Bd

2 1/2+1/d √ d( √ d+1) 1/d d √ 2 (d+1) √ d+2 1 √ d+1 2d √ d+2(1+(d-1) √ 2) Cd √ 2 √ d( √ d+1) 1/d √ 2d d+1 1 √ d+1 2 √ d 2+(d-1) √ 2
Dd

2 1/2+2/d √ d( √ d+1) 1/d d √ 2 (d+1) √ d+4 1 √ d+1 d √ 2 (d-
4 √ 2 3(2+ √ 2) G2 √ 2 2 1 √ 3 1 2 2 1+ √ 3
Out of them, only à family triangulations have a non-zero relative protection value equal to:

δ = √ d 2 + 2d + 24 - √ d 2 + 2d √ d 2 + 2d ∼ 12 d 2
Only à family, C family and D4 triangulations have vertex sets with lattice structure.

The proof of this theorem and the table without normalization can be found in Appendix B. The corresponding quality measures for the regular d-simplex ∆ (which does not correspond to a triangulation in general) are:

Fatness Θ Aspect Ratio α Thickness θ Radius Ratio ρ

∆ 1 d! d+1 2 d d+1 2d d+1 2d 1 d
All simplex quality measures in the table above are normalized with respect to the regular simplex. Note that the fatness values in the table are given powered 1/d. It is due to the fact that fatness is a volume-based simplex quality. Also note that all normalized simplex qualities for the families Ãd , Bd , Cd and Dd behave as

O 1 √ d .
The numerical values of these quality measures are given in Tables 3,4, 5 and 6 in Appendix E, and plotted in Figure 4 below. A quick glance suffices to see that Ãd achieves the greatest aspect ratio, fatness, thickness and radius ratio among the Coxeter triangulations in each dimension d.

Protection value of an Ãd triangulation

In this section we will prove the bound on protection stated in Theorem 5.1. Lemma 6.1. Ãd Coxeter triangulation has a relative protection equal to

δ = √ d 2 + 2d + 24 - √ d 2 + 2d √ d 2 + 2d ∼ 12 d 2 .
Proof. Let V be the vertex set of the triangulation containing the simplex in the Ãd row of Table 1. By Proposition B.2 in Appendix B, V coincides with the coweight lattice, which corresponds to an A d root system R.

Take the following basis vectors of the coweight lattice V :

u k = 1 d + 1 (k -(d + 1)) {k} , k {d+1-k} , for 0 ≤ k ≤ d.
This means that any point of V can be expressed as

d k=1 α k u k , with α k ∈ Z for all k ∈ {1, .
. . , d}. Each coordinate of (d + 1) u k is an integer congruent to k modulo (d + 1). Following the definition of [START_REF] Adams | Fast High-Dimensional Filtering Using the Permutohedral Lattice[END_REF], we call a point a remainder-k point if its coordinates are congruent to k modulo (d + 1). Since any lattice point z in V can be written as z = α k u k , it follows that z is a k-remainder point, where k is congruent to ( α k • k) modulo (d + 1).

We will now look at the circumcentre c

= 1 d+1 -d 2 , -d-2 2 , -d-4 2 , . . . , d 2
of σ and find its nearest neighbours in the lattice. Take z

= 1 d+1 n 1 (d + 1) + k, • • • , n d+1 (d + 1
) + k a remainder-k lattice point, for some k ∈ {0, . . . , d}. Note that because the lattice V resides in the hyperplane d+1 i=1 x i = 0, we have z, (1 {d+1} ) = 0, and therefore n i = -k. We now need to find the value of n

= (n 1 , • • • , n d+1 ) ∈ N = x ∈ Z d+1 x i = -k which minimizes d(z, c
) for a given k. We now state the following claim, which will be proved below.

Claim. For each k ∈ Z/(d + 1)Z, the closest remainder-k point in V to c is u k . A remainder-k point that is the second closest corresponds to the vector n equal to

(-1 {k-1} , 0, -1, 0 {d-k} ), for k ∈ {1, ..., d} (-1, 0 {d-1} , 1), if k = 0
and has the coordinates

((k -(d + 1)) {k-1} , k, k -(d + 1), k {d-k} ), for k ∈ {1, ..., d} (-(d + 1), 0 {d-1} , d + 1), if k = 0 .
Each of these points are at a distance

R = d(d + 2) 12(d + 1) + 2 d + 1 from c.
This claim implies that the protection radius of σ is

R -R = d(d + 2) 12(d + 1) + 2 d + 1 - d(d + 2) 12(d + 1
) .

Thus, the relative protection is

δ = √ d 2 + 2d + 24 - √ d 2 + 2d √ d 2 + 2d = 1 + 24 d 2 + 2d -1 ∼ 1 + 12 d 2 + 2d -1 ∼ 12 d 2 .
This completes the proof of Lemma 6.1 apart from the claim, which we will focus on now.

The main ingredient for the proof of the Claim is the following lemma.

Lemma 6.2. The difference between the two squared distances d(z, c) 2 and d(z , c) 2 for two points z and z of the lattice V is of the form 2q d+1 where q is an integer. Proof. It is enough to compare the distances for z and z of the same congruence class. Indeed, each congruence class k already contains the point u k , which is of squared distance R 2 from c. The difference between any two squared distances d(z, c) 2 and d(z , c) 2 , for z and z a remainder-k and a remainder-k point respectively, can be expressed as

d(z, c) 2 -d(z , c) 2 = (d(z, c) 2 -d(z, u k ) 2 ) -(d(z , c) 2 -d(z , u k ) 2 ).
If both differences are in 2 d+1 Z, the overall difference is as well. So let

z = 1 d + 1 n 0 (d + 1) + k, • • • , n d (d + 1) + k and z = 1 d + 1 n 0 (d + 1) + k, • • • , n d (d + 1) + k
be two remainder-k points of V , with n i and n i integers for all i ∈ {1, . . . , d + 1}. The difference between d(z, c) 2 and d(z , c) 2 can be expressed as:

d(z, c) 2 -d(z , c) 2 = ( z 2 -2 z, c + c 2 ) -( z 2 -2 z , c + c 2 ) = z 2 -z 2 -2 z -z , c = d i=0 n i + k d + 1 2 - d i=0 n i + k d + 1 2 -2 d i=0 n i + k d + 1 -n i - k d + 1 - d 2(d + 1) + i d + 1 = d i=0 (n i -n i ) n i + n i + 2k d + 1 + 2 d i=0 (n i -n i ) d/2 -i d + 1 = d i=0 (n i -n i ) n i + n i + 2k + d -2i d + 1 Because d i=0 n i = -k, we can express n 0 = -k - d i=1 n i . Therefore d(z, c) 2 -d(z , c) 2 = d i=1 (n i -n i ) n i + n i + 2k + d -2i d + 1 +(n 0 -n 0 ) n 0 + n 0 + 2k + d d + 1 = d i=1 (n i -n i ) n i + n i + 2k + d -2i d + 1 - d i=1 (n i -n i ) -2k - d i=1 (n i + n i ) + 2k + d d + 1
The last expression is further simplified to

d i=1 (n i -n i )   n i + n i + 2k + d j=1 (n j + n j ) - 2i d + 1   .
We will split this expression in two parts:

d i=1 (n i -n i )   n i + n i + d j=1 (n j + n j )   + 2 d + 1 d i=1 (n i -n i )((d + 1)k -i). (1)
The second part of the expression ( 1) is already of the form 2q d+1 with q an integer, so we will be interested in the first part.

Let a i ∈ Z/2Z be the congruence class of (n i -n i ) modulo 2. At the same time, a i is the congruence class of (n i + n i ) modulo 2. So the first part of the expression has the congruence class modulo 2 as follows:

d i=1 a i   a i + d j=1 a j   = d i=1 a 2 i + d i=1 a i 2 = 2 d i=1 d j=0 j =i a i a j = 0.
It implies that the first part of ( 1) is an even integer and it can be represented as 2q d+1 for some integer q . Thus, the difference d(z, c) 2 -d(z , c) 2 can be expressed as 2q d+1 for some integer q. Proof (of Claim). A consequence of Lemma 6.2 is that the minimal positive difference between two squared distances is 2 d+1 . By Theorem 4.9 we know that the triangulation has a non-zero protection, so out of all points in V only the vertices of σ are distant from c by the circumradius R, and they are unique to be so in their respective congruence class. The squared distance R 2 between the points in the statement of the Claim and the circumcenter c is exactly different from R 2 by 2 d+1 , so these points are indeed second closest points to c after the vertices of σ, which concludes the proofs of the Claim and Lemma 6.1. Remark 6.3. One can verify that the points in the statement of the Claim are the only second closest points to c in V , but it goes beyond the scope of this paper.

A Roots, Groups and lattices: general background

The Coxeter triangulations we use originate in group theoretical studies of symmetries. This section provides a group-theoretical background for and gives a brief introduction of Coxeter triangulations. The first four subsections of the background form a summary of the lecture notes by Jaap Top [START_REF] Top | Dynkin diagrammen en Wortelsystemen[END_REF], while the latter subsections give some essential results from Humphreys [START_REF] Humphreys | Reflection groups and Coxeter groups[END_REF].

A.1 Graphs and Cartan matrices

We consider undirected connected graphs without loops with d vertices {v 1 , . . . , v d }. One can associate an incidence matrix to any such graph, A = (a ij ). This is the symmetric d × d-matrix with a ij = 1 if there is an edge between v i and v j and a ij = 0 otherwise. Definition A.1. The Cartan matrix of a graph Σ with incidence matrix A is defined by C = 2I -A, where I is the identity matrix.

To each d×d Cartan matrix we can associate a symmetric bi-linear form •, • C on R d defined by u, v C = u t Cv, with u, v ∈ R d and where u t denotes the transposition of u.

We are now interested in identifying the graphs for which the symmetric bi-linear form is positive definite and therefore defines an inner product. Each such d × d Cartan matrix gives us d linear maps σ i , one for each vector e i of the canonical basis, defined by

σ i : R d → R d x → x -x, e i C e i = x -(x t Ce i )e i .
If the bi-linear form •, • C is positive definite, the linear map σ i is the orthogonal reflection through the hyperplane, which is orthogonal to e i with respect to the inner product determined by C.

Definition A.2. The Weyl group W Σ of a graph Σ is the subgroup of GL(d, R) generated by all σ i . The roots of Σ are the vectors in the set

R Σ = {σ(e i ) | 1 ≤ i ≤ d, σ ∈ W Σ }.
We now have the following (cf. Section 2.2 of [START_REF] Humphreys | Reflection groups and Coxeter groups[END_REF]):

Lemma A.3. Let Σ be a connected graph with Cartan matrix C and Weyl group W Σ .

• If •, • C is positive definite, that is it defines an inner product, then the action of W Σ on R d is irreducible, which means that there is no non-trivial subspace of R d (a subspace that is not equal to R d or {0}) that is mapped to itself under the action of W Σ .

• If W Σ is finite, then the action of W Σ on R d is irreducible.

Theorem A.4 ([18, Section 1.3]). For a graph Σ with Cartan matrix C, Weyl group W Σ and root set R Σ , the following three statements are equivalent:

• •, • C is positive definite, that is it defines an inner product.

• The root set R Σ is finite.

• The Weyl group W Σ is finite.

The Section 1.8 of [START_REF] Humphreys | Reflection groups and Coxeter groups[END_REF] also gives us the following proposition:

Proposition A.5. For any graph Σ with a positive definite inner product, the action of elements of Weyl group W Σ is simply transitive on the root set R Σ .

The connected graphs Σ that give a positive definite form •, • C have been classified to be the following (see Section 2.4 of [START_REF] Humphreys | Reflection groups and Coxeter groups[END_REF]): A.2 Construction of root systems for positive definite graphs

A d D d ... ...
in (R 2 , •, • C ) ( √ DO) • R = r 1 r 1 + r 2 r 2 -r 2 -r 1 -r 2 -r 1 in (R 2 , •, • )
We now want to make the Weyl groups as concrete as possible. To do this we need to find vectors r 1 , . . . r d ∈ R m , for m ≥ d, and R m endowed with the standard inner product •, • , such that r i , r j = c ij . These vectors are linearly independent because the Cartan matrix C is invertible. In general such a matrix of inner products in called a Gram matrix. The span of the vectors r i will be denoted by V . Note that it is always possible to find such vectors r i , even in R d . The reason for this is that C can be diagonalized by an orthogonal matrix

O, O t DO = C. Let us write D = (d ij ), with d ij = 0, if i = j. If √ D denotes the matrix with √ d
ii on the diagonal, r i can be found as the ith column of the matrix √ DO (see Figure 5). Note that this choice is not unique. However in the context of root systems, nicer roots can be chosen, if we allow the roots to lie in R m for m > d. According to Humphreys[18, Section 2.10], the nice choices are not so obvious, and historically arose from close scrutiny of simple Lie algebras.

The linear maps ϕ i given by ϕ i (v) = v -v, r i C r i , are automorphisms of V and their matrices with respect to the basis {r 1 , . . . , r d } coincide with the matrices of the generators σ i of the Weyl group. This means we can identify all roots with images of r i under products of ϕ j s, and the Weyl group may be identified with the group generated by the ϕ j s.

The vectors for graphs Σ that give a positive definite form •, • C are listed in Theorem A.12.

A.3 Root systems

As we have seen in the previous section, a root set R of each of the diagrams A d , D d , E 6 , E 7 and E 8 is stable under the reflections of its roots. These reflections therefore generate a finite group. We will now construct more of such groups based on finite sets of R d and properties that are similar to the properties of the roots we discussed.

A.3.1 Definition and properties

We work in R d endowed with the standard inner product •, • . For r ∈ R d , with r = 0, the reflection σ r in the hyperplane {v ∈ R d | v, r = 0} is given by σ r (x) = x -2 x, r r, r r.

Definition A.6. A reduced (red) and irreducible (irr

) root system in R d is a finite set R ⊂ R d that satisfies: (R1) 0 / ∈ R and R contains a basis of R d (R2) For all r ∈ R, σ r (R) ⊂ R (R3) For all r, s ∈ R, σ r (s) -s is an integer multiple of r. (red) If r ∈ R and λr ∈ R, then λ = ±1 (irr) There is no decomposition R = R 1 ∪ R 2 with R 1 = ∅ = R 2 and r 1 , r 2 = 0 for all r 1 ∈ R 1 and r 2 ∈ R 2 .
The Weyl groups of the root system R is the (finite) group W generated by the reflections σ r .

From this point onward we shall assume that every root system is reduced and irreducible.

Remark A.7. The angle ϕ, with 0 ≤ ϕ ≤ π, between the two roots r, s is given by cos ϕ = r,s |r||s| . Note that, due to (R3),

σ r (s) -s = 2 r, s r, r r ∈ Z • r,
and thus n(s, r) := 2 r, s r, r ∈ Z.

It follows that 4 cos 2 ϕ = n(s, r) • n(r, s) ∈ Z. In the case r, s = 0, observe that the ratio of the squared norms of these two roots is given by s,s r,r = 2 r,s r,r s,s 2 r,s = n(s,r) n(r,s) . This gives us, up to symmetry, the following table:

4 cos 2 ϕ n(s, r) n(r, s) ϕ length relation order(σ r σ s ) 4 2 2 0 r = s 1 4 -2 -2 π r = -s 1 3 3 1 π/6 |s| = √ 3|r| 6 3 -3 -1 5π/6 |s| = √ 3|r| 6 2 2 1 π/4 |s| = √ 2|r| 4 2 -2 -1 3π/4 |s| = √ 2|r| 4 1 1 1 π/3 |s| = |r| 3 1 -1 -1 2π/3 |s| = |r| 3 0 0 0 π/2 (undetermined) 2
By inspection of the table we observe that the length ratio of any two roots can only be 1, √ 2 or √ 3. It implies that there are at most two different norms of roots, and in this case we speak about short and long roots.

Definition A.8. Assume that for a root system R we are given an arbitrary t ∈ R d such that t, r = 0 for all r ∈ R. The root system now decomposes as

R = R + t ∪ R - t into positive roots R + t = {r ∈ R | r, t > 0} and negative roots R - t = {r ∈ R | r, t < 0}. A root r ∈ R + t is called decomposable if r = r 1 + r 2 , with r 1 , r 2 ∈ R + t
, and a root r ∈ R + t is called simple if it is not decomposable. The set of simple roots is denoted by S t . Lemma A.9. For any two simple roots r = s we have:

• r, s ≤ 0.

• The simple roots form a basis of R d .

• The Weyl group is generated by the reflections associated to the simple roots.

We refer to Sections 1.3 and 1.5 of Humphreys [START_REF] Humphreys | Reflection groups and Coxeter groups[END_REF] for the proof of the lemma. Because n(r, s) ∈ {-3, -2, -1, 0} and n(s, r) • n(r, s) = 4 cos 2 ϕ, the angle ϕ between r and s equals π 2 , 2π 3 , 3π 4 or 5π 6 . This information can be represented in a graph. Definition A.10. Given a root system R and a set of simple roots S t . We can assume without loss of generality that the short roots in S t have length 1, because we can always rescale all roots. The Coxeter diagram of R consists of a graph with the following data: For each r ∈ S t we insert one vertex. For every pair r = s in S t with r, s = 0 we define a number m(r, s) ∈ {2, 3, 4, 6}, such that π m(r,s) = arccos | cos ϕ|, where ϕ is an angle between r and s. We then insert an edge between r and s and write the number m(r, s) next to it. We further follow the convention not to draw an edge labelled 2 and not denote the label 3 next to an edge. Lemma A.9 states that the simple roots S t form a basis of R d . So the standard inner product can be expressed in terms of the basis S t . If we write

v = r∈St v r r w = r∈St w r r we see that v, w = r∈St v r w r r, r + r =s∈St v r w s r, s .
Because the Euclidean inner product is a positive definite form it is positive definite with respect to any basis.

To put it differently the right hand side must be positive definite too. The classification of all Coxeter diagrams can now be performed based on the determination which bilinear forms

r∈St v r w r r, r + r =s∈St v r w s r, s = r∈St v r w r r, r + 1 2
r =s∈St v r w s r, r s, s m(r, s) are positive definite. After rescaling this reduces to determining for which diagrams the quadratic form

r, s C = r∈St v r v r + 1 2 r =s∈St v r v s m(r, s)
is positive definite. Such a determination yields:

Theorem A.11. The complete list of Coxeter diagrams of reduced and irreducible root systems consists of A d , D d , E 6 , E 7 and E 8 and the following diagrams:

B d (= C d ) 4 ... F 4 4 G 2 6
In this list the root system C d is defined as dual to B d (see Definition A.15). As a root and a dual root systems they share the same Coxeter diagram and Weyl group (see Section A.4).

See for example Sections 2.4 and 2.7 of Humphreys [START_REF] Humphreys | Reflection groups and Coxeter groups[END_REF] for a proof and more information on the classification of Coxeter diagrams.

Having the classification, we can give the roots explicitly as discussed in Section A.2:

Theorem A.12 ( [START_REF] Bourbaki | Lie groups and Lie algebras[END_REF]). Let {e 1 , . . . , e d } be the canonical basis in R d . The complete list of simple root sets (up to scale, rotation and permutation) is the following: In this list the root system C d is defined as dual to B d (see Definition A.15).

• A d (in R d+1 ): s 1 = e 1 -e 2 ,
Remark A.13. The list of positive definite graphs also includes the following graphs:

H 3 5 H 4 5
I n n
The corresponding reflection groups are the isometry groups of the icosahedron (H 3 ), the isometry group of a regular 120-sided solid with dodecahedral faces in R 4 (H 4 ) and the dihedral group D n (I 2 (n)). These diagrams do not correspond to Weyl groups, with the following exceptions: I 2 (6), which is traditionally denoted as G 2 in the context of Weyl groups, I 2 (3) which corresponds to A 2 and I 2 (4), which corresponds to B 2 . Apart from these three exceptions these groups violate condition (R3) and are also called non-crystallographic (they do not correspond to locally finite lattices), hence are not considered in this paper. We refer to Humpreys [18, Sections 2.8 and 2.13] for further reading.

A.4 Root lattices

We can now define lattices based on the roots we discussed above. These lattices will be essential to the remainder of the text.

Definition A.14. The root lattice Λ R of a root system R is defined as

Λ R = r∈R n r r | n r ∈ Z .
It is indeed a lattice in the sense that it is a group under addition of vectors, contains a basis of a R d and any bounded region contains only a finite number of elements.

Definition A.15. For each root r ∈ R define its dual root (or coroot) to be r ∨ = 2r r,r . The set of dual roots forms a root system [18, Section 2.9] called dual root system and is denoted by R ∨ .

Observe that coroots share the same symmetries σ i as the roots. Therefore they generate the same Weyl group W . In most cases, the root system R ∨ is identical to R up to scale and rotation; however, the root systems B d and C d are dual to each other [18, Section 2.9]. Short roots in a system R of type B d give rise to long roots in a system R ∨ of type C d and vice versa.

Definition A. [START_REF] David P Dobkin | Contour tracing by piecewise linear approximations[END_REF]. Similarly to root lattices, we define a coroot lattice Λ R ∨ :

Λ R ∨ = r∈R n r r ∨ | n r ∈ Z .
Another important family of lattices is so-called weight lattices:

Definition A.17. The set of points which has an integer inner product with all coroots is called the weight lattice:

Λ w R = x ∈ R d | x, r ∨ ∈ Z, r ∈ R .
Similarly the coweight lattice is defined as:

Λ w R ∨ = x ∈ R d | x, r ∈ Z, r ∈ R .

A.5 Affine reflection groups

The goal for us now is to define a triangulation of the Euclidean space associated to every root system. First, we need the following definitions:

Definition A.18 (Affine Weyl group). Let R ⊂ R d be a finite root system. For every root r ∈ R and integer k ∈ Z we define an affine hyperplane:

H r,k := {x ∈ R d | x, r = k}.
The set of affine hyperplanes H r,k for all r ∈ R and k ∈ Z will be denoted as H. To each H r,k we can associate an affine reflection σ r,k : x → x -( x, r -k)r ∨ . These reflections generate a subgroup of the group of affine transformations of R d , which is called the affine Weyl group and is denoted by W a .

Roughly speaking, the affine Weyl group is a combination of the Weyl group and translations along a lattice. This can be made more precise using the dual lattice Λ R ∨ defined in Section A.4: Proposition A.19. Let R be a root system and W be a corresponding Weyl group. W a is a semidirect product of W and the translation group corresponding to the coroot lattice Λ R ∨ .

We refer to Section 4.2 of [START_REF] Humphreys | Reflection groups and Coxeter groups[END_REF] for more information. By Definition A.15, the dual roots are rescaled versions of roots such that the inner product of a root and its dual is 2 (see Figure 7). We can also define these dual roots as follows: one defines σ r,k as the affine reflection that leaves H r,k invariant. With this definition the dual root r ∨ is the image of 0 under the reflection σ r,1 . In general, the image of 0 by σ r,k is kr ∨ (see Figure 6).

The positions of hyperplanes H r,k with respect to primal and dual root systems in R 2 are illustrated in Figure 7. We notice that the open regions in between the hyperplanes H r,k are congruent triangles. These regions are called alcoves and are the subject of our study in the following. We now formalize: Definition A.20. Define A to be the set of connected components of R d \ H∈H H. Each element in A is called an alcove.

Let R + be a set of positive roots and S the corresponding simple system. In general, an alcove is characterized by a set of inequalities of the form: ∀r ∈ R + , k r < x, r < k r + 1, with k r integers. We will denote by A o the particular alcove for which all k r are equal to 0:

A o = {x ∈ R d | ∀r ∈ R + , 0 < x, r < 1}
If the root system R is irreducible, most of the inequalities that define A o are redundant. If we want to eliminate the redundant inequalities, we first need to define the so called highest root.

r = r ∨ H r,-5 H r,-4 H r,-3 H r,-2 H r,-1 H r,0 H r,1 H r,2 H r,3 H r,4 H r,5
Figure 6: Root system A 2 and the hyperplanes H r,k corresponding to the root r. Note that r 2 = 2, therefore the primal and the dual roots coincide and the hyperplane H r,1 goes halfway through r = r ∨ .

Because simple roots S form a basis of the irreducible root system R, any root can be decomposed as a sum of simple roots with integer coefficients. So for any two roots r and r we can write r = d i=1 c i s i and r = d i=1 c i s i , where S = {s 1 , . . . , s d } and the coefficients c i and c i are integers. This gives a partial order on the set of roots R, which compares the coefficients of two roots meaning that r r if and only if c i ≤ c i for all 1 ≤ i ≤ d. Using the decomposition, the positive roots R + can be characterized as the roots that have non-negative coefficients when expressed in terms of simple roots.

Proposition A.21 (Existence and uniqueness of the highest root). For an irreducible root system R and a simple root set S ⊂ R, there is a unique maximal element s ∈ R + for the partial order , which is called the highest root.

Remark A. [START_REF] Ms Klamkin | Inequality for a simplex[END_REF]. If R has multiple irreducible components there is a highest root for each of them.

For proofs and more details on the highest root we refer to Section 2.9 of Humphreys [START_REF] Humphreys | Reflection groups and Coxeter groups[END_REF]. The following proposition states that there are exactly d + 1 hyperplanes that delimit A o : d hyperplanes corresponding to simple roots and one corresponding to the highest root: Now, we are interested in the closure of the alcove A o . This simplex will be the starting point of the triangulations we will construct. Definition A.24. Let R be a root system and S ⊂ R a set of simple roots. Let A o be the alcove as above. The closure F of A o is called the fundamental domain (or fundamental simplex) of R with respect to S. Proposition A.25 ([18, Section 4.3]). Let R be a root system and S ⊂ R be a set of simple roots. Let A be the set of alcoves. The affine Weyl group W a acts simply transitively on A.

The reason behind the name fundamental domain is that the group W a acts simply transitively on A. In other words, any alcove A is an image of A o under a unique transformation w ∈ W a , as the following proposition states. We call such triangulations Coxeter triangulations. Another more geometric way to get the corollary above is linked with the Voronoi diagram of coroot lattice Λ R ∨ (see also Figure 7): Proposition A.27 [START_REF] Conway | Sphere-packings, Lattices, and Groups[END_REF]Chapter 21]). Let R be a root system and W the corresponding Weyl group. Let F be the fundamental domain of R with respect to a set of simple roots S ⊂ R. Then the Voronoi cell of 0 in the Voronoi diagram of the coroot lattice Λ R is:

A 2 B 2 G 2 A ∨ 2 = A 2 B ∨ 2 = C 2 G ∨ 2
Vor(0) = W F := w∈W wF
Simply put, simplices in W F triangulate the Voronoi cell of 0, even though the term "triangulate the Voronoi cell" although it is somewhat abusive: the vertices of the triangulation we build consists not only of the vertices of the Voronoi cell, but also of its centre.

The Coxeter diagrams for Affine Weyl groups are defined in the same way as in Definition A.10, except that we use not only the simple roots, but the highest root as well. This means that the vertices correspond to simple roots and the highest root, and the edges correspond to angles between them.

The classification of all affine Weyl groups is possible thanks to the notion of subgraph and the following lemma: Based on these results we can now derive: For a proof we refer to Sections 2.5 and 2.7 of [START_REF] Humphreys | Reflection groups and Coxeter groups[END_REF]. We now have a classification of the Coxeter triangulations, whose properties are the topic of this paper.

Definition A.

B Geometrical analysis of each family of Coxeter triangulations

For all families we will start with presenting two Coxeter diagrams, an augmented one on the left with coefficients on vertices, which are proportional to inverse heights of a simplex in the triangulation (taken from [START_REF] David P Dobkin | Contour tracing by piecewise linear approximations[END_REF]). The Coxeter diagram on the right indicates the notations of the corresponding facets in the following proofs.

In order to compute the quality measures we will apply the following schema:

1. We give the equations of the hyperplanes containing the facets ϕ i of a simplex σ that generates the root lattice in question.

2. We give the coordinates of the vertices u i of the simplex σ.

3. By using the augmented Coxeter diagram we find which height is the shortest (denoted by h(σ)). We then compute it as the distance from the corresponding vertex to the corresponding hyperplane.

4. We find the circumradius R(σ) and the inradius r(σ) of the simplex.

5. We find the length of the longest edge L(σ), using the coordinates of the vertices found previously.

6. We compute the thickness θ(σ) = h(σ) L(σ) , the aspect ratio α(σ) = h(σ) 2R(σ) and the radius ratio ρ(σ) = r(σ) R(σ) .

7. We compute the volume vol(σ) and the fatness Θ(σ) = vol(σ) L(σ) d .

8. We determine if the triangulation is Delaunay with the help of Theorem 4.5. If it is, we also compute its protection value. 9. We determine if the vertex set of the triangulation form a lattice.

The equations for the delimiting hyperplanes of fundamental simplices can be found in [START_REF] Bourbaki | Lie groups and Lie algebras[END_REF] or [START_REF] Conway | Sphere-packings, Lattices, and Groups[END_REF], or alternatively can be deduced from Theorem A.12.

We will adopt the following writing convention: the powers in point coordinates correspond to duplications of the same coordinate. For example: (0, 1 {3} , 0) is the same as (0, 1, 1, 1, 0). Ãd , d 2 ...

( √ d+1) d+1 d! 3(d+1) 2d(d+2) 2 d+1 6 d(d+1)(d+2) Ãd , d even 2 d ( √ d+1) d-1 √ d(d+2) d d! 2(d+1) d(d+2) Bd 2 d d/2 d! 1 √ 2(d+2) 1 √ 2d 2 √ d+2(1+(d-1) √ 2)
Cd

1 d d/2 d! 1 √ 2d 1 √ 2d 2 √ d(2+(d-1) √ 2) Dd 4 d d/2 d! 1 √ 2(d+4) 1 √ 2d √ 2 √ d+4(d-1) Ẽ6 √ 3 174960 1 6 1 2 √ 6 1 12 Ẽ7 √ 3 14696640 1 2 √ 13 1 4 √ 3 2 9 √ 13 Ẽ8 1 696729600 1 2 √ 19 1 6 √ 2 1 5 √ 19 F4 1 576 √ 2 6 √ 2 6 √ 2 3(2+ √ 2) G2 √ 3 8 √ 3 4 √ 3 4 1 1+ √ 3
Table 2: The non-normalized values for fatness, aspect ratio, thickness and radius ratio of Coxeter triangulations.

1. The delimiting (d -1)-planes of the fundamental simplex σ in R d+1 can be defined as the intersection of the hyperplane d i=0 x i = 0 and the following hyperplanes: for ϕ 0 :

-x 0 + x d = 1 for ϕ k : x k -x k-1 = 0 ∀k ∈ 1, d .
2. The vertices of σ are (in R d+1 ):

u 0 = 0 {d+1} u k = (-d+1-k d+1 ) {k} , ( k d+1 ) {d+1-k} , ∀k ∈ {1, . . . , d}.
3. All heights are equal to h(σ) = 1 √ 2 (see the augmented diagram in Figure 8). 12(d+1) , which is easily verifiable. The incentre coincides with the circumcentre and the inradius is r(σ) = 1 √ 2(d+1) , which is easily verifiable.

5. The edges of σ are described by differences u k -u j , for certain j, k ∈ {0, . . . , d} with j < k.

The squared norm of such a difference is equal to u k -u j 2 = (k-j)(d+1-k+j)

d+1

.

An easy analysis (substitute k -j as a new variable) yields that this function on k and j is maximal when k -j = (d + 1)/2.

So the maximal edge in σ has length

L(σ) = √ d+1 2 if d is odd 1 2 d(d+2) (d+1)
if d is even .

6. The aspect ratio, the thickness and the radius ratio are:

α(σ) = 3(d+1) 2d(d+2) θ(σ) =    2 d if d is odd 2(d+1) d(d+2) if d is even ρ(σ) = 6 d(d+1)(d+2) . 7.
Lemma B.1. Simplices in the Ãd triangulation have fatness:

Θ(σ) =      2 d ( √ d+1) d+1 d! if d is odd 2 d ( √ d+1) d-1 √ d(d+2) d d!
if d is even .

The lemma above comes mostly from the fact that the fundamental simplex σ has volume:

vol(σ) = 1 √ d + 1 d! .
Proof. Fix the dimension d ≥ 2. Let a k denote -d+1-k d+1 and b k denote k d+1 . Denote by σ the d-simplex of a Ãd triangulation described above. We build a (d + 1)-simplex σ , which consists of the d-face σ and a vertex u d+1 = (1 {d+1} ). Note that the edge u 0 u d+1 is orthogonal to the face σ.

The (d + 1)-dimensional volume of σ can be expressed as a determinant:

vol(σ ) = 1 (d + 1)! det        a 1 a 2 . . . a d 1 b 1 a 2 . . . a d 1 b 1 b 2 . . . a d 1 . . . . . . . . . . . . . . . b 1 b 2 . . . b d 1       
.

First, we subtract the last row from all the other rows. It gives us:

vol(σ ) = 1 (d + 1)! det        a 1 -b 1 a 2 -b 2 . . . a d -b d 0 0 a 2 -b 2 . . . a d -b d 0 0 0 . . . a d -b d 0 . . . . . . . . . . . . . . . b 1 b 2 . . . b d 1        = 1 (d + 1)! det      a 1 -b 1 a 2 -b 2 . . . a d -b d 0 a 2 -b 2 . . . a d -b d . . . . . . . . . . . . 0 0 . . . a d -b d      = 1 (d + 1)! d k=1 (a k -b k ) = 1 (d + 1)! d k=1 - d + 1 -k d + 1 - k d + 1 = 1 (d + 1)! .
The volume of σ can be found as:

vol(σ) = (d + 1)vol(σ ) (1 {d+1} ) = (d + 1) √ d + 1(d + 1)! = 1 √ d + 1 d! .
8. Because the circumcentre coincides with the incentre, it lies inside the simplex. So by Theorem 4.5 the triangulation is Delaunay. It also has a non-zero protection value by Theorem 4.9, the exact value of which is proven in Section 6.

9.

Proposition B.2. The vertex set of a Ãd triangulation is a lattice for all d ≥ 2.

As we will show, this lattice is in fact the coweight lattice introduced in Section A. [START_REF] Boissonnat | The stability of Delaunay Triangulations[END_REF]. The fact that the vertex set is a lattice is not entirely obvious. This lattice happens to be equal to the permutahedral lattice studied in for example [START_REF] Conway | Sphere-packings, Lattices, and Groups[END_REF].

Before proving the proposition, we will need the following lemma:

Lemma B.3.
Let R be a root system. Let V be the vertex set of the Coxeter triangulation corresponding to R. The coweight lattice Λ w R ∨ is a subset of V .

Proof. Let S = {s 1 , . . . , s d } be a set of simple roots. For any point p in Λ w R ∨ there exist integers n 1 , . . . , n d such that for every i, p, s i = n i . The point p lies in the intersection of the hyperplanes H si,ki . Therefore, being in the intersection of d hyperplanes in H, it is a vertex in the Coxeter triangulation. Now, we are ready to prove the proposition.

Proof. Take the triangulation generated by σ described in the beginning of the section. We will further prove that its vertex set V is the coweight lattice Λ w R ∨ of the root lattice R with the following highest root and simple roots: s = (-1, 0 {d-1} , 1) s k = (0 {k-1} , 1, -1, 0 {d-k} ), for all k ∈ {1, . . . , d}.

By Lemma B.3, the coweight lattice Λ w R ∨ is a subset of V . Now let us prove the other inclusion. The highest root can be expressed in terms of the simple roots as: s = -d i=1 s i . Because all the coefficients of this decomposition are of absolute value 1, any simple root s j can be expressed as a sum of the highest root and the rest of the simple roots with integer coefficients:

s j = s + 1≤i≤d i =j s j .
Let x be a vertex in V . The point x lies on d hyperplanes of the form H s,k with s ∈ S ∪ {s} and k ∈ Z. There are two cases to study:

(a) In the first case, all d hyperplanes correspond to simple roots. By the definition of the hyperplanes H s,k , this implies that all inner products with the simple roots are integers, which leads to the conclusion that x is in the coweight lattice Λ w R ∨ . (b) In the second case, d -1 hyperplanes correspond to simple roots and one hyperplane corresponds to the highest root s. Let s j be the root, whose hyperplane does not appear in the definition of x. By definition of x, all inner products x, s i with i = j as well as the inner product x, s are integers. But then:

x, s j = x, s +

1≤i≤d i =j
x, s j ∈ Z Therefore, all inner products of x with the simple roots are integers, which means that x lies in the coweight lattice Λ w R ∨ .

Bd , d 3

4 1 1 2 2 2 2 √ 2
... 1. The delimiting hyperplanes of the fundamental simplex σ can be defined as follows:

ϕ 0 : x 1 + x 2 = 1 ϕ k : x k -x k+1 = 0, ∀k ∈ {1, . . . , d -1} ϕ d : x d = 0.
2. The vertices of σ are:

u 0 = 0 {d} u 1 = 1, 0 {d-1} u k = 1 2
{k} , 0 {d-k} , ∀k ∈ {2, . . . , d}.

The minimal height falls on any of ϕ

k for k in {2, . . . , d -1} and is equal to h(σ) = 1 2 √
2 (see the augmented diagram in Figure 9).

The circumcentre of the simplex is (

1 2 , 0, 1 4 {d-2}
) and the circumradius is

R(σ) = √ d+2 4 , which is easily verifi- able. The incentre is 1+(d-1) √ 2 2(1+(d-1) √ 2) , 1+(d-2) √ 2 2(1+(d-1) √ 2) , . . . , 1 2(1+(d-1) √
2) and the inradius is

r(σ) = 1 2(1+(d-1) √
2) , which is easily verifiable.

The longest edge is given by u

d -u 0 and is equal to L(σ) = √ d
2 . 6. The aspect ratio, the thickness and the radius ratio are:

α(σ) = 1 2(d + 2) and θ(σ) = 1 √ 2d and ρ(σ) = 2 √ d + 2(1 + (d -1) √ 2)
7. The volume of the simplex is given by the formula:

vol(σ) = 1 d! det      1 1/2 . . . 1/2 0 1/2 1/2 . . . . . . . . . . . . 0 . . . 0 1/2      = 1 2 d-1 d! .
The fatness of the simplex is:

Θ(σ) = vol(σ) L(σ) d = 2 d d/2 d! .
8. Observe that the inner products of the normal vector s 2 to the hyperplane ϕ 2 with the circumcentre and u 2 have different signs:

s 2 , c = - 1 4 and s 2 , u 2 = 1 2 .
Therefore the hyperplane ϕ 2 separates the circumcentre c from u 2 , so by Theorem 4.5 the triangulation is not Delaunay. We will now prove that v = u d -u d-1 = 1 2 e d is not in the vertex set, which implies that V does not form a lattice.

The positive roots that have integer inner product with v are exactly:

{e i | i ∈ {1, . . . , d -1}} ∪ {e i -e j |
i, j ∈ {1, . . . , d -1} and i < j} ∪ {e i + e j | i, j ∈ {1, . . . , d -1} and i < j}, which is easily verifiable. These roots span the vector space Vect(E \ {e d }), which is (d -1)-dimensional. Thus, there do not exist (r 1 , ..., r d ) ⊆ R + that are linearly independent and have integer inner products with v. Therefore v does not belong to V .

Cd , d 2 4 4 1 √ 2 √ 2 √ 2 √ 2 1
... 1. The delimiting hyperplanes of the fundamental simplex σ can be defined as follows:

ϕ 0 : 2x 1 = 1 ϕ k : x k -x k+1 = 0, ∀k ∈ {1, . . . , d -1} ϕ d : x d = 0.
2. The vertices of σ are:

u k = 1 2
{k} , 0 {d-k} , ∀k ∈ {0, . . . , d}.

3. The minimal height falls on any of ϕ k for k in {1, . . . , d -1} and is equal to h(σ) = 1 2 √ 2 (see the augmented diagram in Figure 10).

1+(d-1) √ 2 2(2+(d-1) √ 2) , 1+(d-2) √ 2 2(2+(d-1) √
2) , . . . ,

1 2(2+(d-1) √ 2)
and the inradius is r(σ) = 2) , which is easily verifiable.

5. The longest edge is given by u d -u 0 and is equal to L(σ) = √ d 2 . 6. The aspect ratio, the thickness and the radius ratio are:

α(σ) = 1 √ 2d and θ(σ) = 1 √ 2d and ρ(σ) = 2 √ d(2 + (d -1) √ 2) .
7. The volume of the simplex is given by the formula:

vol(σ) = 1 d! det      1/2 1/2 . . . 1/2 0 1/2 1/2 . . . . . . . . . . . . 0 . . . 0 1/2      = 1 2 d d! .
The fatness of the simplex is:

Θ(σ) = vol(σ) L(σ) d = 1 d d/2 d! .
8. Observe that all inner products of the normals s i to hyperplanes ϕ i and the corresponding opposite vertices u i are positive. Observe as well that the inner products with the circumcentre s i , c are either positive or zero. It implies that the circumcentre lies on the boundary of the simplex, therefore by Theorem 4.8 the triangulation is non-protected Delaunay. 9.

Proposition B.5. The vertex set of a Cd triangulation is a lattice for d ≥ 2.

Proof. A point v ∈ R d is a vertex of the triangulation if and only if it lies in the intersection of at least d hyperplanes in H (as defined in Section A.5) that are linearly independent. Equivalently, the inner products of at least d linearly independent positive roots should be integers.

Let E = {e 1 , ..., e d } be the canonical base of R d . Bourbaki [START_REF] Bourbaki | Lie groups and Lie algebras[END_REF]Planche III] gives the explicit expressions of positive roots:

R + = {2e i | i ∈ {1, . . . , d}} ∪
{e i -e j | i, j ∈ {1, . . . , d} and i < j} ∪ {e i + e j | i, j ∈ {1, . . . , d} and i < j}.

We will denote by V the vertex set of the Cd triangulation that contains the simplex σ. The goal is to prove that V = ( 1 2 Z) d , which is a lattice. We will first prove that V ⊆ ( 1 2 Z) d . Indeed, for any x ∈ ( 1 2 Z) d , its image by an affine reflection σ r,k for r ∈ R and k ∈ Z, as defined in Section A.5, is σ r,k (x) = x -( x, r -k)r ∨ . For any r ∈ R and x ∈ ( 1 2 Z) d , the inner product x, r is in 1 2 Z, hence ( x, r -k) is in 1 2 Z as well. The dual root r ∨ has integer coefficients, so σ r,k (

x) = x -( x, r -k)r ∨ is in ( 1 2 Z) d
. Now recall that one can obtain any simplex from another one by a series of affine reflections. All vertices of σ are in ( 12 Z) d , so with the above observation we conclude that any vertex in V is in ( 12 Z) d as well. To prove the other direction, observe that {2e i | i ∈ {1, . . . , d}} is a set of d linearly independent positive roots that have integer inner products with any element in ( 12 Z) d . With both inclusions proven, we conclude that V = ( 1 2 Z) d , which is a lattice. 1. The delimiting hyperplanes of the fundamental simplex σ can be defined as follows:

ϕ 0 : x 1 + x 2 = 1 ϕ k : x k -x k+1 = 0, ∀k ∈ {1, . . . , d -1} ϕ d : x d-1 + x d = 0.
2. The vertices of σ are:

u 0 = 0 {d} u 1 = 1, 0 {d-1} u k = 1 2 {k} , 0 {d-k} , ∀k ∈ {2, . . . , d -2} u d-1 = 1 2 {d-1} , -1 2 u d = 1 2 {d} .
3. The minimal height falls on any of ϕ k for k in {2, . . . , d -2} and is equal to

h(σ) = 1 2 √
2 (see the augmented diagram in Figure 11).

4. The circumcentre of the simplex is 1 2 , 0, 1 4 {d-4} , 1 2 , 0 and the circumradius is

R(σ) = √ d+4 4 , which is easily verifiable. The incentre is 1 2 , d-2 2(d-1) , d-3 2(d-1) , . . . , 1 2(d
-1) , 0 and the inradius is r(σ) = 7. The volume of the simplex is:

vol(σ) = 1 d! det           1 1/2 . . . 1/2 1/2 1/2 0 1/2 1/2 1/2 1/2 0 0 . . . . . . . . . . . . . . . . . . . . . 1/2 1/2 1/2 0 0 . . . 0 1/2 1/2 0 0 . . . 0 -1/2 1/2           = 1 2d! det        1 1/2 . . . 1/2 1/2 0 1/2 . . . 1/2 1/2 . . . . . . . . . . . . . . . 0 . . . 0 1/2 1/2 0 . . . 0 0 1/2        + 1 2d! det        1 1/2 . . . 1/2 1/2 0 1/2 . . . 1/2 1/2 . . . . . . . . . . . . . . . 0 . . . 0 1/2 1/2 0 . . . 0 0 1/2        = 1 2 d-2 d! .
The fatness of the simplex is:

Θ(σ) = vol(σ) L(σ) d = 4 d d/2 d! .
8. Observe that the inner products of the normal vector s d-2 to the hyperplane ϕ d-2 with the circumcentre and u d-2 have different signs:

s d-2 , c = - 1 4 and s d-2 , u d-2 = 1 2 .
Therefore the hyperplane ϕ d-2 separates the circumcentre from u d-2 , so by Theorem 4.5 the triangulation is not Delaunay. Denote by V the vertex set of the triangulation.

Let Λ = {x ∈ ( 1 2 Z) 4 | x 1 + x 2 + x 3 + x 4 ∈ Z}.
We will now prove that V = Λ. For any x ∈ Λ, its image by an affine reflection σ r,k for r ∈ R and k ∈ Z, as defined in Section A.5, is σ r,k (x) = x -( x, r -k)r ∨ . For any r ∈ R and x ∈ ( 1 2 Z) 4 , the inner product x, r is in 1 2 Z, hence ( x, r -k) is in 1 2 Z as well. The coefficients of the dual root r ∨ are integers, so (

x, r -k)r ∨ ∈ ( 1 2 Z) 4 , hence σ r,k (x) ∈ ( 1 2 Z) 4 .
By assumption, the sum of coefficients of x is an integer. For any r ∈ R + defined above, the sum of coefficients of 1 2 r is an integer as well. Therefore σ r,k (x) ∈ Λ. Now recall that one can obtain any simplex from another one by a series of affine reflections. All vertices of σ are in Λ, so with the above observation we conclude that any vertex in V is in Λ as well. To prove the other direction, observe that {e 1 + e 2 , e 1 -e 2 , e 3 + e 4 , e 3 -e 4 } is a set of 4 linearly independent positive roots that have integer inner products with any element in Λ. With both inclusions proven, we conclude that V = Λ, which is a lattice.

(b) Let V be the the vertex set of the triangulation. We will now prove that v = u 3 -u 2 = 1 2 e 3 is not in the vertex set, which implies that V does not form a lattice. One can easily check that the positive roots that have integer inner product with v are exactly: {e i -e j | i, j ∈ {1, . . . , d} \ {3} and i < j} ∪ {e i + e j | i, j ∈ {1, . . . , d} \ {3} and i < j} and these roots span the vector space Vect(E \ {e 3 }), which is (d -1)-dimensional. Thus, there does not exist (r 1 , ..., r d ) ⊆ R + that are linearly independent and have integer inner products with v. We therefore conclude that v does not belong to V . 1. The delimiting hyperplanes of the fundamental simplex σ can be defined as follows:

ϕ 0 : 1 2 ((x 1 + x 2 + x 3 + x 4 + x 5 + x 8 ) -(x 6 + x 7 )) = 1 ϕ 1 : (x 1 + x 8 ) -(x 2 + x 3 + x 4 + x 5 + x 6 + x 7 ) = 0 ϕ 2 : x 1 + x 2 = 0 ϕ 3 : x 1 -x 2 = 0 ϕ 4 : x 2 -x 3 = 0 ϕ 5 : x 3 -x 4 = 0 ϕ 6 : x 4 -x 5 = 0

Ẽ7

1. The delimiting hyperplanes of the fundamental simplex σ can be defined as follows:

ϕ 0 : x 7 -x 8 = 1 ϕ 1 : (x 1 + x 8 ) -(x 2 + x 3 + x 4 + x 5 + x 6 + x 7 ) = 0 ϕ 2 : x 1 + x 2 = 0 ϕ 3 : x 1 -x 2 = 0 ϕ 4 : x 2 -x 3 = 0 ϕ 5 : x 3 -x 4 = 0 ϕ 6 : x 4 -x 5 = 0 ϕ 7 : x 5 -x 6 = 0
2. The vertices of σ are (in R 8 ) [12, Chapter 21]:

u 0 = 0 {8} u 1 = 0 {6} , 1 2 , -1 2 u 2 = -1 4 {6} , 1 2 , -1 2 u 3 = 1 6 , -1 6 {5} , 1 2 , -1 2 u 4 = 0 {2} , -1 4 {4} , 1 2 , -1 2 u 5 = 0 {3} , -1 3 {3} , 1 2 , -1 2 u 6 = 0 {4} , -1 2 {2} , 1 2 , -1 2 u 7 = 0 {5} , -1, 1 2 , -1 2
3. The smallest height falls on ϕ 4 and is equal to h(σ) = √ 2 8 (see the augmented diagram in Figure 13).

4. The circumcentre is (-

1 8 {2} , 0 {3} , -1 2 , 1 4 , - 1 4
) and the circumradius is R(σ) = 1 4 13 2 , which is easily verifiable. The incentre is (0, -

(σ) = 3 2 .
6. The aspect ratio, the thickness and the radius ratio are:

α(σ) = 1 2 √ 13 and θ(σ) = 1 4 √ 3 and ρ(σ) = 2 9 √ 13
7. The volume of σ is:

vol(σ) = √ 2
2903040 . Therefore, the fatness is:

Θ(σ) = vol(σ) L(σ) 7 = √ 3 14696640 ∼ 1.179 • 10 -7
8. Observe that the inner products of the normal vector s 4 to the hyperplane ϕ 4 with the circumcentre and the vertices have different signs: the inner product s 4 , c = -1 8 is strictly negative, whereas the inner products n, u i are all non-negative. Therefore the hyperplane ϕ 4 separates the circumcentre from the rest of the simplex, so by Theorem 4.5 the triangulation is not Delaunay.

9.

Proposition B.8. The vertex set of a Ẽ7 triangulation does not form a lattice.

Proof. A point v ∈ R 8 is a vertex of the triangulation if and only if it lies in the intersection of at least 7 hyperplanes in H (as defined in Section A.5) that are linearly independent. Equivalently, the inner products of at least 7 linearly independent positive roots should be integers.

Let E = {e 1 , ..., e 8 } be the canonical base of R 8 . Bourbaki [START_REF] Bourbaki | Lie groups and Lie algebras[END_REF]Planche VI] gives the explicit expressions of positive roots: R + = {e j -e i | i, j ∈ {1, . . . , 6} and i < j} ∪ {e i + e j | i, j ∈ {1, . . . , 6} and i < j} ∪ Let V be the vertex set of the corresponding triangulation. We will now prove that v = -6u 1 + 2u 2 + 3u 3 -4u 4 = e 2 is not in the vertex set, which implies that V does not form a lattice.

One can easily check that the positive roots that have integer inner product with v are exactly:

{e j -e i | i, j ∈ {1, . . . , 6} and i < j} ∪ {e i + e j | i, j ∈ {1, . . . , 6} and i < j} and these roots span the vector space Vect({e 1 , ..., e 6 }), which is 6-dimensional. Thus, there does not exist (r 1 , ..., r 7 ) ⊆ R + that are linearly independent and have integer inner products with v. We therefore conclude that v does not belong to V .

G2

Simplex of G2 triangulation (also called Kisrhombille tiling) is the right triangle with π/6 angle. By an easy computation, the aspect ratio, thickness and radius ratio are as follows:

α(σ) = θ(σ) = √ 3 4 and ρ(σ) = 1 1 + √ 3
The fatness is Θ(σ) = √ 3

8 . The circumcentre of any triangle lies on its hypotenuse, therefore by Theorem 4.8 the triangulation is non-protected Delaunay.

It is obvious from Figure 7 that the vertex set of the triangulation does not form a lattice.

C Proofs of the optimal quality of regular simplices in each dimension

In this section we will prove Theorem 3.2. The proof will be subdivided into lemmas that prove that each individual quality measure we consider is maximized by the regular simplex.

Radius ratio

The first result is by Klamkin for radius ratio [START_REF] Ms Klamkin | Inequality for a simplex[END_REF]: [START_REF] Ms Klamkin | Inequality for a simplex[END_REF]). Out of all d-simplices, the regular d-simplex ∆ has the maximum radius ratio equal to ρ(∆) = 1 d .

Lemma C.1 ([
Aspect ratio We can adapt the proof by Klamkin to prove the result for aspect ratio:

Lemma C.2. Out of all d-simplices, the regular d-simplex ∆ has the maximum aspect ratio equal to α(∆) = d+1 2d .

Proof. Let σ be a d-simplex. We will now prove that α(σ) = h(σ) 2R(σ) ≤ d+1 2d (see the augmented diagram). Let F i be the (d -1)-dimensional volume of the ith facet (see Figure 16). Denote v i the opposite vertex. If p is an arbitrary point, we have by Cauchy-Schwarz inequality:

d i=0 F i • d i=0 F i -→ pv i 2 ≥ d i=0 F i -→ pv i 2 . ( 2
)
Note that the equality takes place if and only if p is the circumcentre (making -→ pv i 2 all equal). Let F =

d i=0 F i -→ pv i 2 = d i=0 F i ( - → op --→ ov i ) ( - → op --→ ov i ) = F R(σ) 2 + - → op 2 -2 - → op • - → oq . Since 2 - → op • - → oq = - → op 2 + - → oq 2 -( - → oq -- → op) 2 = - → op 2 + - → oq 2 -- → pq 2 , d i=0 F i • d i=0 F i -→ pv i = F 2 R(σ) 2 + - → pq 2 -- → oq 2 . (3)
Denote by h i and r i the distances from v i and p respectively to the facet F i . Then d(p, v i ) is greater than h i -r i as the hypotenuse is greater than a leg in a right triangle (see Figure 16). So

d i=0 F i d(p, v i ) ≥ d i=0 F i h i - d i=0 F i r i .
Note that if V denotes the volume of the simplex, then for a fixed i we have F i h i = dV . On the other hand, for all i, the d-simplex formed by p and F i has a height r i with respect to F i (see Figure 16). It yields that

Thus combining (2), ( 3) and ( 4), we get:

F 2 R(σ) 2 + - → pq 2 -- → oq 2 = d i=0 F i d i=0 F i -→ pv i ≥ d i=0 F i -→ pv i 2 ≥ dF h(σ) d + 1 2 .
Setting p equal to q removes the -→ pq term:

R(σ) 2 ≥ d d + 1 h(σ) 2 + - → oq 2 ≥ d d + 1 h(σ) 2 ,
which gives the inequality that we sought to prove.

Thickness We can combine Lemma C.2 with Jung's theorem [START_REF] Jung | Über die kleinste Kugel, die eine räumliche Figur einschliesst[END_REF] to prove the result for thickness: Proof. Assume that σ be a d-simplex. We will distinguish two cases: namely σ is self-centred or not (as in Definition 4.1). Let σ be not self-centred. Let τ be a facet of σ that separates σ from its circumcentre c. Let p be the vertex of σ opposite to τ . Denote by h the height from p to τ and L be the length of the longest edge e adjacent to p (see Figure 17). By construction, h ≤ L/ √ 2, because the angle of the edge e with τ is less or equal to π/4. Therefore:

θ(σ) = h(σ) L(σ) ≤ h L ≤ 1 √ 2 ≤ d + 1 2d .
From now on we assume that σ is self-centred. This implies in particular that the circumradius of σ is equal to the radius of the minimal enclosing ball of σ. So, by combining Lemma C.2 and Jung's theorem we get:

θ(σ) = h(σ) L(σ) = h(σ) 2R(σ) 2R(σ) L(σ) = h(σ) 2R(σ) 2R enc (σ) L(σ) ≤ d + 1 2d • 2 d 2(d + 1) = d + 1 2d .
Jung's theorem becomes equality in the case of the regular d-simplex [START_REF] Danzer | Helly's theorem and its relatives[END_REF], so its thickness is θ(∆) = d+1 2d .

6 Figure 1 :

 61 Figure 1: List of all Coxeter diagrams.

Figure 2 :Figure 3 :

 23 Figure 2: Coxeter triangulations in R 2 .

Lemma 4 . 2 ([ 28 ,

 4228 Theorem 5]). If a triangulation of R d consists of only self-centred simplices, then it is a Delaunay triangulation.

Corollary 4 . 3 .

 43 If a simplex in a Coxeter triangulation is self-centred, then this triangulation is Delaunay.We now want to consider the converse: Lemma 4.4. Let R be the maximum circumradius in a Delaunay triangulation D of R d . Then any simplex in D with circumradius R is self-centred.

Definition 4 . 6 .

 46 The protection of a d-simplex σ in a Delaunay triangulation on a point set P is the minimal distance of points in P \ σ to the circumscribed ball of σ:δ(σ) = inf p∈P \σ d(p, B(σ)), where B(σ) is the circumscribed ball of σ.

Figure 4 :

 4 Figure 4: The visual representation of the normalized aspect ratio value, thickness, fatness and the radius ratio for simplices of Ãd , Bd , Cd and Dd triangulations.

E 6 E 7 E 8 1 e 1 + e 2 -e 2 -e 1 -e 1

 78112211 These graphs are called the Coxeter diagrams of type A d , D d , E 6 , E 7 and E 8 . The definition of Coxeter diagrams will be given in Definition A.10. -e 2

Figure 5 :

 5 Figure 5: An example of the root sets of the A 2 diagram before and after multiplying by √ DO.

s 2 =

 2 e 2 -e 3 , . . . , s d = e d -e d+1 . • B d : s 1 = e 1 -e 2 , s 2 = e 2 -e 3 , . . . , s d-1 = e d-1 -e d , s d = e d . • C d : s 1 = e 1 -e 2 , s 2 = e 2 -e 3 , . . . , s d-1 = e d-1 -e d , s d = 2e d . • D d : s 1 = e 1 -e 2 , s 2 = e 2 -e 3 , . . . , s d-1 = e d-1 -e d , s d = e d-1 + e d . • E 6 (in R 8 ): s 1 = 1 2 (e 1 + e 8 ) -1 2 (e 2 + e 3 + e 4 + e 5 + e 6 + e 7 ), s 2 = e 1 + e 2 , s 3 = e 2 -e 1 , s 4 = e 3 -e 2 , s 5 = e 4 -e 3 , s 6 = e 5 -e 4 . • E 7 (in R 8 ): s 1 = 1 2 (e 1 + e 8 ) -1 2 (e 2 + e 3 + e 4 + e 5 + e 6 + e 7 ), s 2 = e 1 + e 2 , s 3 = e 2 -e 1 , s 4 = e 3 -e 2 , s 5 = e 4 -e 3 , s 6 = e 5 -e 4 , s 7 = e 6 -e 5 . • E 8 : s 1 = 1 2 (e 1 + e 8 ) -1 2 (e 2 + e 3 + e 4 + e 5 + e 6 + e 7 ), s 2 = e 1 + e 2 , s 3 = e 2 -e 1 , s 4 = e 3 -e 2 , s 5 = e 4 -e 3 , s 6 = e 5 -e 4 , s 7 = e 6 -e 5 , s 8 = e 7 -e 6 . • F 4 : s 1 = e 2 -e 3 , s 2 = e 3 -e 4 , s 3 = e 4 , s 4 = 1 2 (e 1 -e 2 -e 3 -e 4 ). • G 2 (in R 3 ): s 1 = e 1 -e 2 , s 2 = -2e 1 + e 2 + e 3 .

Proposition A. 23 ([ 18 ,

 2318 Section 4.3]). Let R be a root system and S ⊂ R a set of simple roots. The alcove A o is an open simplex bounded by d+1 hyperplanes. Of them, d hyperplanes are of the form H s,0 = {x ∈ R d | x, s = 0}, one for each simple root s ∈ S and the final hyperplane is H s,1 = {x ∈ R d | x, s = 1} where s is the highest root.

Figure 7 :

 7 Figure 7: Above: Three root systems and corresponding affine hyperplanes in R 2 . Simple roots are marked in red, the highest root in blue and the fundamental domain in green. Each triangle in the background is an alcove. Below: The dual root systems put on the same grid of affine hyperplanes. For the sake of illustrating Proposition A.27, the coroot lattice as well as the Voronoi cell Vor(0) in the Voronoi diagram of the coroot lattice are shown as well.

  28. A subgraph of a Coxeter diagram G is a Coxeter diagram G obtained by omitting some vertices (and adjacent edges) of G or by decreasing the labels on one or more edges. Lemma A.29 ([18, Corollary 2.6]). Every subgraph of an affine Coxeter diagram has a positive definite Cartan matrix.

Theorem A. 30 .

 30 The complete list of affine Weyl groups and the corresponding Coxeter diagrams is as follows:

Figure 8 :

 8 Figure 8: The augmented Coxeter diagram for the Ãd triangulation and the notation of the facets of a corresponding simplex.

4 .

 4 The circumcentre coincides with the baricentre c = -d 2(d+1) , -d-2 2(d+1) , -d-4 2(d+1) , . . . , d

Figure 9 :

 9 Figure 9: The augmented Coxeter diagram for the Bd triangulation and the notation of the facets of a corresponding simplex.

Figure 10 :

 10 Figure 10: The augmented Coxeter diagram for the Cd triangulation and the notation of the facets of a corresponding simplex.

4 . 4 ,

 44 The circumcentre of the simplex is ( 1 4 {d} ) and the circumradius is R(σ) = √ d which is easily verifiable. The incentre is

Figure 11 :

 11 Figure 11: The augmented Coxeter diagram for the Dd triangulation and the notation of the facets of a corresponding simplex.

5 .d 2 . 6 .

 526 The longest edge is given by u d -u 0 and is equal to L(σ) = √ The aspect ratio, the thickness and the radius ratio are:

9 .Proposition B. 6 .

 96 (a) The vertex set of a D4 triangulation is a lattice. (b) No other vertex set of a Dd triangulation for d ≥ 5 is a lattice. Proof. (a) A point v ∈ R d is a vertex of the triangulation if and only if it lies in the intersection of at least d hyperplanes in H (as defined in Section A.5) that are linearly independent. Equivalently, the inner products of at least d linearly independent positive roots should be integers. Let E = {e 1 , ..., e d } be the canonical base of R d . Bourbaki [7, Planche IV] gives the explicit expressions of positive roots: R + = {e i -e j | i, j ∈ {1, . . . , d} and i < j} ∪ {e i + e j | i, j ∈ {1, . . . , d} and i < j}.

Ẽ6

ϕ 1 ϕ 3 ϕ 4 ϕ 5 ϕ 6 ϕ 2 ϕ 0 Figure 12 :

 2012 Figure 12: The augmented Coxeter diagram for the Ẽ6 triangulation and the notation of the facets of a corresponding simplex.

ϕ 0 ϕ 1 ϕ 3 ϕ 4 ϕ 5 ϕ 6 ϕ 7 ϕ 2 Figure 13 :

 213 Figure 13: The augmented Coxeter diagram for the Ẽ7 triangulation and the notation of the facets of a corresponding simplex.

1 2 e 8 -e 7 + 6 i=1(- 1 ) ν(i) e i 6 i=1ν

 8616 (i) is odd .

Ẽ8

ϕ 1 ϕ 3 ϕ 4 ϕ 5 ϕ 6 ϕ 7 ϕ 8 ϕ 0 ϕ 2 Figure 14 : 1 . 6 : x 4 -x 5 = 0 ϕ 7 : x 5 -x 6 = 0 ϕ 8 : x 6 -x 7 = 0 2 . 1 u 2 = 1 6 {7} , 5 6u 3 = -1 8 , 1 8 {6} , 7 8u 4 = 0 {2} , 1 6 {5} , 5 6u 5 = 0 {3} , 1 5 {4} , 4 5u 6 = 0 {4} , 1 4 {3} , 3 4u 7 = 0 {5} , 1 3 {2} , 2 3u 8 = 0 {6} , 1 2 {2} 6

 214164758621265387465554643732826 Figure 14: The augmented Coxeter diagram for the Ẽ8 triangulation and the notation of the facets of a corresponding simplex.

1 oFigure 16 :

 116 Figure 16: Illustration for the proof of Lemma C.2.

d i=0 F

 i=0 i , o be the circumcentre and -→ oq = d i=0 F i -→ ov i /F . Then:

d i=0 FF i h i ≥ d i=0 FF

 i=0i=0 i r i = dV . Therefore, d i=0 F i d(p, v i ) ≥ (d + 1)dV -dV = d 2 V . As before, let h(σ) = min i h i . Now observe that (d + 1)dV = d i=0 i h(σ) = F h(σ), hence d i=0 i d(p, v i ) ≥ dF h(σ) d + 1 .

Theorem C. 3 (

 3 Jung's theorem). Let S ⊆ R d be a compact set. Let L(S) be its diameter and R enc (S) be the radius of the minimum enclosing ball. Then:R enc (S) ≤ L(S) d 2(d + 1).Lemma C.4. Out of all d-simplices, the regular d-simplex ∆ has the maximum thickness equal to θ(∆) = d+1 2d .

9 .

 9 Proposition B.4. No vertex set of a Bd triangulation for d ≥ 3 is a lattice. Proof. A point v ∈ R d is a vertex of the triangulation if and only if it lies in the intersection of at least d hyperplanes in H (as defined in Section A.5) that are linearly independent. Equivalently, the inner products of at least d linearly independent positive roots should be integers. Let E = {e 1 , ..., e d } be the canonical base of R d . Bourbaki [7, Planche II] gives the explicit expressions of positive roots: R + = {e i | i ∈ {1, . . . , d}} ∪ {e i -e j | i, j ∈ {1, . . . , d} and i < j} ∪ {e i + e j | i, j ∈ {1, . . . , d} and i < j}.

Acknowledgements

The research leading to these results has received funding from the European Research Council (ERC) under the European Union's Seventh Framework Programme (FP/2007-2013) / ERC Grant Agreement No. 339025 GUDHI (Algorithmic Foundations of Geometry Understanding in Higher Dimensions).

We also thank Arijit Ghosh, Ramsay Dyer and Jean-Daniel Boissonnat for discussion and suggestions.

2. The vertices of σ are (in R 8 ) [START_REF] Conway | Sphere-packings, Lattices, and Groups[END_REF]Chapter 21]:

{4} , -5 12 {2} , 5 12

3. The smallest height falls on ϕ 4 and is equal to h(σ) = √ 2 6 (see the augmented diagram in Figure 12).

4. The circumcentre is (0 {2} , -

) and the circumradius is R(σ) = 1 √ 2 , which is easily verifiable. The incentre is (0, 1 12 , 1 6 , 1 4 , 1 3 , -1 3 , -1 3 , 1 3 ) and the inradius is r(σ) = 1 12 √ 2 , which is easily verifiable.

5. The longest edge is L(σ) = 2 √ 3 . 6. The aspect ratio, the thickness and the radius ratio are: 8. Observe that the inner products of the normal vector n = (0 {3} , 1, 0 {4} ) to the hyperplane x 4 = 0 with the circumcentre and the vertices have different signs: the inner product n, c = -1 6 is strictly negative, whereas the inner products n, u i are all non-negative. Therefore the hyperplane x 4 = 0 separates the circumcentre from the rest of the simplex, so by Theorem 4.5 the triangulation is not Delaunay.

9.

Proposition B.7. The vertex set of a Ẽ6 triangulation does not form a lattice.

Proof. A point v ∈ R 8 is a vertex of the triangulation if and only if it lies in the intersection of at least 6 hyperplanes in H (as defined in Section A.5) that are linearly independent. Equivalently, the inner products of at least 6 linearly independent positive roots should be integers.

Let E = {e 1 , ..., e 8 } be the canonical base of R 8 . Bourbaki [START_REF] Bourbaki | Lie groups and Lie algebras[END_REF]Planche V] gives the explicit expressions of positive roots:

ν(i) is even .

Let V be the vertex set of the corresponding triangulation. We will now prove that v = -2u 1 + 3u 2 + 3u 3 -2u 4 = 3 2 e 2 is not in the vertex set, which implies that V does not form a lattice. One can easily check that the positive roots that have integer inner product with v are exactly: {e j -e i | i, j ∈ {1, 3, 4, 5} and i < j} ∪ {e i + e j | i, j ∈ {1, 3, 4, 5} and i < j} and these roots span the vector space Vect({e 1 , e 3 , e 4 , e 5 }), which is 4-dimensional. Thus, there do not exist (r 1 , ..., r 6 ) that are linearly independent and have integer inner products with v. We therefore conclude that v does not belong to V .

3. The circumcentre is (- 14). 5. The longest edge is L(σ) = 1.

6. The aspect ratio, the thickness and the radius ratio are:

7. The volume of σ is: vol(σ) = 1 696729600 ∼ 1.435 • 10 -9 . Therefore the fatness is:

8. Observe that the inner products of the normal vector n = (0, 1, 0 {6} ) to the hyperplane x 2 = 0 with the circumcentre and the vertices have different signs: the inner product n, c = -1 12 is strictly negative, whereas the inner products n, u i are all non-negative. Therefore the hyperplane x 2 = 0 separates the circumcentre from the rest of the simplex, so by Theorem 4.5 the triangulation is not Delaunay.

9.

Proposition B.9. The vertex set of a Ẽ8 triangulation does not form a lattice.

Proof. A point v ∈ R 8 is a vertex of the triangulation if and only if it lies in the intersection of at least 8 hyperplanes in H (as defined in Section A.5) that are linearly independent. Equivalently, the inner products of at least 8 linearly independent positive roots should be integers.

Let E = {e 1 , ..., e 8 } be the canonical base of R 8 . Bourbaki [START_REF] Bourbaki | Lie groups and Lie algebras[END_REF]Planche VII] gives the explicit expressions of positive roots: R + = {e j -e i | i, j ∈ {1, . . . , 7} and i < j} ∪ {e i + e j | i, j ∈ {1, . . . , 7} and i < j} ∪

ν(i) is even .

Let V be the vertex set of the corresponding triangulation. We will now prove that v = -u 1 + 3u 2 + 4u 3 -6u 4 = e 2 is not in the vertex set, which implies that V does not form a lattice.

One can easily check that the positive roots that have integer inner product with v are exactly:

{e j -e i | i, j ∈ {1, . . . , 7} and i < j} ∪ {e i + e j | i, j ∈ {1, . . . , 7} and i < j} and these roots span the vector space Vect({e 1 , ..., e 7 }), which is 7-dimensional. Thus, there does not exist (r 1 , ..., r 8 ) ⊆ R + that are linearly independent and have integer inner products with v. We therefore conclude that v does not belong to V . 1. The delimiting hyperplanes of the fundamental simplex σ can be defined as follows:

2. The vertices of σ are: u 0 = (0, 0, 0, 0)

3. The inverse height proportions suggest that the smallest height corresponds to ϕ 2 and is equal to

(see the augmented diagram in Figure 15).

4. The circumcentre of the simplex is ( 1 2 , 0, 0, 0) and the circumradius is

2) and the inradius is

2) , which is easily verifiable.

5. The longest edge is given by u 4 -u 0 and is equal to L(σ) = 1.

6. The aspect ratio, the thickness and the radius ratio are:

7. The volume of σ is: vol(σ) = 1 576 = 0.00174. Therefore the fatness is:

Observe that all inner products of the normals s i to hyperplanes ϕ i and the corresponding opposite vertices u i are positive. Observe as well that the inner products with the circumcentre s i , c are either positive or zero. It implies that the circumcentre lies on the boundary of the simplex, therefore by Theorem 4.8 the triangulation is non-protected Delaunay.

9.

Proposition B.10. The vertex set of a F4 triangulation does not form a lattice.

Proof. A point v ∈ R 4 is a vertex of the triangulation if and only if it lies in the intersection of at least 4 hyperplanes in H (as defined in Section A.5) that are linearly independent. Equivalently, the inner products of at least 4 linearly independent positive roots should be integers.

Let E = {e 1 , ..., e 4 } be the canonical base of R 4 . Bourbaki [7, Planche VIII] gives the explicit expressions of positive roots:

Let V be the vertex set of the corresponding triangulation. We will now prove that v = u 1 +u 2 = 7 6 , 5 6 , 1 3 , 0 is not in the vertex set, which implies that V does not form a lattice.

One can easily check that the positive roots that have integer inner product with v are exactly e 4 , e 1 + e 2 , 1 2 (e 1 -e 2 -e 3 ± e 4 ) .

Note that 1 2 (e 1 -e 2 -e 3 + e 4 ) = 1 2 (e 1 -e 2 -e 3 -e 4 ) + e 4 , so these roots are not linearly independent. Thus, there does not exist (r 1 , ..., r 4 ) ⊆ R + that are linearly independent and have integer inner products with v. We therefore conclude that v does not belong to V . Proof. Let σ d be a d-simplex. We define a sequence of faces σ 1 ⊂ ... ⊂ σ d of σ d , such that for each i ∈ {1, ..., d-1}, σ i has dimension i and the height falling on σ i is the minimum height in σ i+1 .

We can now express the volume of σ in the following manner:

Observe that for each i, the set of edges of σ d is a subset of the set of edges of σ, therefore we have L(σ i ) ≤ L(σ d ).

By combining this fact with the volume expression we get:

From Lemma C.4, we have for each i, θ(σ i ) ≤ i+1 2i . Therefore:

and with that we conclude the proof.

D Proof of Lemma 4.4 and Lemma 4.7

Proof of Lemma 4.4. Let σ be a simplex in D with circumsphere S, whose circumcentre is c and circumradius R.

We assume that the circumcentre c lies outside of σ and derive a contradiction. Because the circumcentre lies outside σ there exists a facet τ of σ, whose supporting hyperplane H τ separates c from σ. We denote the simplex in D that shares the facet τ with σ by σ . We write S for the circumsphere of σ and denote its circumcentre by c and circumradius by R . The (d -2)-dimensional sphere T that forms the intersection of S and S , divides S into a part that lies inside S and a cap that lies outside S .

We shall call the line on which c and c lie . If we restrict to any two-dimensional plane P that contains , we see that S ∩ P and S ∩ P are circles. We shall think of as vertical in P (see Figure 18). The circumcentres can't coincide, because then they would lie on H τ . So the circles S ∩ P and S ∩ P intersect transversely in two points. This means that S ∩ P is subdivided into two parts: a part inside S ∩ P and a cap outside S ∩ P .

We shall assume that the cap lies below the part inside S ∩ P , see Figure 18. This implies that c lies below c on . This can be seen as follows: assume that both S and H τ are fixed. This means that points of intersection of S ∩ P and S ∩ P are fixed, but the circumcentre c can be varied. We now let c descend along from +∞ to -∞. As long as c and c do not coincide, the cap of S ∩ P outside S ∩ P remains stable. At the point of coincidence of c and c the inside and outside switch. It follows by considering the limit cases that the cap S ∩ P outside S ∩ P lies below the cap inside as long as c lies below c on .

We now make two important observations. Firstly, because the triangulation D is Delaunay, the sphere S doesn't contain the vertex p = σ \ τ . Hence p lies on the cap of S which is outside S . Secondly, as we assume that the circumcentre c lies outside of σ, c lies above H τ ∩ P . Now let o be the centre of T = S ∩ S and let q be a vertex of τ . Because d(c, o) < d(c , o), the distance d(c, q) is strictly less than d(c , q). By remarking that d(c, q) = R and d(c , q) = R , we get R < R , which is a contradiction with the hypothesis that R is the largest circumradius in D. Proof of Lemma 4.7. We use the same construction and the same notations as in the proof of Lemma 4.4 (see Figure 18). Observe that by hypothesis o coincides with c. If c was different from c , then the radius R would be bigger than R, which would lead to a contradiction. Therefore c coincides with c , so σ and σ share the same circumball. We conclude the proof by observing that the vertex σ \ τ lies on the circumball of σ, therefore σ has zero protection.

E Comparison of quality measures between