La triangulation de Delaunay est une structure largement étudiée et utilisée en géométrie algorithmique. En 2D, il est bien connu que sa taille (nombre d’arêtes) est linéaire du nombre de points. En revanche, en 3D, sa taille peut varier de linéaire à quadratique. Dans cette thèse, on se place dans le cas où les points sont distribués sur une surface. On souhaite alors estimer le taille de triangulation 3D de Delaunay de ces points selon la nature de la surface sur laquelle ils sont distribués et selon la manière dont ils sont distribués sur la surface.

Dans la littérature, plusieurs cas ont déjà été étudiés. Sur un cylindre, on peut trouver un bon échantillon ( $(\epsilon,\kappa)$-sample ) qui donne à la triangulation une taille $n\sqrt{n}$ en ordre de grandeur [Erickson, 2001]. Lorsque l’échantillon est aléatoire, la configuration en $n\sqrt{n}$ se trouve improbable, et la taille moyenne de la triangulation tombe à $n\log n$ [Devillers, Erickson & Goaoc, 2008]. Néanmoins, le cas du cylindre est particulier, voire pathologique, pour la triangulation de Delaunay. Aussi on s’intéresse aux surfaces dites “génériques”, présentant moins de symétries. Pour de telles surfaces, avec un bon échantillon, il est démontré que la triangulation a une taille $n\log n$ [Attali, Boissonnat & Lieutier, 2003]. L’objet de cette thèse est de démontrer que lorsque les points sont distribués aléatoirement sur une surface générique, la taille moyenne de la triangulation est linéaire.

Afin de démontrer ce résultat, on fera un détour par les graphes de régions vides en 2D, notamment les graphes d’ellipses alignées aux axes, dans lesquels 2 sommets p et q sont voisins s’il existe une ellipse alignée au axe d’un repère et passant par p et q, qui ne contienne pas d’autre point de l’échantillon. En effet, pour étudier la triangulation 3D de points sur une surface, on est amenés à regarder des intersections sphères/surface dont on observe qu’elles approchent des ellipses qui s’alignent aux axes de courbure de la surface. On présentera alors une méthode pour étudier les graphes de régions de vides, et illustrera cette méthode sur des graphes d’ellipses vides.

Une fois l’approche 2D formalisée, on reviendra sur la triangulation 3D de points sur une surface générique. On commencera par définir ce que l’on entend par générique, puis on présentera comment on parvient à retrouver, dans ce contexte, les graphes d’ellipses vides sus-cités, pour finalement démontrer que lorsque les points sont distribués aléatoirement sur une surface générique, la triangulation de Delaunay a une taille moyenne linéaire.