Generalized Delaunay triangulations of non-convex domains (Q922670)

L'aut. considère le problème suivant: étant donné un ensemble fini S de points du plan, déterminer une triangulation de l'enveloppe convexe de S dont les sommets sont exactement les points de S et dont les triangles sont autant que possible non-dégénérés. La solution du problème proposé est donnée par la triangulation de Delaunay. Celle-ci est définie pour \(\forall x\in S\) au moyen d'un lieu géométrique P(x) plan. Ce lieu a la forme d'un polygone, qui peut être illimité. La collection des frontières des polygones P(x), \(x\in S\), constitue le diagramme de Voronoi associé à S. On en déduit la triangulation de Delaunay. Ce procédé intervient dans des méthodes de calcul telles que les méthodes Lagrangiennes libres en dynamique des fluides. Deux théorèmes suggèrent des généralisations de la notion examinée pour des domaines non-convexes; elles s'avèrent être équivalentes. Les triangulations de Delaunay suscitent un problème d'unicité; au cas où celles-ci sont généralisées, une démonstration de l'existence en est donnée. Finalement l'aut. établit un algorithme en vue de la construction de ces triangulations.