Chapitre 3

Triangulation

Une triangulation d’une région polygonale du plan est une décomposition de cette région
en triangles dont les sommets sont ceux du bord de la région. Une triangulation permet
souvent de résoudre plus facilement des problèmes portant sur la région qu’elle triangule.
Le problème du gardiennage d’une galerie d’art en est un bel exemple.
Au début du XXe siècle N. J. Lennes montre de manière constructive que tout polygone
simple admet une triangulation [Len11]. Cette construction fournit de fait un algorithme
de complexité quadratique en fonction du nombre de sommets. Du temps de l’émergence
de la géométrie algorithmique, Garey et al. (1978) ont proposé un algorithme de com-
plexité O(n log n) pour trianguler un polygone à n côtés. Après diverses améliorations
(cf. notes historiques du livre de [dBCvKO08]), Bernard Chazelle montre en 1991 qu’un
polygone simple peut être triangulé en temps linéaire. L’algorithme de Chazelle [Cha91]
est réputé très complexe. Une version plus simple et randomisée est décrite par Amato
et al. [AGR01].
Le problème de la triangulation de l’intérieur d’un polyèdre dans R3 est beaucoup plus
compliqué. Contrairement au cas bidimensionnel le nombre de tétraèdre d’une triangula-
tion d’un polyèdre (même convexe) à n sommets peut varier suivant la triangulation. De
plus, tous les polyèdres ne sont pas triangulables, à moins d’ajouter des sommets intérieurs
(dits de Steiner), comme le montre le cas du polyèdre de Schönhardt sur la figure 3.1. Ce
polyèdre est obtenu à partir d’un prisme de base triangulaire en tournant légèrement le
triangle supérieur par rapport au triangle inférieur. Du coup, les faces verticales du prisme
(des quadrilatères) ne sont plus planes et il faut ajouter une diagonale pour trianguler

Figure 3.1 – La face supérieure du prisme à base triangulaire de gauche est légèrement
pivotée pour obtenir le polyèdre de Schönhardt, à droite.

42
Notes Géométrie Algorithmique. December 3, 2014. Francis Lazarus. 43

chacun de ces quadrilatères gauches. En choisissant cette diagonale de manière à rendre

les quadrilatères ’concaves’, on vérifie que toute nouvelle arête entre deux sommets du
polyèdre est extérieure au polyèdre. Il n’est donc pas possible de trianguler son intérieur.
Références :
- Handbook of Discrete and Computational Geometry. Edited by Goodman and O’Rourke.
CRC Press 2004.

3.1 Existence
Définitions Une ligne polygonale de sommets (s1 , . . . , sn ) est la suite de segments
(s1 s2 , . . . , sn−1 sn ). Cette ligne polygonale est fermée si s1 = sn ; elle est simple si les
sommets sont deux à deux distincts et si les intérieurs de ses segments sont disjoints
des sommets et disjoints entre eux. Un polygone est une ligne polygonale simple et fer-
mée. On appelle arêtes les segments d’un polygone. Par le théorème de Jordan (version
polygonale), un polygone P sépare le plan en deux régions connexes appelées intérieur
et extérieur de P . Dans ce chapitre, on notera respectivement IntP et extP ces régions
(ce sont des ouverts du plan).
Une diagonale d’un polygone P est un segment dont l’intérieur relatif (i.e. le segment
privé de ses extrémités) est intérieur à P et dont les extrémités sont des sommets de
P . Une triangulation de P est un recouvrement de son intérieur (au sens large, i.e. de
IntP ) par des triangles d’intérieurs disjoints et dont les côtés sont soit des arêtes soit des
diagonales de P .

Lemme 3.1 Tout polygone ayant au moins 4 sommets admet une diagonale.

Preuve : Soit P un polygone et soit s le sommet de P de coordonnées minimales pour

l’ordre lexicographique (s est le sommet le plus bas parmi les sommets les plus à gauche).
Soit p le sommet précédant s et q le sommet suivant s pour l’ordre circulaire dans P .
– Si le triangle spq ne contient (au sens large) aucun sommet de P \ {s, p, q}, alors le
segment pq est une diagonale : aucune arête de P ne peut rencontrer l’intérieur ni le
bord de spq car l’une de ses extrémités serait contenue dans spq. Donc toute demi-droite
issue d’un point x intérieur au segment pq et passant par s ne rencontre P qu’une seule
fois (en s). Par le théorème de Jordan, et puisque la droite est extérieure à P à l’infini,
le point x est intérieur à P , i.e. pq est intérieur à P .
– Sinon, soit r un sommet de P intérieur au triangle spq et qui maximise la distance à la
droite pq. On vérifie aisément que le segment sr est une diagonale de P . (cf. figure 3.2).

Exercice 3.2 Compléter les détails manquant de la preuve précédente en indiquant en

particulier où intervient l’hypothèse sur le nombre minimal (4) de sommets.
Notes Géométrie Algorithmique. December 3, 2014. Francis Lazarus. 44

P
p

r
s
q

Figure 3.2 – Existence d’une diagonale dans un polygone.

Théorème 3.3 Tout polygone admet une triangulation.

Preuve : Soit P un polygone et soit D un ensemble de diagonales de P d’intérieurs

disjoints qui soit maximal pour l’inclusion. Toute région bornée du graphe plan P ∪
D est nécessairement un triangle ; dans la négative le lemme précédent contredirait la
maximalité de D. 2

On montre par récurrence sur n que toute triangulation d’un polygone à n sommets a
exactement n − 2 triangles et n − 3 diagonales.

Exercice 3.4 La preuve de Lennes pour l’existence d’une triangulation est proche de la
précédente quoique légèrement différente. Soit spq un triangle et soit R un ensemble de
points intérieurs à ce triangle. Montrer qu’il existe r ∈ R tel que rsp ∩ R = {r} (ici rsp
désigne le bord et l’intérieur du triangle). Compléter la preuve de Lennes.

3.2 Algorithmes
Si un polygone P est décrit sous forme d’une liste doublement chaînée de sommets, la
recherche d’une diagonale selon la preuve du lemme 3.1 prend un temps O(n), où n = |P |
est le nombre de sommets de P . On en déduit aisément un algorithme de triangulation
de complexité quadratique. Nous allons voir deux algorithmes plus efficaces.

Théorème 3.5 Il existe un algorithme qui triangule tout polygone à n sommets en temps
O(n log n) et espace O(n).

Nous proposons ci-dessous deux preuves – c’est-à-dire deux algorithmes – pour ce théorème.
Elles sont décrites dans les articles [Cha82, GJPT78].

3.2.1 Algorithme diviser pour régner

L’algorithme de Chazelle consiste à calculer en temps linéaire une diagonale du polygone
P qui coupe P en deux sous-polygones de tailles approximativement égales. En appliquant
Notes Géométrie Algorithmique. December 3, 2014. Francis Lazarus. 45

ce calcul de manière récursive à chacun des deux sous-polygones on obtient un algorithme

de triangulation de complexité O(|P | log |P |).
On supposera que P est décrit sous forme d’une liste cyclique doublement chaînée de
ses sommets dans l’ordre (cyclique) le long de P . Par la suite P désignera aussi bien
un polygone que sa liste doublement chaînée. On supposera également disposer de la
liste L doublement chaînée des sommets de P triés selon l’ordre lexicographique de leurs
coordonnées ainsi que de la liste V des paires d’arêtes de P verticalement visibles, i.e.
des paires d’arêtes pour lesquelles il existe un segment vertical intérieur à P et dont les
extrémités sont respectivement intérieures à chacune de ces deux arêtes. En considérant
la taille de la carte des trapèzes (cf. section 10.2), il est facile de voir que la liste V a une
taille linéaire en fonction de |P |.

Théorème 3.6 (du polygon cutting, Chazelle 1982) Soit P un polygone à n som-
mets et soient L et V les listes associées (respectivement des sommets triés selon l’ordre
lexicographique des coordonnées et des paires d’arêtes verticalement visibles). Il existe un
algorithme de complexité O(n) pour calculer une diagonale de P qui coupe P en deux
polygones P1 et P2 tels que
2
|P1 |, |P2 | ≤ d ne + 1.
3
De plus, les listes Pi , Li et Vi relatives à chacun des deux polygones pour i = 1, 2 peuvent
être calculées en temps O(n) également.

On montre dans un premier temps qu’il existe un segment vertical intérieur à P et qui le
coupe en deux polygones de tailles approximativement égales.

Lemme 3.7 Soit P un polygone à n sommets. Il existe un segment vertical pq (i.e.

xp = xq ) intérieur à P et intersectant P en ses deux extrémités p et q exactement de
sorte que les deux composantes de P \ {p, q} contiennent chacune au plus d 32 ne sommets
de P .

Preuve : On considère la décomposition trapézoïdale de P (cf. section 10.2). On sup-

pose dans un premier temps que P est en position générique, c’est à dire que tous les
sommets de P ont des abscisses distinctes. Il suit que chaque trapèze de la décomposition
intérieur à P est bordé par exactement un sommet de P sur sa gauche et un sommet de
P sur sa droite. Soit T le graphe plan obtenu en reliant par un segment chaque paire de
sommets incidents à un même trapèze (il y a donc un segment par trapèze). T est con-
nexe (utiliser par exemple la connexité du graphe d’adjacence des trapèzes) et acyclique
(utiliser l’acyclicité du graphe d’adjacence des trapèzes), i.e. que T est un arbre. De plus,
l’hypothèse de position générique montre que chaque sommet est incident à trois trapèzes
au plus et donc que le degré des sommets de T est au plus trois. La figure 3.3 illustre la
construction de T .
Remarquons qu’on peut associer à chaque arête a de T un segment vertical intérieur à P
et intersectant P en ses extrémités. Le nombre de sommets des deux lignes polygonales
de P coupées par ces extrémités est précisément le nombre de sommets de chaque sous
arbre de T − a. Le lemme suivant permet donc de conclure.
Notes Géométrie Algorithmique. December 3, 2014. Francis Lazarus. 46

T
p

Figure 3.3 – Le segment pq coupe le polygone en deux chaînes de tailles comparables.

Dans le cas non-générique, on perturbe les sommets en tournant de manière infinitésimale

le polygone afin de distinguer toutes les abscisses des sommets de P . Cette rotation
est elle-même simulée en considérant l’ordre lexicographique sur les paires (abscisses,
ordonnées) des coordonnées des sommets. 2

Lemme 3.8 Soit T un arbre à n sommets, n ≥ 2. On suppose que chaque sommet de T

est de degré au plus 3. Alors il existe une arête a de T telle que chaque composante de
T − a possède au plus d 2n
3
e sommets.

Preuve : Soit a une arête de T . Si une composante C de T − a est telle que |C| < b n3 c
alors il existe une arête b de T telle que
1. ou bien une composante K de T − b vérifie
n
|C| < |K| < b c
3
2. ou bien chaque composante de T − b est de taille au moins b n3 c.
En effet, soit C 0 la composante complémentaire de C dans T − a et x le sommet incident
à C 0 et a. Par les hypothèses sur T , x est de degré d ≤ 2 dans C 0 .
– On ne peut avoir d = 0 car dans ce cas on aurait |C 0 | = 1 > d 2n 3
e, en contradiction
avec n ≥ 2.
– Si d = 1, on choisit pour b l’unique arête incidente x dans C 0 . Alors T − b a une
composante K (de fait C + a) de taille |C| + 1. On se retrouve alors dans le cas 1 ou 2
ci-dessus selon que |C| + 1 est respectivement strictement inférieur ou égal à b n3 c.
– Sinon d = 2. Soient a1 , a2 les deux arêtes incidentes à x dans C 0 et soit C1 (resp. C2 )
la composante de C 0 − a1 (resp. de C 0 − a2 ) qui n’est pas incidente à x. Si |C1 | > d 2n 3
e
alors on se retrouve dans le cas 1 en choisissant b = a1 (et K = C + a + C2 ). De
même en choisissant b = a2 si |C2 | > d 2n 3
e. On peut donc supposer |C1 | ≤ d 2n 3
e et
|C2 | ≤ d 3 e. Puisqu’on ne peut avoir à la fois |C1 | < b 3 c et |C2 | < b 3 c, on a |C1 | ≥ b n3 c
2n n n

ou |C2 | ≥ b n3 c. On se retrouve dans le cas 2 en choisissant b = a1 dans le premier cas

et b = a2 dans le second cas.
La preuve du lemme est alors terminée par récurrence sur |C|. 2

Preuve du théorème 3.6 : On sait d’après le lemme 3.7 qu’il existe une verticale dont
les extrémités coupent P en deux lignes polygonales contenant chacune au plus d 2n 3
e
sommets. En parcourant la liste V des paires d’arêtes verticalement visibles on trouvera
Notes Géométrie Algorithmique. December 3, 2014. Francis Lazarus. 47

a
Pc Pd Q0
c Q Cd0
d

Cc0
b

Figure 3.4 – (Gauche) Le polygone P est coupé en deux chaînes Pc et Pd par la paire
(a, b) de segments visibles. (Droite) Une triangulation de la zone Q0 bordée par a, b, Cc0
et Cd0 .

donc nécessairement une paire (a, b) telle que tout segment vertical de visibilité entre les
deux arêtes a et b coupe P comme ci-dessus. Fixons un sommet s de P et indexons les
sommets de P de 0 à n − 1 dans l’ordre direct le long de P à partir de s. À partir de ces
indices on peut calculer en temps constant la longueur de la ligne polygonale entre deux
sommets d’indices i et j : en incluant les deux sommets et en considérant la ligne de i
vers j dans le sens direct, cette longueur vaut j − i + 1 si j ≥ i et n − j + i − 1 sinon. On
peut donc tester en temps constant si une paire d’arêtes convient et de ce fait déterminer
(a, b) en temps linéaire.
Il n’est en général pas possible de relier deux des extrémités de a et de b par une diagonale
car celle-ci peut recouper P . Considérons le quadrilatère Q formé par a, b et les deux
segments c et d reliant les extrémités de a et b situés d’un même côté d’une “verticale
de visibilité” entre a et b. Le quadrilatère Q forme bien un polygone (simple) de par
l’existence d’un segment de visibilité qui sépare c et d. Soit Pc (resp. Pd ) la sous-ligne
polygonale de P bordés par les extrémités de c (resp. de d) et ne contenant ni a ni b.
L’objectif est de calculer une diagonale entre un sommet de Pc intérieur à Q et un sommet
de Pd intérieur à Q de sorte que cette diagonale sépare P comme voulu. Pour cela on
considère l’ensemble Sc et Sd des composantes de P ∩ IntQ qui s’appuient respectivement
sur c et d. On pose Cc = Conv(Sc ) et Cd = Conv(Sd ) (voir figure 3.4, gauche).
Affirmation I : Cc et Cd sont disjointes. De plus, les sommets de Cc (resp. de Cd ) sont
les sommets de Pc (resp. de Pd ).

Preuve de l’affirmation I : Par hypothèse, il est facile de voir – à l’aide du théorème

de Jordan – que Sc et Sd sont séparées dans Q par un segment vertical. Il en est donc de
même de leurs enveloppes convexes. Par ailleurs, toujours à l’aide du théorème de Jordan,
on montre que toute région bordée par une composante de Sc ∩ Pd et un segment de c
est contenue dans une région bordée par une composante de Sc ∩ Pc et un segment de c.
On en déduit que Cc = Conv(Sc ∩ Pc ). Donc Cc est l’enveloppe convexe des sommets de
Sc ∩ Pc qui comprend les sommets de Pc inclus dans Sc et les extrémités des composantes
de Sc . Or ces sommets sont tous sur c donc dans l’enveloppe convexe des extrémités de c
(ce sont des sommets de Pc ). Un raisonnement analogue montre que les sommets de Cd
sont des sommets de Pd . 2
Notes Géométrie Algorithmique. December 3, 2014. Francis Lazarus. 48

L’affirmation précédente permet de sélectionner en temps O(n) un sous-ensemble A des

sommets de P tel que Cc = Conv(A) : il suffit de parcourir Pc et de retenir les sommets
de Pc compris entre deux intersections successives de Pc avec c, lorsque Pc entre dans
Q à la première intersection. On peut extraire de L la sous-liste LA , triée selon l’ordre
lexicographique des coordonnées, des sommets de A. On obtient finalement Cc en temps
linéaire à partir de LA par l’algorithme classique de balayage 8.1.2. 1 De manière analogue
on calcule Cd en temps linéaire.
On considère maintenant le polygone Q0 formé des arêtes a et b et des deux chaînes
concaves Cc0 = Cc − c et Cd0 = Cd − d. Notons que Q0 est bien une ligne polygonale simple
d’après l’affirmation I. Notre but est de montrer que dans toute triangulation T de Q0
l’une des arêtes de T fournit une diagonale qui sépare P comme voulu. On remarque
tout d’abord que tout triangle de T contient nécessairement une arête de Cc0 ou bien de
Cd0 . En effet, Cc0 et Cd0 étant concaves, un tel triangle ne peut avoir deux sommets non
adjacents sur une même de ces deux chaînes (cf. figure 3.4, droite). Le dual de T est
donc une chaîne simple, ce qui permet d’ordonner les diagonales de T de la première,
incidente au même triangle que a, à la dernière, incidente au même triangle que b. On
note δ1 , δ2 , . . . δk ces diagonales, on pose δk+1 = b et pour i = 1, . . . , k − 1, on note γi la
troisième arête du triangle de T bordé par δi et δi+1 . Donc γi est une arête de Cc0 ou de
Cd0 et on note Γi la sous-chaîne de respectivement Pc ou Pd joignant les extrémités de
γi . Pour chaque diagonale δi de T , on note enfin ∆i la sous-chaîne de P contenant a et
joignant les extrémités de δi .
Affirmation II : Une des arêtes de T (soit une diagonale soit une arête de Q0 ) est une
diagonale de P qui coupe P en deux lignes polygonales (extrémités incluses) de taille au
plus d 32 ne + 1.

Preuve de l’affirmation II : Supposons qu’une arête γi de Cc0 ou de Cd0 ne soit pas une
arête de P (et soit donc une diagonale de P ) et que
n
|Γi | ≥ b c + 1.
3
On a alors, en notant Γ0i l’autre chaîne de P joignant les extrémités de γi
– d’une part : |Γi | ≤ max{|Pc |, |Pd |} ≤ d 2n
3
e,
– d’autre part : |Γi | + |Γ0i | = n + 2, d’où |Γ0i | ≤ d 32 ne + 1.
L’affirmation est donc vérifiée en choisissant γi comme diagonale de P .
Supposons maintenant à l’inverse que pour toute arête γi de Cc0 ou de Cd0 on ait
n
|Γi | ≤ b c.
3
On a en particulier
n
|∆1 | = |Γ1 + a| ≤ b c + 1.
3
1. Chazelle utilise un autre argument. Il extrait de Sc une ligne polygonale simple joignant les ex-
trémités de c et dont l’enveloppe convexe est Cc Cette ligne est constituée de composantes de Sc et de
segments de c. Il utilise ensuite l’algorithme de complexité linéaire pour calculer l’enveloppe convexe
d’une ligne polygonale simple.
Notes Géométrie Algorithmique. December 3, 2014. Francis Lazarus. 49

Par ailleurs si pour un certain i ∈ [1, k] on a |∆i | ≤ b n3 c alors δi n’est pas la dernière
diagonale de T (i.e. i < k) et
2
|∆i | < |∆i+1 | ≤ d ne + 1.
3
En effet, on a
n
|∆i+1 | = |∆i + Γi | = |∆i | + |Γi | − 1 ≤ 2b c − 1.
3
Alors que |∆k | ≥ d 23 ne + 1 (faire un raisonnement analogue à la majoration de |∆1 |). On
conclut par récurrence sur k que l’une au moins des diagonales δi vérifie
n 2
b c + 1 ≤ |∆i | ≤ d ne + 1.
3 3
Ceci permet également de confirmer l’affirmation en choisissant δi comme diagonale de
P. 2

Affirmation III : Q0 peut être triangulé en temps linéaire.

Preuve de l’affirmation III : D’après la preuve de l’affirmation II, on peut trianguler

Q0 de manière incrémentale en calculant chaque diagonale δi+1 en fonction de la diagonale
δi calculée précédemment : en notant pc et pd les extrémités de δi et pc qc et pd qd les arêtes
de Q0 respectivement incidentes à pc et pd et “au dessus” de δi , alors on a soit δi+1 = pc qd
soit δi+1 = pd qc . Il suffit de tester si qd (resp. pc ) est au dessous de la droite pc qc (resp.
pd qd ) pour savoir si pc qd (resp. pd qc ) est une diagonale. Il se peut que les deux le soient,
auquel cas l’une ou l’autre convient puisque dans les deux cas on se retrouve dans une
configuration où la partie de Q0 au dessus de δi+1 est constituée de deux chaînes concaves
reliées par deux segments, ce qui permet d’appliquer la récurrence. 2

La conjonction des affirmations II et III permet de conclure la première partie du théorème.

Il reste à vérifier, en appelant P1 et P2 les deux polygones coupés par la diagonale δ trou-
vée, que les listes Pi , Li et Vi relatives au polygone Pi pour i = 1, 2 peuvent être calculées
en temps O(n) également. C’est clair pour les listes Pi et Li (ces listes contiennent plus
précisément des pointeurs bidirectionnels sur un tableau des sommets fixé une fois pour
toute. On peut associer à chacun des sommets du tableau un drapeau qui permet de
sélectionner dans une première passe les sommets qui nous intéressent). Pour la liste Vi
il suffit de remarquer qu’elle est constituée d’une part des paires d’arêtes de V qui sont
dans Pi et d’autre part des paires (a, δ) pour chaque paire (a, b) de V dont la visibilité
est obstruée par δ et telle que a est une arête de Pi (et donc b n’est pas une arête de Pi ).
En parcourant V , on peut ainsi construire Vi de la manière suivante. Pour chaque paire
(a, b) de V :
1. si a ∈ Pi et b ∈ Pi , alors on place (a, b) dans Vi ,
2. sinon, si a et b ne sont pas dans le même polygone, disons a ∈ Pi , b 6∈ Pi , et si les
projections verticales sur l’axe des abscisses des arêtes a, b et δ ont une intersection
non vide, alors on place (a, δ) dans Vi après avoir vérifié que cette paire n’était pas
déjà présente dans Vi . Cette dernière vérification s’obtient en temps constant en
marquant au fur et à mesure les arêtes a de P telles que (a, δ) est dans Vi .
Notes Géométrie Algorithmique. December 3, 2014. Francis Lazarus. 50

Preuve du théorème 3.5 : Soit P donc un polygone à n sommets. L’algorithme con-

siste à appliquer récursivement le théorème du polygon cutting : la triangulation de P
est l’union des triangulations des polygones P1 et P2 obtenus par le théorème 3.6.
Pour initialiser l’algorithme il faut construire la liste L des sommets de P triés selon
l’ordre lexicographique de leurs coordonnées ; ce qui prend un temps O(n log n) et une
place linéaire suivant tout algorithme de tri standard. Il faut construire également la liste
V des paires d’arêtes de P verticalement visibles que l’on obtient en temps linéaire en
parcourant la carte des trapèzes de P (cf. section 10.2). Cette carte a elle-même une
taille linéaire (lemme 10.2) et peut être construite en temps O(n log n) par un algorithme
randomisé (cf. section 10.2) ou non (cf. section 10.1).
Soit C(n) la complexité maximale de la triangulation de tout polygone de taille n. On
peut écrire
C(n) ≤ kn + max {C(n1 ) + C(n2 )}
n1 +n2 =n+2
n1 ,n2 ≤d 32 ne+1

pour un certain k > 0. Montrons que C(n) = O(n log n). Soit α tel que 2/3 < α < 1.
Choisissons N assez grand pour que n > N =⇒ d 32 ne + 1 < αn et n2 log α1 > 2 log n.
Choisissons ensuite K suffisamment grand pour que n ≤ N =⇒ C(n) ≤ Kn log n et
pour que K log α1 > 2k.
Pour n ≤ N on a donc par hypothèse C(n) ≤ Kn log n. Supposons par récurrence
C(m) ≤ Km log m pour m inférieur à un certain n > N . Pour n1 , n2 ≤ d 32 ne + 1 tels que
n1 + n2 = n + 2 on a

kn + C(n1 ) + C(n2 ) ≤ kn + Kn1 log n1 + Kn2 log n2 ≤ kn + K(n + 2) log(αn)

1
≤ Kn log n + 2K log n + (k − K log )n
α
n 1
≤ Kn log n + K(2 log n − log ) ≤ Kn log n
2 α

Ce qui permet de conclure C(n) ≤ Kn log n. 2

3.2.2 Algorithme par décomposition en polygones monotones

L’algorithme de triangulation de Garey et al. se compose de deux étapes. Dans un premier
temps le polygone à trianguler est décomposé en polygones plus simples appelés polygones
monotones. Cette étape prend un temps O(n log n). Ces polygones monotones sont ensuite
triangulés en temps linéaire selon une technique appropriée. Au total on obtient donc une
complexité équivalente à l’algorithme diviser pour régner de Chazelle.

Polygones monotones

Définition 3.9 On considère une direction du plan qu’on appelle verticale. La direction
orthogonale est dite horizontale. La hauteur d’un point est sa projection horizontale sur
Notes Géométrie Algorithmique. December 3, 2014. Francis Lazarus. 51

q u

p
A B C t

Figure 3.5 – (A) Une ligne polygonale non monotone. (B) Une ligne polygonale stricte-
ment monotone. (C) Un polygone monotone, mais pas strictement. Les sommets p q sont
des extrema stricts, r et s sont des extrema non stricts, t est un minimum strict et u n’est
pas un extremum. Les sommets p, r et u sont réflexes.

la verticale. Une ligne polygonale L est dite (strictement) monotone si la hauteur de la

séquence des sommets de L est (strictement) monotone. Dit autrement L est monotone si
toute droite horizontale intersecte L en au plus une composante, réduite à un point dans
le cas strict.
Un polygone P est dit (strictement) monotone s’il est la réunion de deux lignes polygonales
(strictement) monotones ayant seulement leurs extrémités en commun. Dit autrement un
polygone P est monotone (resp. strictement monotone) si toute droite horizontale coupe
P en au plus deux composantes (resp. au plus deux points).
Un sommet intérieur (i.e. qui n’est pas une extrémité) à une ligne polygonale ou à un
polygone est dit maximum, (resp. minimum) (strict) si ces deux sommets voisins sont
(strictement) en dessous (resp. au dessus) de la droite horizontale passant par ce sommet.
On appelle extremum (strict) un sommet qui est soit maximum (strict) soit minimum
(strict). La figure 3.5 illustre les différentes définition.

On vérifie aisément qu’un sommet n’est pas un extremum si et seulement si sa hauteur

est strictement comprise entre celles de ses deux sommets voisins. Par suite :

Lemme 3.10
– une ligne polygonale ayant au moins 3 sommets est strictement monotone si et seule-
ment si aucun de ses sommets intérieurs n’est extremum.
– Un polygone est strictement monotone si et seulement si il a exactement deux extrema.

Définition 3.11 Un sommet d’un polygone est dit réflexe si l’angle intérieur au polygone
formé par les deux arêtes incidentes au sommet est strictement plus grand que π. Une
sous-chaîne d’un polygone est dite concave si ses sommets intérieurs sont réflexes.

Lemme 3.12 Un polygone sans extremum réflexe est monotone.

Preuve : Soit P un polygone sans extremum réflexe. Soient p et q des sommets de P de

hauteur respectivement minimale et maximale. Les sommets p et q coupent P en deux
Notes Géométrie Algorithmique. December 3, 2014. Francis Lazarus. 52

q C q
h+ x ~h
b
C a
PD Cb q
h w=v p v
u v p
D
−
h PG y
q
A p B C

Figure 3.6 – (A) Le polygone P est supposé sans extremum réflexe (B) Une composante
C de PG ∩ h+ . (C) L’extrémité v de C sépare C de q le long de PG ; le sommet y est un
minimum réflexe.

lignes polygonales PG et PD telles que PG est à gauche de PL . Supposons par l’absurde que
P n’est pas monotone. Alors par définition, PG ou PD n’est pas monotone. On suppose
sans perte de généralité que PG n’est pas monotone. Il existe donc une droite horizontale
h coupant PG en deux composantes au moins. On note h+ et h− les demi-plans ouverts
respectivement au dessus et au dessous de h. Par connexité de PG , l’une des composantes,
C, de h+ ∩ PG ou de h− ∩ PG a ses deux extrémités dans h. On note u et v ces deux
extrémités avec u à gauche de v. Supposons à nouveau sans perte de généralité C ⊂ h+
comme sur la figure 3.6.A.
J’affirme que
(A) le long de C, l’intérieur de P est situé du même côté que l’intérieur du polygone
délimité par C et le segment uv de h.
Par ailleurs, puisque PG est à gauche de PD , l’intérieur de P est à droite de PG lorsque
PG est parcourue du bas vers le haut (i.e. de p vers q). Par conséquent, en admettant
(A), le sommet u est avant v dans ce parcours. Soit D la composante de PG \ C joignant
v à q. J’affirme que
(B) le sommet le plus à gauche parmi les sommets de hauteur minimale de D est extremum
réflexe (cf. figure 3.6.C).
Cette dernière contradiction permet de conclure la monotonicité de PG et donc de P . Il
reste à montrer les affirmations (A) et (B).
Pour (A), on considère le sommet x de C le plus à droite parmi les sommets de hauteur
maximale. Les directions des deux arêtes d’origine x et la direction horizontale ~h vers la
droite sont donc deux à deux distinctes. Soit a l’arête issue de x dont la direction suit celle
de ~h dans le sens indirect (le sens des aiguilles d’une montre). On note b la seconde arête
issue de x. Comme x est extremum, il ne peut être réflexe, ce qui montre que l’intérieur
de P est entre b et a dans le sens direct, ou encore à droite de a. Montrons que c’est
également le cas pour l’intérieur de la courbe de Jordan uv ∪ C. Pour cela, on note Ca et
Cb les deux composantes de C \{x} contenant respectivement a et b et on note w ∈ {u, v}
l’extrémité de Ca autre que x (cf. figure 3.6.B). Il est clair qu’on ne peut avoir w = u,
Notes Géométrie Algorithmique. December 3, 2014. Francis Lazarus. 53

Figure 3.7 – Le polygone P est décomposé en polygones monotones par ajout de diag-
onales incidentes à ses extrema réflexes.

sinon la courbe simple S formée de Ca , de la demi-droite horizontale à droite de x et de la

demi-droite horizontale à gauche de w formerait une courbe de Jordan qui ne rencontre
pas Cb . Or l’intérieur de b est au dessus de S et l’extrémité v de Cb est au dessous de
S, ce qui contredit la connexité de Cb . Donc w = v. Comme l’intérieur de uv ∪ C est au
dessus et donc à droite de vu, il en est de même pour Ca , i.e. l’intérieur de uv ∪ C est à
droite de a.
Un raisonnement analogue permet de montrer que le sommet spécifié dans (B) qui est
évidemment extremum est également réflexe. 2

Décomposition en polygones monotones

Théorème 3.13 Il existe un algorithme de complexité O(n log n) pour décomposer tout
polygone à n sommets, par l’ajout de diagonales au polygone, en polygones monotones .

Preuve : Considérons la décomposition trapézoïdale d’un polygone P obtenue par cloi-

sonnement horizontal (cf. section 10.2). On suppose le polygone en position générale, i.e.
deux sommets distincts ont des ordonnées distinctes. Chaque trapèze intérieur à P est
donc incident à exactement deux sommets de P , un sommet supérieur sur le côté hor-
izontal supérieur du trapèze et un sommet inférieur sur le côté horizontal inférieur du
trapèze. On ajoute une diagonale joignant ces deux sommets si le sommet supérieur est
un minimum réflexe ou si le sommet inférieur est un maximum réflexe. On obtient ainsi
une décomposition de P en sous-polygones comme sur la figure 3.7. Aucun sous-polygone
de la décomposition ne peut avoir d’extremum réflexe : un sommet p qui serait extremum
réflexe dans un sous-polygone le serait nécessairement dans P ; mais les règles d’ajout
de diagonales font que p n’est plus extremum dans aucun des sous-polygones incidents.
Il suit du lemme 3.12 que ces polygones sont tous monotones. Le cas non générique
où plusieurs sommets peuvent posséder une même ordonnée se traite en simulant une
rotation infinitésimale en considérant l’ordre lexicographique sur les paires (ordonnée,
abscisse).
Notes Géométrie Algorithmique. December 3, 2014. Francis Lazarus. 54

Notons que la décomposition trapézoïdale peut s’obtenir en temps O(n log n) et que
l’ajout de chaque diagonale s’obtient en temps constant par diagonale (en utilisant une
structure de carte planaire en demi-arêtes), ce qui achève la démonstration. 2

Exercice 3.14 Décrire un algorithme de complexité O(n log n) pour la décomposition

d’un polygone P en polygones monotones qui n’utilise pas à proprement parler la décom-
position trapézoïdale de P , mais seulement un balayage des sommets de P .

Triangulation des polygones monotones

Théorème 3.15 Il existe un algorithme de complexité linéaire pour trianguler un poly-

gone monotone.

Preuve : Soit P un polygone strictement monotone. En temps linéaire on peut couper

P en deux chaînes monotones. Les sommets sur chaque chaîne sont naturellement triés
selon leur ordonnée. La fusion (en temps linéaire) de ces deux listes permet d’obtenir la
liste V des sommets de P triés selon leur ordonnée. On effectue un balayage des sommets
de haut en bas. Au cours du balayage une partie de l’intérieur de P est triangulée et
une autre Pi forme un polygone strictement monotone que l’on doit trianguler. Soit σi
le sommet maximum de Pi et soient Gi et Di les deux chaînes monotones maximales de
Pi . On stocke les sommets balayés dans une pile Π de manière à conserver l’invariant
suivant : (i) les sommets dans Π forment une sous-chaîne concave de sommets réflexes de
Pi issue de σi et (ii) le sommet σi est également incident dans Pi à un sommet νi plus bas
que les sommets de Π. En particulier, si les sommets de Π sont dans Gi (resp. Di ) alors
νi est dans Di (resp. Gi ). Au départ Π est initialisée avec les deux premiers sommets de
V (i.e. le sommet maximal de P0 = P et le sommet juste au dessous).
Soit s le nouveau sommet balayé dans la liste V .
1. Si s forme une chaîne concave avec Π (i.e. le dernier sommet de Π est réflexe) alors
on empile s. Les invariants (i) et (ii) sont maintenus.
2. Si s = νi et si s n’est pas le sommet minimal de P alors on relie s par des segments
à chacun des sommets de Π, hormis σi (qui est déjà relié à s). Notons que ces
segments sont des diagonales de Pi (et donc de P ) car aucune arête entre deux
sommets de Π ne peut couper une telle diagonale (par concavité de Π) ni aucune
autre arête de Pi par monotonie de Π. On a ainsi triangulé une partie supérieure
de Pi . Le reste constitue le polygone Pi+1 . On vide ensuite Π et on ré-insert son
dernier sommet, qui devient le sommet σi+1 , puis le sommet s ; ces deux sommets
formant les deux plus hauts sommets de Pi+1 . On définit également νi+1 comme le
sommet suivant Π le long de Pi . Clairement les invariants (i) et (ii) sont rétablis.
3. Si s est incident au dernier sommet s` de Π mais ne forme pas une chaîne concave
avec Π (i.e. s` est convexe dans Pi ) alors on relie s par des segments aux derniers
sommets sk , sk+1 , . . . , s`−1 de Π, hormis le tout dernier s` auquel il est déjà relié, de
sorte que la droite ssk est support pour Π (i.e. les sommets de Π sont d’un même
côté de cette droite) mais que la droite ssk+1 ne l’est pas. À nouveau ces segments
sont des diagonales de Pi car aucune des deux chaînes Gi et Di ne peut recouper
Notes Géométrie Algorithmique. December 3, 2014. Francis Lazarus. 55

σ0 σ0 σ0
Π Π
Π σ1 Π σ1
ν0 ν0 ν0

P0 P1 P1
ν1 ν1

a b c d e

σ2 = σ1
Π Π Π Π

P2
ν2 = ν1 ν2 ν2 ν2

e f g h i

Figure 3.8 – (a-i) Triangulation par balayage vertical des sommets de P = P0 . On

retrouve la situation 1 aux étapes a,b,f, la situation 2 aux étapes c, h, i et la situation 3
aux étapes e et g.

le segment ssk du fait de leur monotonie. On a ainsi triangulé une partie de Pi .

Le reste constitue le polygone Pi+1 . On dépile alors les sommets sk+1 , . . . , s` de Π
et insert le sommet s. Le fait que la droite ssk soit support de Π montre que Π
contient bien une chaîne concave et que les invariants (i) et (ii) sont rétablis.
Lorsqu’on balaye le sommet minimal de P on se retrouve dans la situation 2 ci-dessus et
la triangulation qui suit achève la triangulation de P . La figure 3.8 résume les différentes
étapes sur un exemple. Pour chaque sommet balayé les opérations effectuées ci-dessus se
décomposent dans chacun des trois cas en un nombre constant d’opérations élémentaires
auquel s’ajoute un nombre d’opérations proportionnel au nombre de diagonales ajoutées
à la triangulation. Comme il y a un nombre linéaire de diagonales et que l’on balaye un
nombre linéaire de sommets, le coût total de la triangulation est linéaire. 2

3.2.3 Application au problème de la galerie d’art

Le problème communément attribué à Victor Klee en 1973 est le suivant : étant donné
une galerie d’art dont le sol a la forme d’un polygone, combien de gardiens (ou caméras)
fixes suffisent à garder la galerie ? On sous-entend que chaque gardien peut regarder dans
toutes les directions autour de lui.
Notes Géométrie Algorithmique. December 3, 2014. Francis Lazarus. 56

De manière plus géométrique, soit P un polygone du plan et x ∈ IntP un point intérieur

(au sens large) à P . La zone de visibilité de x dans P est l’ensemble des points intérieurs
à P et visibles depuis x dans P . C’est encore

VP (x) = {y ∈ IntP | xy ⊂ IntP }

où xy dénote le segment joignant x et y. Un ensemble X ⊂ P couvre P si

P = ∪x∈X VP (x)

i.e. si l’union des zones de visibilités des points de X recouvre P . Le problème de la galerie
d’art revient donc à chercher un ensemble X de taille minimale couvrant P . Le problème
de Klee était plus précisément de trouver la taille minimale g(n) telle que tout polygone
à n sommets est couvert par un ensemble de taille g(n).

Théorème 3.16 (de la galerie d’art, Chvátal 1973)

g(n) = bn/3c.

La preuve suivante due à Fisk en 1978 utilise la notion de coloriage. Un coloriage d’un
ensemble E par une ensemble C est une application de E dans C. Si le cardinal de C est
k on parle d’un k-coloriage de E.

Preuve du théorème : g(n) ≤ bn/3c : soit P un polygone à n sommets et T une

triangulation de P . L’algorithme suivant construit un 3-coloriage des sommets de P tel
que tout triangle de T est tricolore (ses trois sommets ont des couleurs 2 à 2 distinctes) :
Choisir une arête a de P et colorier ses deux sommets, l’un en bleu et l’autre en blanc.
Cette arête est incidente à un unique triangle de T , ce qui détermine la couleur de son
troisième sommet, disons rouge. Si l’arête (rouge, blanc) de ce triangle est une diagonale,
colorier récursivement la partie de P coupée par cette diagonale et ne contenant pas a.
Faire de même avec l’arête (rouge, bleu).
Remarquons alors que l’ensemble des sommets de P ayant la couleur la moins fréquente
dans un tel 3-coloriage est de cardinal au plus bn/3c et couvre P , puisque couvre tout
triangle de T .
g(n) ≥ bn/3c : Pour tout k, on construit un polygone en forme de peigne de taille
3k, ayant k dents, qui ne peut être couvert par moins de k points. Considérons pour
cela un triangle t ayant un côté horizontal de longueur 1 et k copies t1 , t2 , . . . , tk de t
successivement translatées horizontalement de 2 unités. Ces copies sont donc disjointes
et forment les dents du peigne. On considère également un trapèze dont les bases sont
horizontales : l’une joint un sommet du côté horizontal de t1 avec un sommet du côté
horizontal de tk et l’autre joint un point intérieur à un côté non horizontal de t1 avec un
point intérieur à un côté non horizontal de tk . Notre peigne est le bord de l’union de ce
trapèze avec les k triangles t1 , t2 , . . . , tk . Puisque les triangles sont disjoints, aucun point
du peigne ne peut couvrir simultanément les deux pointes de deux dents du peigne. Il
faut donc au minimum k points pour couvrir le peigne. 2
Notes Géométrie Algorithmique. December 3, 2014. Francis Lazarus. 57

L’algorithme de coloriage de la preuve du théorème est clairement de complexité linéaire.

Compte tenu de l’existence d’un algorithme de triangulation de complexité linéaire [Cha91],
ceci permet de trouver en temps linéaire, pour un polygone donné, un ensemble couvrant
de taille minimale dans le cas le pire. Par contraste, trouver la taille minimale de tout
ensemble couvrant pour un polygone précis est un problème NP-difficile [Agg84].
Références :
- [Link]
- [Link]
- On pourra consulter l’État de l’art
Art Gallery and Illumination Problems. J. Urratia. Chap. 22 in “Handbook of Computa-
tional Geometry”. Edited by J. R. Sack and J. Urrutia