SHARP APPROXIMATE CARATHÉODORY THEOREM AND APPLICATION TO ITERATED DELAUNAY REFINEMENT

Raphaël Tinarrage \orcid 0000-0002-1404-1095 · 2026

Read SHARP APPROXIMATE CARATHÉODORY THEOREM AND APPLICATION TO ITERATED DELAUNAY REFINEMENT by Raphaël Tinarrage \orcid 0000-0002-1404-1095 (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2606-25854.txt.

Introduction

Raphaël Tinarrage studies Delaunay refinement. The process builds meshes in geometry software by splitting a region into simplices. A simplex is the simplest shape in each dimension. Unlike plain subdivision, a refined Delaunay mesh need not nest inside the previous one, so it is not obvious that the pieces keep shrinking. Tinarrage asks how fast simplex diameters fall under repeated refinement for several choices of inserted Steiner points.

Shrink bounds come out explicitly for several families. They include Delaunay versions of barycentric and edgewise subdivision. The proofs reduce the geometry to covering estimates for flat simplices. Those estimates come from a sharpened approximate Carathéodory theorem. The proof uses a pivotal sampling twist on Maurey's empirical method. Theory and numerical tests agree on the outcome. Delaunay refinements contract more strongly than plain subdivision does. That is welcome news for methods that approximate maps between meshes.

Catalog record

CREATORRaphaël Tinarrage \orcid 0000-0002-1404-1095
YEAR2026
COLLECTIONPAPERS
FORMATTXT
FILE SIZE121 KB
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2606.25854

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

SHARP APPROXIMATE CARATHÉODORY THEOREM AND APPLICATION TO ITERATED DELAUNAY REFINEMENT Raphaël Tinarrage \orcid 0000-0002-1404-1095 Abstract We analyze the decrease of simplex diameters under iterated refinement of spherical Delaunay complexes. Unlike in ordinary subdivision, the refined Delaunay complex need not be a subdivision of the previous one, so mesh contraction is not automatic. We derive explicit contraction bounds for several families of Steiner points, including Delaunay analogues of barycentric and edgewise subdivision. The proof reduces the problem to sharp covering estimates for Euclidean simplices. These estimates are obtained through a strengthening of Maurey’s empirical method via pivotal sampling and a dimension-dependent version of the approximate Carathéodory theorem. Theoretical results and numerical experiments show that Delaunay refinements achieve stronger contraction than their subdivision counterparts. Contents 1 Introduction 1.1 Motivations Subdivision is a fundamental operation in computational geometry and topology. In geometry, a mesh is refined in order to represent a domain more accurately and to improve the performance of numerical methods [ 69 , 57 , 64 , 41 , 17 , 26 ] . In topology, subdivision refines a triangulation without changing its underlying space, allowing one to relate different triangulations through common subdivisions, to compute topological invariants, and to approximate continuous maps by simplicial maps [ 48 , 81 , 52 , 36 , 37 , 32 ] . The last point is our main motivation. Let K,L be finite simplicial complexes, and let f\colon|K|\to|L| be a continuous map between their geometric realizations. Simplicial approximation produces a simplicial map g\colon K^{\prime}\to L , defined on a subdivision K^{\prime} of K , such that the realization |g|\colon|K^{\prime}|\to|L| is homotopic to f . Thus, simplicial approximation is a way of “triangulating a map”: it replaces a continuous map by a finite combinatorial object. The simplicial approximation theorem says that such an approximation exists once K has been subdivided finely enough, i.e., once the edge lengths are sufficiently small; see [ 44 , Theorem 2C.1] . Thus, we need a refinement procedure that produces triangulations with arbitrarily small simplices. The standard choice is barycentric subdivision . However, it is often inefficient in practice because the number of vertices grows rapidly under iteration. The purpose of this paper is to study an alternative refinement procedure based on Delaunay complexes . Starting from a point set, we insert Steiner points and recompute the Delaunay complex. This procedure is closer in spirit to mesh generation than to ordinary subdivision. But it raises a difficulty: recomputing the Delaunay complex alters the previous simplices. In particular, the simplex diameters need not decrease at each refinement step. We prove that several natural Delaunay refinements do shrink after sufficiently many steps ( Corollary 1 ). More precisely, we study four families of Steiner points: the minicenters of the facets , the barycenters of the facets , the equal-weight barycenters of all faces (as in barycentric subdivision), and the k -fold barycenters of the facets for k\geq 2 (as in edgewise subdivision). We restrict our attention to a particular setting: refinements of Euclidean and spherical Delaunay complexes. In particular, our results do not give a general refinement procedure for arbitrary abstract simplicial complexes. Still, this is the setting needed in our companion paper, where we use simplicial approximation to obtain triangulations of manifolds [ 75 ] . The proofs are based on sharp Euclidean covering estimates for a simplex. For each refinement scheme, we ask how far a point inside the simplex can be from the old vertices together with the newly inserted Steiner points. We prove the best possible dimension-dependent bounds ( Theorem 1 ). For the equal-weight barycenters, we employ pivotal sampling to strengthen the argument underlying Maurey’s empirical method ( Lemma 4 ). For the k -fold barycenters, we prove a sharp version of the approximate Carathéodory theorem ( Theorem 3 ). These results may help guide refinement strategies in computational settings such as mesh generation, where both contraction rate and mesh quality matter. The final section illustrates this experimentally: by recomputing the Delaunay complex, the refinement can counteract the accumulation of poorly shaped simplices under iteration. 1.2 Related work 1.2.1 Classical subdivision methods The classical way to refine a simplicial complex is barycentric subdivision . It works in every dimension and gives a uniform decrease of the mesh size. If \sigma is a d -simplex and \sub(\sigma) denotes its barycentric subdivision, then the maximal diameter of its simplices satisfies \maxdiam(\sub(\sigma))\leq\frac{d}{d+1}\diam(\sigma). (1) Thus, after n iterations of barycentric subdivision, the simplicial complex \sub^{n}(\sigma) satisfies \maxdiam(\sub^{n}(\sigma))\leq\bigg(\frac{d}{d+1}\bigg)^{n}\diam(\sigma). In particular, all edge lengths can be made arbitrarily small. The drawback is combinatorial: \sub(\sigma) is a simplicial complex with 2^{d+1}-1 vertices—one barycenter for each face of \sigma —and (d+1)! facets. Thus repeated barycentric subdivision quickly becomes expensive. A more economical alternative is the Coxeter–Freudenthal–Kuhn subdivision of simplices, also called edgewise subdivision [ 40 , 54 , 33 , 4 , 42 ] . It depends on a parameter k\geq 2 and creates a simplicial complex, still denoted \sub(\sigma) , with \binom{d+k}{k} vertices. More precisely, k -edgewise subdivision introduces all the k -fold barycenters of \sigma=\{v_{0},\dots,v_{d}\} , by which we mean the equal-weight barycenters of all k -tuples (v_{i_{1}},\dots,v_{i_{k}}) , repetitions allowed. The simplices of \sub(\sigma) are obtained from the Freudenthal–Kuhn triangulation of the unit cube, equivalently from the Coxeter hyperplane arrangement; see [ 10 , Appendix A.1] for details. This popular construction appears in several computational settings [ 43 , 79 , 29 , 9 , 10 , 11 , 19 , 6 , 56 ] . For instance, 2 -edgewise subdivision introduces the midpoints of the edges of \sigma . It subdivides a 2 -simplex into four homothetic triangles, and a 3 -simplex into eight (not all homothetic) tetrahedra; see Figure 1 . In general, k -edgewise subdivision satisfies the estimate \maxdiam(\sub(\sigma))\leq\min\bigg\{1,\frac{\lfloor\frac{d+1}{2}\rfloor}{k}\bigg\}\diam(\sigma). (2) This bound is sharp. We have not found it in the literature and prove it in Section B.1 . When \lfloor\frac{d+1}{2}\rfloor/k\geq 1 , k -edgewise subdivision does not guarantee contraction by an absolute constant smaller than 1 . This obstruction already appears for tetrahedra with k=2 : inserting the edge midpoints creates a central octahedron, which must be triangulated by choosing a diagonal. The chosen diagonal can have length arbitrarily close to \diam(\sigma) . A standard way to control the resulting diameters is to split the central octahedron along its shortest diagonal, as in red refinement and in the related shortest-interior-edge partition [ 80 , 53 , 50 ] . This yields the contraction factor 1/\sqrt{2} . Related refinement schemes were studied in [ 61 , 55 ] . However, in higher dimensions, the central cell is a hypersimplex rather than an octahedron, and there is no single diagonal to choose. The literature instead focuses on the congruence classes of simplices produced by the subdivision [ 4 , 51 ] . In this article, we study a different refinement strategy based on Delaunay complexes. The resulting contraction bounds, collected in Table 1 , are significantly sharper. For instance, the Delaunay analogue of 2 -edgewise subdivision attains the factor \sqrt{(d-1)/(2d)} for d\geq 2 , improving on the barycentric bound d/(d+1) , on the 2 -edgewise bound \lfloor\frac{d+1}{2}\rfloor/2 and, in dimension d=3 , on the red refinement bound 1/\sqrt{2} .

Read the complete text