550
15 Flashs-science
le segment P i P j entre les sites P i et P j si les cellules V (P i ) et V (P j ) ont une arˆ ete
commune (figure 15.34).
Fig. 15.34. La triangulation de Delaunay (en trait noir ´ epais) associ´ ee au diagramme de
Vorono¨ ı de la figure 15.32 (en trait fin gris)
´
Etant donn´ e un ensemble de sites, il existe plusieurs triangulations pour lesquelles
les sommets des triangles sont situ´ es aux points de S. Les triangulations de Delaunay ont de tr` es bonnes propri´ et´ es, entre autres parce que leurs triangles sont « plus
´ equilat´ eraux » (moins aplatis) en moyenne que ceux d’autres triangulations. Elles sont
donc tr` es utilis´ ees dans tous les probl` emes appliqu´ es o` u des maillages sont requis (voir
aussi l’exercice 24).
Le probl` eme r´ eciproque Nous avons vu qu’´ etant donn´ e un ensemble S de sites,
son diagramme de Vorono¨ ı consiste en une partition du plan en cellules convexes.
Les cellules born´ ees sont des polygones convexes. La fronti` ere de chaque cellule non
born´ ee est form´ ee d’un nombre fini de segments de droite et de deux demi-droites.
Rien n’empˆ eche de g´ en´ eraliser le concept du diagramme de Vorono¨ ı `
a des surfaces non
planes. La r´ eciproque est beaucoup plus difficile : supposons que l’on ait une partition du
plan ou d’une autre surface en cellules du type d´ ecrit ci-dessus. Sous quelles conditions
existe-t-il un ensemble de sites S dont cette partition est le diagramme de Vorono¨ ı ?
On peut d´ ej` a penser ` a un processus de mod´ elisation qui conduirait `
a un diagramme
de Vorono¨ ı. En effet, supposons que l’on d´ epose des gouttes d’encre aux points d’un
ensemble de sites sur un papier buvard. Alors, les gouttes s’´ etendent et se rejoignent
pr´ ecis´ ement sur les fronti` eres des cellules de Vorono¨ ı (voir, par exemple, le chapitre 4
o` u ce genre de probl` eme est examin´ e et, en particulier, l’exercice 19 de ce chapitre).
Un mod` ele semblable est obtenu si, au lieu de papier buvard, on consid` ere une surface
15 Flashs-science
le segment P i P j entre les sites P i et P j si les cellules V (P i ) et V (P j ) ont une arˆ ete
commune (figure 15.34).
Fig. 15.34. La triangulation de Delaunay (en trait noir ´ epais) associ´ ee au diagramme de
Vorono¨ ı de la figure 15.32 (en trait fin gris)
´
Etant donn´ e un ensemble de sites, il existe plusieurs triangulations pour lesquelles
les sommets des triangles sont situ´ es aux points de S. Les triangulations de Delaunay ont de tr` es bonnes propri´ et´ es, entre autres parce que leurs triangles sont « plus
´ equilat´ eraux » (moins aplatis) en moyenne que ceux d’autres triangulations. Elles sont
donc tr` es utilis´ ees dans tous les probl` emes appliqu´ es o` u des maillages sont requis (voir
aussi l’exercice 24).
Le probl` eme r´ eciproque Nous avons vu qu’´ etant donn´ e un ensemble S de sites,
son diagramme de Vorono¨ ı consiste en une partition du plan en cellules convexes.
Les cellules born´ ees sont des polygones convexes. La fronti` ere de chaque cellule non
born´ ee est form´ ee d’un nombre fini de segments de droite et de deux demi-droites.
Rien n’empˆ eche de g´ en´ eraliser le concept du diagramme de Vorono¨ ı `
a des surfaces non
planes. La r´ eciproque est beaucoup plus difficile : supposons que l’on ait une partition du
plan ou d’une autre surface en cellules du type d´ ecrit ci-dessus. Sous quelles conditions
existe-t-il un ensemble de sites S dont cette partition est le diagramme de Vorono¨ ı ?
On peut d´ ej` a penser ` a un processus de mod´ elisation qui conduirait `
a un diagramme
de Vorono¨ ı. En effet, supposons que l’on d´ epose des gouttes d’encre aux points d’un
ensemble de sites sur un papier buvard. Alors, les gouttes s’´ etendent et se rejoignent
pr´ ecis´ ement sur les fronti` eres des cellules de Vorono¨ ı (voir, par exemple, le chapitre 4
o` u ce genre de probl` eme est examin´ e et, en particulier, l’exercice 19 de ce chapitre).
Un mod` ele semblable est obtenu si, au lieu de papier buvard, on consid` ere une surface