Regular triangulations as lexicographic optimal chains

David Cohen-Steiner (1, 2) , André Lieutier (3) , Julien Vuillamy (1, 3, 4)

1 COMUE UCA - COMUE Université Côte d'Azur (2015-2019)
2 DATASHAPE - Understanding the Shape of Data
3 Dassault Systèmes
4 TITANE - Geometric Modeling of 3D Environments

We introduce a total order on n-simplices in the n-Euclidean space for which the support of the lexicographic-minimal chain with the convex hull boundary as boundary constraint is precisely the n-dimensional Delaunay triangulation, or in a more general setting, the regular triangulation of a set of weighted points. This new characterization of regular and Delaunay triangulations is motivated by its possible generalization to submanifold triangulations as well as the recent development of polynomial-time triangulation algorithms taking advantage of this order.

Domaines: Géométrie algorithmique [cs.CG]

David Cohen-Steiner, André Lieutier, Julien Vuillamy. Regular triangulations as lexicographic optimal chains. 2019. ⟨hal-02391285⟩