Un maillage est une approximation d’un domaine en éléments simples qu’on appelle des simplexes ‹: triangles dans le plan, tétraèdres en dimension 3 et leurs analogues en dimensions supérieures. La qualité de l’approximation dépend de la forme des simplexes utilisés. L’une des questions importantes est la construction de « ‹bonnes‹ » triangulations, c’est-à-dire des triangulations dont les éléments ne sont pas trop aplatis et ont des angles dièdres suffisamment grands. Cette question est centrale dès que l’on veut produire une image de synthèse réaliste ou simuler un phénomène physique complexe.
Ce cours montre tout d’abord que, pour un ensemble de points donné, la triangulation de Delaunay est optimale de plusieurs points de vue. On peut améliorer la qualité d’un maillage en choisissant la position de ses sommets. On introduit pour cela la notion d’ε-net qui caractérise la qualité d’un ensemble fini de points échantillonnant un domaine. On montre que de tels échantillons peuvent être construits de manière efficace en toutes dimensions. Ce résultat est suffisant en dimension 2 pour assurer que la triangulation de Delaunay de tels échantillons est bonne, ce qui la rend très utile en pratique. Malheureusement, cette propriété n’est pas vraie en dimensions 3 et au-delà : les triangulations tridimensionnelles peuvent contenir des simplexes très aplatis quel que soit le raffinement du maillage. Si le problème est bien connu, aussi bien des mathématiciens qui cherchent à établir des garanties que des ingénieurs qui utilisent ces maillages pour faire des calculs, il est très difficile à résoudre. Le cours présente quelques-unes des avancées théoriques obtenues au cours des dix dernières années ainsi que des solutions heuristiques efficaces. Il présente notamment un algorithme randomisé qui permet de construire de bonnes triangulations de Delaunay en toutes dimensions. L’algorithme s’appuie sur une version algorithmique du lemme local de Lovász, un résultat algorithmique majeur dû à Moser et Tardos.
