Construction de la triangulation de Delaunay de segments par ...

Construction de la triangulation de Delaunay de
segments par un algorithme de flip
Mathieu Brévilliers
Laboratoire LMIA
Université de Haute-Alsace
Mathieu Brévilliers (LMIA, UHA) Soutenance de thèse 9 décembre 2008 1 / 42Triangulation de points
Mathieu Brévilliers (LMIA, UHA) Soutenance de thèse 9 décembre 2008 2 / 42Triangulation de points
Mathieu Brévilliers (LMIA, UHA) Soutenance de thèse 9 décembre 2008 3 / 42Triangulation de points
Théorème
′Pour tout ensemble S de n sites, soit n le nombre de sites sur la
frontière de l’enveloppe convexe de S.
Toute triangulation de S admet :
′2n− n − 2 faces et
′3n− n − 3 arêtes.
′Exemples où n= 8 et n = 6 : 8 faces et 15 arêtes
Mathieu Brévilliers (LMIA, UHA) Soutenance de thèse 9 décembre 2008 4 / 42Triangulation de Delaunay
Triangulation quelconque
Mathieu Brévilliers (LMIA, UHA) Soutenance de thèse 9 décembre 2008 5 / 42Triangulation de Delaunay
Triangulation quelconque Triangulation de Delaunay
Mathieu Brévilliers (LMIA, UHA) Soutenance de thèse 9 décembre 2008 5 / 42Triangulation de Delaunay
Triangulation quelconque Triangulation de Delaunay
Régularité
La triangulation de Delaunay maximise le minimum des
angles des triangles.
Mathieu Brévilliers (LMIA, UHA) Soutenance de thèse 9 décembre 2008 5 / 42Algorithme de flip
Une triangulation quelconque de S
⇓
Modifications locales
⇓
Triangulation de Delaunay de S
Mathieu Brévilliers (LMIA, UHA) Soutenance de thèse 9 décembre 2008 6 / 42Algorithme de flip
Une triangulation ...