15.5 Les diagrammes de Vorono¨ ı
549
D´ efinition 15.18 Un sous-ensemble D du plan est convexe si, pour toute paire de
points P, Q ∈ D, le segment P Q est inclus dans D.
La figure 15.33 donne des exemples d’ensembles convexe et non convexe.
(a) Un
ensemble
convexe
(b) Un ensemble non
convexe
Fig. 15.33. Ensembles convexe et non convexe
Proposition 15.19 Une cellule de Vorono¨ ı est un sous-ensemble convexe du plan. Si
la cellule est finie (c’est-` a-dire incluse dans un disque de rayon r), c’est un polygone du
plan.
Preuve On donne ses grandes lignes et on laisse le reste en exercice. Un demi-plan est
un sous-ensemble convexe du plan. Une intersection d’ensembles convexes est convexe.
Construction du diagramme de Vorono¨ ı d’un ensemble S Il n’est pas facile en
pratique de programmer la construction du diagramme de Vorono¨ ı d’un ensemble S de
sites, surtout quand le nombre d’´ el´ ements de S est grand. Il se fait beaucoup de recherche
en g´ eom´ etrie combinatoire et en informatique sur ce sujet. Certains programmes sont
cependant disponibles sur Internet ou dans des langages de manipulation symbolique.
Par exemple, une fonction de Mathematica a ´ et´ e utilis´ ee pour construire les figures 15.30
et 15.32.
Les diagrammes de Vorono¨ ı sont souvent pr´ esent´ es avec leurs « duaux », les triangulations de Delaunay. Un probl` eme important de g´ eom´ etrie combinatoire est de construire
une partition d’un ensemble en triangles (on dit une triangulation), ayant deux `
a deux
soit une intersection vide, soit une arˆ ete en commun, soit encore un sommet en commun. Pour un ensemble S de sites et son diagramme de Vorono¨ ı, la triangulation de
Delaunay est d´ efinie ainsi : les sommets des triangles sont les sites de S, et on trace
549
D´ efinition 15.18 Un sous-ensemble D du plan est convexe si, pour toute paire de
points P, Q ∈ D, le segment P Q est inclus dans D.
La figure 15.33 donne des exemples d’ensembles convexe et non convexe.
(a) Un
ensemble
convexe
(b) Un ensemble non
convexe
Fig. 15.33. Ensembles convexe et non convexe
Proposition 15.19 Une cellule de Vorono¨ ı est un sous-ensemble convexe du plan. Si
la cellule est finie (c’est-` a-dire incluse dans un disque de rayon r), c’est un polygone du
plan.
Preuve On donne ses grandes lignes et on laisse le reste en exercice. Un demi-plan est
un sous-ensemble convexe du plan. Une intersection d’ensembles convexes est convexe.
Construction du diagramme de Vorono¨ ı d’un ensemble S Il n’est pas facile en
pratique de programmer la construction du diagramme de Vorono¨ ı d’un ensemble S de
sites, surtout quand le nombre d’´ el´ ements de S est grand. Il se fait beaucoup de recherche
en g´ eom´ etrie combinatoire et en informatique sur ce sujet. Certains programmes sont
cependant disponibles sur Internet ou dans des langages de manipulation symbolique.
Par exemple, une fonction de Mathematica a ´ et´ e utilis´ ee pour construire les figures 15.30
et 15.32.
Les diagrammes de Vorono¨ ı sont souvent pr´ esent´ es avec leurs « duaux », les triangulations de Delaunay. Un probl` eme important de g´ eom´ etrie combinatoire est de construire
une partition d’un ensemble en triangles (on dit une triangulation), ayant deux `
a deux
soit une intersection vide, soit une arˆ ete en commun, soit encore un sommet en commun. Pour un ensemble S de sites et son diagramme de Vorono¨ ı, la triangulation de
Delaunay est d´ efinie ainsi : les sommets des triangles sont les sites de S, et on trace