Delaunay and Regular Triangulations as Lexicographic Optimal Chains

Autor: David Cohen-Steiner, André Lieutier, Julien Vuillamy
Přispěvatelé: Understanding the Shape of Data (DATASHAPE), Inria Sophia Antipolis - Méditerranée (CRISAM), Institut National de Recherche en Informatique et en Automatique (Inria)-Institut National de Recherche en Informatique et en Automatique (Inria)-Inria Saclay - Ile de France, Institut National de Recherche en Informatique et en Automatique (Inria), Dassault Systèmes Provence
Jazyk: angličtina
Rok vydání: 2023
Předmět:
Zdroj: Discrete and Computational Geometry
Discrete and Computational Geometry, 2023, 70, ⟨10.1007/s00454-023-00485-1⟩
ISSN: 0179-5376
1432-0444
DOI: 10.1007/s00454-023-00485-1⟩
Popis: International audience; 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.
Databáze: OpenAIRE
Externí odkaz: