15.5 Les diagrammes de Vorono¨ ı
547
Dessiner le diagramme de Vorono¨ ı permet aux concepteurs de visualiser les zones mal
desservies parce que certaines parcelles sont trop grandes et d’apporter des correctifs.
Une parenth` ese historique Le math´ ematicien ukrainien Vorono¨ ı (1868-1908) a d´ efini
les diagrammes de Vorono¨ ı en dimension quelconque, mais c’est en fait Dirichlet (18051859) qui les a d’abord ´ etudi´ es en deux et trois dimensions. Le concept est donc aussi
appel´ e tessellation de Dirichlet. On trouve mˆ eme d´ ej` a de tels diagrammes dans les
travaux de Descartes en 1644.
On peut remplacer les antennes par des bureaux de poste, des hˆ opitaux ou encore,
par des ´ ecoles. Dans ce dernier cas, on pourrait vouloir d´ efinir le bassin de chaque ´ ecole
d’une r´ egion de telle sorte que chaque enfant soit affect´ e ` a l’´ ecole la plus proche de son
domicile. Les diagrammes de Vorono¨ ı ont donc de tr` es nombreuses applications.
´
Enon¸ cons le probl` eme en termes math´ ematiques.
D´ efinition 15.15 Soit S = {P 1 , . . . , P n } un ensemble de points distincts d’une r´ egion
D ⊂ R
2 . Les points P i sont appel´ es sites.
1. Pour chaque site P i , la cellule de Vorono¨ ı de P i , not´ ee V (P i ), est l’ensemble des
points de D qui sont plus proches de P i que des autres sites P j (ou ´ egalement
proches) :
V (P i ) = {Q ∈ D, |P i Q| ≤ |P j Q|, j = i}.
2. Le diagramme de Vorono¨ ı de S, not´ e V (S), est la d´ ecomposition de D en cellules
de Vorono¨ ı.
Pour d´ ecider comment aborder le probl` eme, prenons le cas o` u D = R
2 et S = {P, Q},
P = Q.
Proposition 15.16 Soient P et Q deux points distincts du plan. La m´ ediatrice du
segment P Q est le lieu g´ eom´ etrique des points `
a ´ egale distance de P et de Q. C’est une
droite (D) perpendiculaire au segment P Q en son milieu. Tous les points R d’un cˆ ot´ e
de (D) satisfont ` a |P R| < |QR|, et ceux de l’autre cˆ ot´ e satisfont ` a |P R| > |QR|. Donc,
le diagramme de Vorono¨ ı de S est la partition de R
2 en deux demi-plans ferm´ es limit´ es
par (D) (figure 15.31).
Preuve La preuve est laiss´ ee en exercice.
Nous avons maintenant l’ingr´ edient de base pour trouver la cellule de Vorono¨ ı V (P i )
d’un point P i appartenant `
a un ensemble de sites S = {P 1 , . . . , P n }. Nous nous limiterons
au cas D = R
2 (figure 15.32).
Proposition 15.17 ´
Etant donn´ e un ensemble S = {P 1 , . . . , P n } de sites, pour chaque
paire de points (P i , P j ), la m´ ediatrice du segment P i P j divise le plan en deux demi-plans
547
Dessiner le diagramme de Vorono¨ ı permet aux concepteurs de visualiser les zones mal
desservies parce que certaines parcelles sont trop grandes et d’apporter des correctifs.
Une parenth` ese historique Le math´ ematicien ukrainien Vorono¨ ı (1868-1908) a d´ efini
les diagrammes de Vorono¨ ı en dimension quelconque, mais c’est en fait Dirichlet (18051859) qui les a d’abord ´ etudi´ es en deux et trois dimensions. Le concept est donc aussi
appel´ e tessellation de Dirichlet. On trouve mˆ eme d´ ej` a de tels diagrammes dans les
travaux de Descartes en 1644.
On peut remplacer les antennes par des bureaux de poste, des hˆ opitaux ou encore,
par des ´ ecoles. Dans ce dernier cas, on pourrait vouloir d´ efinir le bassin de chaque ´ ecole
d’une r´ egion de telle sorte que chaque enfant soit affect´ e ` a l’´ ecole la plus proche de son
domicile. Les diagrammes de Vorono¨ ı ont donc de tr` es nombreuses applications.
´
Enon¸ cons le probl` eme en termes math´ ematiques.
D´ efinition 15.15 Soit S = {P 1 , . . . , P n } un ensemble de points distincts d’une r´ egion
D ⊂ R
2 . Les points P i sont appel´ es sites.
1. Pour chaque site P i , la cellule de Vorono¨ ı de P i , not´ ee V (P i ), est l’ensemble des
points de D qui sont plus proches de P i que des autres sites P j (ou ´ egalement
proches) :
V (P i ) = {Q ∈ D, |P i Q| ≤ |P j Q|, j = i}.
2. Le diagramme de Vorono¨ ı de S, not´ e V (S), est la d´ ecomposition de D en cellules
de Vorono¨ ı.
Pour d´ ecider comment aborder le probl` eme, prenons le cas o` u D = R
2 et S = {P, Q},
P = Q.
Proposition 15.16 Soient P et Q deux points distincts du plan. La m´ ediatrice du
segment P Q est le lieu g´ eom´ etrique des points `
a ´ egale distance de P et de Q. C’est une
droite (D) perpendiculaire au segment P Q en son milieu. Tous les points R d’un cˆ ot´ e
de (D) satisfont ` a |P R| < |QR|, et ceux de l’autre cˆ ot´ e satisfont ` a |P R| > |QR|. Donc,
le diagramme de Vorono¨ ı de S est la partition de R
2 en deux demi-plans ferm´ es limit´ es
par (D) (figure 15.31).
Preuve La preuve est laiss´ ee en exercice.
Nous avons maintenant l’ingr´ edient de base pour trouver la cellule de Vorono¨ ı V (P i )
d’un point P i appartenant `
a un ensemble de sites S = {P 1 , . . . , P n }. Nous nous limiterons
au cas D = R
2 (figure 15.32).
Proposition 15.17 ´
Etant donn´ e un ensemble S = {P 1 , . . . , P n } de sites, pour chaque
paire de points (P i , P j ), la m´ ediatrice du segment P i P j divise le plan en deux demi-plans