Une triangulation d’un ensemble de points dans le plan (ou en dimension supérieure) telle qu’aucun point ne se trouve à l’intérieur du cercle circonscrit de tout triangle (propriété de cercle vide) ; elle tend à maximiser l’angle minimal des triangles et est largement utilisée pour le maillage et l’interpolation.

Principe

Le critère de Delaunay impose des conditions locales de cercle circonscrit vide qui, satisfaites globalement, produisent une triangulation aux qualités de forme favorables ; le complexe de Delaunay est dual du diagramme de Voronoï des mêmes sites.

Démonstration

Pour un ensemble fini de points planaires, construire le graphe triangulaire dont les triangles ont la propriété que leur cercle circonscrit ne contient aucun autre point d’entrée ; par exemple, effectuer des flips d’arêtes sur une triangulation arbitraire jusqu’à ce que les angles opposés satisfassent l’inégalité de Delaunay conduit à la triangulation de Delaunay.

Mauvaise application

Employer la triangulation de Delaunay sur des jeux de points mal conditionnés sans traiter les cas cocirculaires ou presque cocirculaires (par ex. ignorer la précision numérique) peut créer des faces ambiguës, des éléments inversés dans un maillage ou des artefacts d’interpolation.

Conséquence

Une triangulation de Delaunay correcte produit des maillages avec un angle minimal borné, de bons rapports d’aspect et des centres circonscrits situés dans des cellules de Voronoï bien définies, ce qui profite aux méthodes d’éléments finis et aux requêtes de plus proche voisin.

Inversion

La structure duale, le diagramme de Voronoï, inverse la perspective en assignant des régions aux sites plutôt que de composer des triangles à partir de points ; cette inversion met en évidence le partitionnement par proximité au lieu de la connectivité simpliciale.

Limite

Défini pour des ensembles de points discrets en espaces euclidiens avec généralisation en dimensions supérieures sous la forme d’un complexe de Delaunay ; exclut les variantes pondérées (triangulations régulières), les arêtes contraintes et les métriques non euclidiennes sauf adaptation.

Tension sémantique

La triangulation de Delaunay est en tension avec les triangulations contraintes et les techniques d’optimisation de maillage : Delaunay optimise un critère d’angles sous la règle du cercle vide, tandis que les méthodes contraintes privilégient la fidélité aux frontières ou la qualité selon une métrique plutôt que l’optimalité Delaunay pure.

Synthèse

La triangulation de Delaunay est le complexe simplicial dual de la partition de Voronoï qui impose la condition de cercle circonscrit vide ; elle fournit des triangulations aux bonnes propriétés locales de forme, utiles pour le maillage, l’interpolation et le calcul géométrique.