15.10 Exercices
573
23. On se donne un polygone convexe `
a n cˆ ot´ es et un point P 1 ` a l’int´ erieur du polygone.
a) Donner un algorithme pour ajouter n autres points P 2 , . . . , P n+1 , de telle sorte
que le polygone devienne la seule cellule ferm´ ee du diagramme de Vorono¨ ı de
S = {P 1 , . . . , P n+1 } (voir la figure 15.32).
b) Donner un algorithme pour ajouter les n demi-droites qui compl` etent le diagramme de Vorono¨ ı de S.
24. Cet exercice porte sur la triangulation de Delaunay associ´ ee ` a un diagramme de
Vorono¨ ı et dont on rappelle la d´ efinition : les sommets des triangles sont les sites
de S, et on trace 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.
a) V´ erifier que, si dans le diagramme de Vorono¨ ı, on a au plus trois arˆ etes passant
par chaque sommet, alors la construction pr´ ec´ edente donne des triangles.
b) V´ erifier que chaque croisement P de trois arˆ etes dans le diagramme de Vorono¨ ı est le centre du cercle circonscrit ` a un triangle de la triangulation de Delaunay, dont les sommets sont les sites des trois cellules du diagramme de Vorono¨ ı qui
ont un sommet en P . (Cette question est une occasion de red´ emontrer que les
m´ ediatrices des trois cˆ ot´ es d’un triangle se coupent en un seul point.)
25. Mettre en ´ evidence un ensemble de sites S dont la figure 15.28 est le diagramme
de Vorono¨ ı et donner la triangulation de Delaunay associ´ ee.
26. Ici on consid` ere le probl` eme inverse de la d´ etermination du diagramme de Vorono¨ ı d’un ensemble de sites. ´
Etant donn´ e une partition du plan en cellules, on
se demande s’il existe un ensemble de sites S tel que ces cellules soient celles du
diagramme de Vorono¨ ı de S.
a) On commence par le cas de trois demi-droites (D 1 ), (D 2 ) et (D 3 ), comme sur la
figure 15.53a. On se demande s’il existe un ensemble de sites S = {A, B, C} tel que
ces demi-droites soient le diagramme de Vorono¨ ı de S. L’analyse est diff´ erente suivant
que le point d’intersection O des trois demi-droites est situ´ e ou non ` a l’int´ erieur
du triangle ABC. Montrer qu’une condition n´ ecessaire pour que O soit situ´ e ` a
l’int´ erieur du triangle ABC est donn´ ee par α, β, γ >
π
2 . Montrer que, si A, B et C
existent, alors les angles de la figure 15.53b ont les valeurs indiqu´ ees sur la figure.
b) Montrer que, si l’on choisit A dans l’angle form´ e par (D 1 ) et (D 2 ), alors
il existe B et C tels que (D 1 ), (D 2 ) et (D 3 ) sont le diagramme de Vorono¨ ı de
S = {A, B, C} si et seulement si A est sur une demi-droite issue de O faisant un
angle de π − γ avec (D 1 ) et de π − β avec (D 2 ).
c) On consid` ere maintenant la figure 15.54a pour le cas de trois demi-droites
telles que α <
π
2 et β, γ >
π
2 . Montrer que les diff´ erents angles prennent les
valeurs indiqu´ ees sur la figure 15.54b.
d) En conclure que, si on a une partition du plan en cellules comme sur la figure 15.55, il n’existe pas toujours d’ensemble de sites S = {A, B, C, D} tel que
ces cellules soient celles du diagramme de Vorono¨ ı de S.
e) Pouvez-vous d´ ecrire le cas interm´ ediaire α =
π
2 ?
573
23. On se donne un polygone convexe `
a n cˆ ot´ es et un point P 1 ` a l’int´ erieur du polygone.
a) Donner un algorithme pour ajouter n autres points P 2 , . . . , P n+1 , de telle sorte
que le polygone devienne la seule cellule ferm´ ee du diagramme de Vorono¨ ı de
S = {P 1 , . . . , P n+1 } (voir la figure 15.32).
b) Donner un algorithme pour ajouter les n demi-droites qui compl` etent le diagramme de Vorono¨ ı de S.
24. Cet exercice porte sur la triangulation de Delaunay associ´ ee ` a un diagramme de
Vorono¨ ı et dont on rappelle la d´ efinition : les sommets des triangles sont les sites
de S, et on trace 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.
a) V´ erifier que, si dans le diagramme de Vorono¨ ı, on a au plus trois arˆ etes passant
par chaque sommet, alors la construction pr´ ec´ edente donne des triangles.
b) V´ erifier que chaque croisement P de trois arˆ etes dans le diagramme de Vorono¨ ı est le centre du cercle circonscrit ` a un triangle de la triangulation de Delaunay, dont les sommets sont les sites des trois cellules du diagramme de Vorono¨ ı qui
ont un sommet en P . (Cette question est une occasion de red´ emontrer que les
m´ ediatrices des trois cˆ ot´ es d’un triangle se coupent en un seul point.)
25. Mettre en ´ evidence un ensemble de sites S dont la figure 15.28 est le diagramme
de Vorono¨ ı et donner la triangulation de Delaunay associ´ ee.
26. Ici on consid` ere le probl` eme inverse de la d´ etermination du diagramme de Vorono¨ ı d’un ensemble de sites. ´
Etant donn´ e une partition du plan en cellules, on
se demande s’il existe un ensemble de sites S tel que ces cellules soient celles du
diagramme de Vorono¨ ı de S.
a) On commence par le cas de trois demi-droites (D 1 ), (D 2 ) et (D 3 ), comme sur la
figure 15.53a. On se demande s’il existe un ensemble de sites S = {A, B, C} tel que
ces demi-droites soient le diagramme de Vorono¨ ı de S. L’analyse est diff´ erente suivant
que le point d’intersection O des trois demi-droites est situ´ e ou non ` a l’int´ erieur
du triangle ABC. Montrer qu’une condition n´ ecessaire pour que O soit situ´ e ` a
l’int´ erieur du triangle ABC est donn´ ee par α, β, γ >
π
2 . Montrer que, si A, B et C
existent, alors les angles de la figure 15.53b ont les valeurs indiqu´ ees sur la figure.
b) Montrer que, si l’on choisit A dans l’angle form´ e par (D 1 ) et (D 2 ), alors
il existe B et C tels que (D 1 ), (D 2 ) et (D 3 ) sont le diagramme de Vorono¨ ı de
S = {A, B, C} si et seulement si A est sur une demi-droite issue de O faisant un
angle de π − γ avec (D 1 ) et de π − β avec (D 2 ).
c) On consid` ere maintenant la figure 15.54a pour le cas de trois demi-droites
telles que α <
π
2 et β, γ >
π
2 . Montrer que les diff´ erents angles prennent les
valeurs indiqu´ ees sur la figure 15.54b.
d) En conclure que, si on a une partition du plan en cellules comme sur la figure 15.55, il n’existe pas toujours d’ensemble de sites S = {A, B, C, D} tel que
ces cellules soient celles du diagramme de Vorono¨ ı de S.
e) Pouvez-vous d´ ecrire le cas interm´ ediaire α =
π
2 ?