Sur le diagramme de Voronoi et la triangulation de Delaunay d’un

ensemble de points dans un revêtement du plan euclidien

Vincent Pilaud

Septembre 2006

Introduction
Il y aurait de nombreuses façons de présenter mon domaine de recherche, la géométrie discrète et algorithmique,
et plus précisément mon travail de recherche actuel effectué sous la direction de Michel Pocchiola (Département d’In-
formatique de l’École Normale Supérieure) et de Francisco Santos (Département de Mathématiques et d’Informatique
de l’Université de Cantabrie). J’ai choisi de présenter ici l’exemple de l’étude des diagrammes de Voronoi et des
triangulations de Delaunay dans des revêtements particuliers de l’espace euclidien.
Ce choix me permet de situer mon exposé à différents niveaux : je présente d’une part des résultats classiques et
des méthodes générales de géométrie discrète et algorithmique (§ 1) ; j’expose d’autre part des résultats obtenus lors
de mon stage du Master Parisien de Recherche Informatique (§ 2,3) ; enfin, je présente certaines questions qui restent
à étudier par la suite. Ainsi, la première partie présente le domaine de ma recherche, tandis que la suite présente le
cadre plus précis de mon travail.
J’estime par ailleurs que le sujet des diagrammes de Voronoi et des triangulations de Delaunay présente simul-
tanément l’aspect combinatoire et l’aspect algorithmique qui sont étudiés dans ce domaine. Ces deux aspects seront
présents dans mon projet de recherche : je travaille avec Michel Pocchiola sur certains aspects algorithmiques dans
les revêtements de l’espace euclidien qui n’ont pas encore été résolus (calcul de l’enveloppe convexe, énumération des
pseudo-triangulations,...) tandis que le sujet du stage que j’effectue avec Francisco Santos est plus combinatoire.
Enfin, le sujet des diagrammes de Voronoi et des triangulations de Delaunay me permet de faire le lien avec ma
formation d’enseignant puisque j’ai présenté certains des résultats qui suivent lors de la préparation à l’agrégation
l’année dernière.

Table des matières

Introduction 1

1 Diagramme de Voronoi et triangulation de Delaunay dans Rm 2

1.1 Généralités . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2
1.2 Linéarisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.3 Calcul dans le plan . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
1.4 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

2 Revêtements 8
2.1 Définition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.2 Motivations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9

3 Diagrammes de Voronoi et triangulation de Delaunay dans les revêtements 10

3.1 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10
3.2 Linéarisation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
3.3 Cônes d’influence et algorithme de balayage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

Conclusion 15

Bibliographie 15

1
1 Diagramme de Voronoi et triangulation de Delaunay dans Rm
Le diagramme de Voronoi d’un ensemble S de n points de Rm est une partition de l’espace en n cellules représentant
les zones d’influence des points de S : la cellule de Voronoi d’un point x de S est constituée de l’ensemble des points
plus proches de x que de tout autre point de S. La triangulation de Delaunay de S est l’unique triangulation de S
dont tout simplexe admet une boule circonscrite qui ne contient aucun point de S (à part les sommets du simplexe).
Ces deux objets, duaux l’un de l’autre, peuvent être linéarisés en augmentant la dimension de l’espace : ainsi, le
diagramme de Voronoi et la triangulation de Delaunay de S sont des projections de polytopes de Rm+1 (§ 1.2). Les
diagrammes de Voronoi et les triangulations de Delaunay dans Rm héritent donc des propriétés combinatoires des
polytopes de Rm+1 . On obtient en particulier une borne sur la complexité d’un diagramme de Voronoi par le théorème
de la borne supérieure (§ 1.2).
On présente ensuite (§ 1.3) un algorithme de calcul du diagramme de Voronoi de n points du plan par une méthode
de balayage effectuée en temps O(n ln n). On renvoie à [Fort, 1997] pour un algorithme incrémental de calcul de la
triangulation de Delaunay en temps O(n ln n).
Enfin, on note que ces objets apparaissent fréquemment en géométrie discrète et algorithmique : on présente ici
(§ 1.4) des applications de ces objets au problème du bureau de poste et au calcul d’arbres couvrants minimaux.
Pour d’autres exemples d’applications des diagrammes de Voronoi classiques, on renvoie à [Edel, 1987]. Pour des
généralisations des diagrammes de Voronoi (diagrammes de Voronoi d’ordre supérieur, diagramme de puissances,
changement de métrique,...), on renvoie à [Edel, 1987], [Fort, 1997], [Klei, 1989] et [YvBo, 1995].

1.1 Généralités
Soit m un entier et E l’espace euclidien de dimension m. La distance euclidienne sur E est notée d. On considère un
ensemble S de points de E, de cardinal n, dont on note ℘(S) l’ensemble des parties. On définit la fonction φS : E 7→ ℘(S)
qui à un point x ∈ E associe {y ∈ S | d(x, y) = minz∈S d(x, z)}, c’est-à-dire l’ensemble de ses plus proches voisins dans
S.

Définition 1 (Diagramme de Voronoi). Pour toute partie R de S, on appelle cellule de Voronoi de R (dans S) l’image
réciproque de R par φS , que l’on note VorS (R).
On appelle diagramme de Voronoi de S l’ensemble des cellules de Voronoi non vides de parties de S.

Le diagramme de Voronoi de S est un complexe cellulaire de Rm . Chaque cellule de dimension m correspond à un

site x de S et est constitué de l’ensemble des points de E plus proche de x que de tout autre site de S. Chaque cellule
de codimension 1 est constitué de l’ensemble des points équidistants de deux sites x et y de S et plus proches de ces
deux sites que de tout autre site de S (cette cellule sépare les deux cellules correspondant à x et y respectivement), et
ainsi de suite (fig. 1).

Fig. 1 – Diagramme de Voronoi et triangulation de Delaunay de points dans le plan et dans l’espace

Définition 2 (Triangulation de Delaunay). Pour toute partie R de S telle qu’il existe une boule circonscrite à R qui
ne contient aucun site de S autre que les points de R, on définit la face de Delaunay DelS (R) comme l’enveloppe
convexe de R.
On appelle triangulation de Delaunay de S l’ensemble Del(S) des faces de Delaunay de S.

La triangulation de Delaunay de S est un complexe cellulaire qui forme une partition de l’enveloppe convexe de
S (fig. 1). Lorsque les points sont en position générale, c’est-à-dire lorsqu’au plus m + 1 d’entre eux appartiennent à
une même sphère et au plus k + 1 d’entre eux appartiennent à un même sous-espace affine de dimension k (pour tout
k < m), la triangulation de Delaunay est un complexe simplicial : toutes les faces de Delaunay sont des simplexes.

2
 Par ailleurs, le diagramme de Voronoi et la triangulation de Delaunay de S sont des complexes cellulaires duaux
l’un de l’autre (fig. 1) : pour tout partie R de S, la cellule de Voronoi VorS (R) est non vide si et seulement si il existe
une boule circonscrite à R ne contenant aucun autre site de S. L’application de Vor(S) dans Del(S) qui envoie VorS (R)
sur DelS (R) est une dualité entre complexes cellulaires (elle renverse l’ordre d’inclusion entre les faces).

1.2 Linéarisation
L’espace des sphères. Soient x ∈ E et r ∈ R+ . On appelle puissance de la sphère de centre x et de rayon
r l’application Σx,r de E dans R qui à un point y associe Σx,r (y) = d(x, y)2 − r2 . La puissance d’une sphère est
clairement nulle sur cette sphère, positive à l’extérieur et négative à l’intérieur. Elle atteind son minimum au centre
de la sphère. Le centre et le rayon de la sphère sont donc déterminés par la puissance de la sphère. Dans la suite, on
confond une sphère et sa puissance.
À la sphère Σx,r de E de centre x et de rayon r, on fait correspondre le point Ψ(Σx,r ) = (x, kxk2 − r2 ) =
(x, Σx,r (0)) ∈ E × R. L’ensemble Ẽ = E × R est appellé espace des sphères. On notera x la première coordonnée des
points de cet espace (x ∈ E) et t la deuxième (t ∈ R) ; on parlera d’abscisse et d’ordonnée. Le paraboloı̈de P de Ẽ
d’équation t = kxk2 représente les sphères de rayon nul. Tous les points de Ẽ situés au-dessous de P correspondent
aux sphères réelles de E tandis que les points de Ẽ au-dessus de P sont des sphères imaginaires.
Nous allons voir dans ce qui suit que les problèmes relatifs aux sphères dans l’espace E peuvent se voir comme
des problèmes linéaires dans l’espace des sphères Ẽ. On a ainsi linéarisé ces problèmes en augmentant la dimension de
l’espace. Pour illustrer ceci, on commence par étudier les faisceaux de sphères de E, puis on applique cette linéarisation
au diagramme de Voronoi et à la triangulation de Delaunay.

Faisceaux de sphères. Un faisceau de sphères est l’ensemble FΣ1 ,Σ2 des sphères combinaisons linéaires affines de
deux sphères données Σ1 et Σ2 :
FΣ1 ,Σ2 = {λΣ1 + (1 − λ)Σ2 | λ ∈ R},
(où λΣ1 + (1 − λ)Σ2 désigne la sphère de puissance x 7→ λΣ1 (x) + (1 − λ)Σ2 (x)).
On vérifie que le faisceau de sphères FΣ1 ,Σ2 est envoyé par Ψ dans l’espace des sphères sur une droite passant par
les points de Ψ(Σ1 ) et Ψ(Σ2 ). Les faisceaux de sphères peuvent donc se classer suivant le nombre d’intersections de
leur image par Ψ avec le paraboloı̈de P. On a ainsi les quatre situations suivantes (fig. 2) :

Faisceau à points limites Faisceau concentrique

Faisceau à sphère de base Faisceau tangent

Fig. 2 – Les quatre types de faisceaux de sphères

1. Si la droite Ψ(F ) rencontre P en deux points, F contient deux sphères de rayon nul que l’on appelle points limites
du faisceau F .
2. Si la droite Ψ(F ) rencontre P transversalement en un point, elle est nécessairement verticale (puisque le para-
boloı̈de est dirigé par la verticale). F est donc un faisceau de sphères concentriques.

3
 3. Si la droite Ψ(F ) ne rencontre pas P, il existe une famille d’hyperplans tangents au paraboloı̈de P qui contiennent
Ψ(F ). On note ΣF l’ensemble des points de E (considérés comme des sphères de rayon nul) qui appartiennent à
toutes les sphères du faisceau F . L’image par Ψ de ΣF correspond aux points de contact avec P des hyperplans
tangents à P et contenant Ψ(F ). Ainsi, ΣF est non vide, et on vérifie que c’est une sphère de dimension n − 1
que l’on appelle sphère de base du faisceau F .
4. Si la droite Ψ(F ) est tangente à P, on se trouve dans la situation d’un faisceau à points limites dont les deux
points limites sont confondus, ou dans celle d’un faisceau à sphère de base dont la sphère de base est réduite à
un point. On parle de faisceau tangent.

Diagramme de Voronoi. Considérons un point y de E (encore une fois confondu avec la sphère de rayon nulle
correspondante), et notons Hy l’hyperplan tangent au paraboloı̈de P au point Ψ(y). L’équation de Hy est donné par :
t = 2hx | yi − kyk2 .
Par conséquent, si y et z sont deux points fixés de E, un point x de E est plus proche de y que de z si et seulement si
au point d’abscisse x, l’hyperplan Hy est au-dessus de l’hyperplan Hz . On en déduit le théorème suivant (fig. 3) :
Théorème 1. Le diagramme de Voronoi d’un ensemble S de points de E est obtenu par projection verticale sur E de
l’intersection des demi-espaces supérieurs de Ẽ délimités par les hyperplans Hx , x ∈ S.

paraboloïde P
plan tangent associé à x
point x relevé de x

Espace de départ Relèvement Plans tangents

cellule de Voronoi de x

diagramme de Voronoi

Intersection Projection Diagramme de Voronoi

Fig. 3 – Diagramme de Voronoi par projection

Cette linéarisation permet d’appliquer les propriétés combinatoires connues des polytopes aux diagrammes de
Voronoi. Commençons par traiter le cas de la dimension 2. Un diagramme de Voronoi de n points du plan est la
projection d’un polytope de R3 à n faces. Or quitte à ajouter un sommet à l’infini, le graphe d’un polytope de R3
vérifie le lemme suivant :
Lemme 1 (Euler). Soit s le nombre de sommets, a le nombre d’arêtes et f le nombre de faces d’un polyèdre de R3 .
Alors s − a + f = 2.
Ce polytope ayant n faces, on en déduit que (s + 1) − a + n = 2. Or chaque arête ayant exactement deux sommets,
et chaque sommet étant incident à au moins trois arêtes, on a
2a = card{(s, a) ∈ S × A | s ∈ a} ≥ 3(s + 1).
On en déduit une borne sur la complexité d’un diagramme de Voronoi d’un ensemble de points du plan :
Proposition 1. Le nombre de sommets (resp. d’arêtes) du diagramme de Voronoi d’un ensemble S de n points du
plan est borné par 2n − 5 (resp. 3n − 6). La complexité du diagramme de Voronoi est donc bornée par 6n − 11.
Notons que l’on aurait pu obtenir directement cette borne en considérant le graphe sommets-arêtes d’un diagramme
de Voronoi de R2 qui est lui même planaire (voir par exemple [BKOS, 1997]). Cependant, la borne sur la complexité
du diagramme de Voronoi obtenue par linéarisation se généralise au cas de la dimension supérieure grâce au théorème
de la borne supérieure que l’on admet ici :

4
Théorème 2 (de
la borne supérieure). La complexité d’un polytope de Rm ayant n facettes (ie. faces de codimension
m
1) est en O n⌊ 2 ⌋ .

On en déduit ainsi par le théorème de projection du diagramme de Voronoi :

m

Proposition 2. La complexité du diagramme de Voronoi de n points de Rm est en O n⌈ 2 ⌉ .

Triangulation de Delaunay. Notons S̃ = {(x, kxk2 ) | x ∈ S} l’ensemble des relevés des points de S sur le
paraboloı̈de P. Soit R une partie de S. Supposons qu’il existe un hyperplan HR tel que tous les points de S̃ soient
situés au-dessus de HR , ou autrement dit tel que HR soit un hyperplan d’appui de l’enveloppe convexe inférieure de
S̃, alors la boule obtenue par projection verticale de l’intersection de P et du demi-espace inférieur délimité par HR
ne contient aucun point de S (exceptés ceux de R). Réciproquement, si R admet une boule circonscrite ne contenant
aucun autre point de S, cette boule est la projection de l’intersection de P par un demi-espace inférieur. L’hyperplan
délimitant ce demi-espace est alors un hyperplan d’appui de l’enveloppe convexe inférieure de S̃. On en déduit le
théorème suivant (fig. 4) :

Théorème 3. La triangulation de Delaunay d’un ensemble S de points de E est obtenue par projection verticale de
l’enveloppe convexe inférieure des points de S̃ = {(x, kxk2 ) | x ∈ S}.

paraboloïde P
point x relevé de x

Espace de départ Relèvement Enveloppe convexe Triangulation de Delaunay

inférieure

Fig. 4 – Triangulation de delaunay par projection

Ce théorème a une conséquence importante en dimension 2. Considérons un ensemble S de points du plan et une
triangulation complète T de S (c’est-à-dire une triangulation dont l’ensemble des sommets est exactement S). On
associe à cette triangulation l’application fT : conv(S) → R telle que
1. ∀x ∈ S, fT (x) = kxk2 ,
2. fT est affine sur tout simplexe de la triangulation T .
Le graphe de cette application est une surface, et même un complexe simplicial dont la projection verticale est exacte-
ment T . On définit alors un ordre partiel sur les triangulations complètes de S correspondant à l’ordre sur les surfaces
associées : si T et T ′ sont deux triangulations complètes de S,

T ≺ T ′ ⇔ fT ≥ fT′ .

La triangulation de Delaunay de S étant obtenue par projection de l’enveloppe convexe inférieure des relevés des points
de S sur le paraboloı̈de P, elle est maximale pour cet ordre.
Soit T une triangulation complète de S, a = {s1 , s2 } une arête de T , t1 , t2 les deux triangles de T qui contiennent
a et s3 , s4 leurs sommets libres respectifs. On dit que l’arête a est flippable si [s3 , s4 ] est contenu dans le quadrilatère
s1 s3 s2 s4 (fig. 5). Le flip de cette arête est un flip de Delaunay si la triangulation T ′ obtenue par ce flip est supérieure
à la triangulation T (fig. 5). Le théorème permet d’affirmer que si l’on se donne une triangulation complète T de S et
une série maximale de flips de Delaunay de cette triangulation, on obtient la triangulation de Delaunay. En particulier,
une triangulation localement Delaunay, c’est-à-dire dont aucune arête n’est flippable, est la triangulation de Delaunay.
Cette caractérisation permet d’établir les propriétés de la triangulation de Delaunay en étudiant uniquement les
propriétés d’une paire de simplexes contigus, et l’effet d’un flip sur ces simplexes. On montre par exemple que la
triangulation de Delaunay est celle qui optimise la séquence angulaire (si T est une triangulation avec t triangles, on
appelle séquence angulaire de T la suite AT = (α1 , α2 , . . . , α3t ) de ses angles intérieurs rangés dans l’ordre croissant ;
l’ordre lexicographique sur les séquences angulaires donne un ordre sur les triangulations, pour lequel la triangulation
de Delaunay est maximale).

5
 arête non flippable
surfaces correspondantes

arête flippable flip de Delaunay

Fig. 5 – Flips dans une triangulation

1.3 Calcul dans le plan

On a donné une interprétation du diagramme de Voronoi et de la triangulation de Delaunay d’un ensemble S de
points de Rm comme projections de polytopes de Rm+1 déterminés par les relevés des points de S sur le paraboloı̈de
P. Il en résulte en particulier que tout algorithme permettant de calculer ces polytopes (c’est-à-dire de déterminer les
sommets et les relations d’incidences entre les faces de ces polytopes) permet de calculer le diagramme de Voronoi et
la triangulation de Delaunay de S. On a vu aussi que la triangulation de Delaunay peut être obtenue en partant d’une
triangulation complète de S et en effectuant une chaı̂ne maximale de flips de Delaunay. Le calcul de la triangulation
de Delaunay ne nous intéressant pas pour la suite, on renvoie à [Fort, 1997] pour une présentation d’un algorithme
incrémental en temps optimal O(n ln n).
Dans ce paragraphe, on présente l’algorithme de Fortune permettant de calculer le diagramme de Voronoi d’un
ensemble de n points en temps optimal O(n ln n) par une technique de balayage du plan.
Le plan E étant le plan horizontal de l’espace, on appelle cône d’influence d’un point P de E le cône CP d’angle
π/4, d’axe vertical et de sommet P (donc d’équation t = d(M, P )). Le diagramme de Voronoi S de S est la projection
verticale sur le plan t = 0 de l’enveloppe convexe inférieure de l’union des cônes d’influence P ∈S CP (fig. 6).

cône d'influence

ensemble de départ diagramme de Voronoi

Fig. 6 – Cônes d’influence et diagramme de Voronoi

L’algorithme de balayage va calculer une projection sur le plan t = 0 de cette enveloppe convexe inférieure, mais
au lieu de calculer la projection verticale, ce sera la projection parallèlement à la direction (0, 1, −1) (fig. 7). Cette
dernière projection va pouvoir être calculée par balayage, et on pourra déduire du diagramme Vor′ (S) ainsi obtenu le
diagramme de Voronoi Vor(S).
On définit donc l’application

R2 −→  R2 
α: x

x
M= 7−→ .
y y + minP ∈S d(M, P )

Cette application est continue. De plus, si D est une droite parallèle à l’axe (Oy), alors
– si D ∩ S = ∅, alors pour tout P ∈ S, et tous points M1 = (x, y1 ) et M2 = (x, y2 ) de D, avec y1 < y2 , l’inégalité
triangulaire donne
d(M1 , P ) < d(M1 , M2 ) + d(M2 , P ).
Ainsi, les applications y 7→ y + d( xy , P ) sont toutes strictement croissantes, donc par passage au minimum, α

est strictement croissante sur D, donc injective.

– si P ∈ D ∩ S, α prend la même valeur sur tous les points de D situés avant P , mais reste injective après P .

6
 droite de balayage

Fig. 7 – Projection parallèlement à une génératrice des cônes

On en déduit que α est injective et continue sur les arètes du diagramme de Voronoi de S. Ainsi, α transforme le
diagramme Vor(S) en un diagramme Vor′ (S) ayant la même structure combinatoire :
1. la cellule VorS (P ) de Vor(S) est envoyée sur une cellule Vor′S (P ) de Vor′ (S),
2. l’arête VorS ({P, Q}) séparant deux cellules adjacentes VorS (P ) et VorS (Q), et portée par la médiatrice de P et
Q est envoyée sur une arête Vor′S ({P, Q}) qui sépare les deux cellules Vor′S (P ) et Vor′S (Q), et est portée par
l’hyperbole projection (parallèlement à la direction (0, 1, −1)) de l’intersection des deux cônes CP et CQ .
3. le sommet VorS ({P, Q, R}) à l’intersection des trois cellules VorS (P ), VorS (Q) et VorS (R) est envoyé sur le
sommet Vor′S ({P, Q, R}) intersection de Vor′S (P ), Vor′S (Q) et Vor′S (R).
Pour retrouver le diagramme Vor(S) à partir du diagramme Vor′ (S), il suffit donc de suivre la structure combinatoire
du second et de calculer les coordonnées des points VorS ({P, Q, R}).

On s’intéresse donc maintenant au calcul effectif de Vor′ (S). Le balayage est effectué par une droite ∆ parallèle
à l’axe (Ox), qui se déplace dans le sens des ordonnées croissantes. À chaque instant, on garde en mémoire deux
structures fondamentales :
1. un dictionnaire D qui représente les arêtes de Vor′ (S) qui intersectent ∆, triées par abscisses croissantes, et les
cellules que ces arêtes séparent.
2. une queue de priorité qui représente les évènements qui nécessitent une mise à jour, triés par ordonnées croissantes.
Ces évènements sont de deux types :
(a) lorsque ∆ atteind un point P de S. Dans ce cas, une nouvelle région VorS (P ) est créée et deux arcs sont
insérés dans D.
(b) lorsque ∆ atteind un point d’intersection de deux arcs. Dans ce cas, les deux arcs Vor′S ({P, Q}) et Vor′S ({Q, R})
sont remplacés par un unique arc Vor′S ({P, R}) et la région VorS (Q) est supprimée de D.
Dans ces deux cas, chaque fois que deux arcs deviennent consécutifs, on teste s’ils se rencontrent, et si tel est le
cas, on insère l’ordonnée de leur intersection dans la queue de priorité.
On parcourt ainsi toute la queue de priorité, et on a construit le diagramme Vor′ (S).

1.4 Applications
Les diagrammes de Voronoi et les triangulations de Delaunay ont de nombreuses interprétations et applications.
On présente ici les exemples du problème du bureau de poste, des problèmes de croissance et des arbres couvrants
minimaux. On renvoie à [Edel, 1987] pour d’autres applications.

Problème du bureau de poste. Soit S un ensemble de points dans le plan représentant les localisations des
bureaux de poste dans une ville. Les habitants de cette ville ont pour habitude de se rendre au bureau de poste le
plus proche de chez eux, la notion de proximité d’un bureau de poste étant mesurée par la distance euclidienne. Il est
clair que la répartition des utilisateurs des bureaux de poste suit le diagramme de Voronoi de S. La connaissance des
diagrammes de Voronoi permet alors de répondre à deux problèmes :

7
 – étant donné un point, quel est le bureau de poste le plus proche. La réponse naı̈ve (consistant à tester à chaque
fois tous les points de S) requiert un temps linéaire pour chaque demande, tandis que si le calcul du diagramme
de Voronoi est effectué comme prétraitement, on peut répondre en temps O(ln n).
– quelle va être la répercussion de l’installation d’un nouveau bureau de poste sur la répartition des utilisateurs.

Problème de croissance. Lorsqu’on dispose des échantillons de bactéries sur une planche nutritive, on observe
une croissance centrifuge qui s’arrète lorsque deux échantillons se rejoignent. Si toutes les bactéries se développent
à la même vitesse, on obtient ainsi le diagramme de Voronoi des points correspondant à l’emplacement initial des
échantillons (fig. 6). On observe le même phénomène sur la carapace des tortues ou dans le cou des girafes réticulés
(fig. 8).

Fig. 8 – Giraphe réticulée et tortue

Arbres couvrants minimaux. Soit S un ensemble de sommets. On dit qu’un arbre est un arbre couvrant pour S si
l’ensemble de ses sommets est S. On appelle arbre couvrant minimal tout arbre couvrant dont la somme des longueurs
des arêtes est minimale (parmi tous les arbres couvrants). On peut construire un arbre couvrant minimal de manière
incrémentale : on initialise l’algorithme en choisissant un sommet arbitraire, puis à chaque étape, on ajoute l’arête la
plus courte reliant un sommet déjà couvert à un sommet non couvert. En maintenant à chaque étape et pour chaque
sommet non couvert la connaissance du sommet couvert le plus proche, on effectue cet algorithme en temps O(n2 ).
De plus, en remarquant qu’une arête ne peut être ajoutée que si c’est une arête de la triangulation de Delaunay de
S, on peut diminuer le nombre de candidats pour le nouvel arc ajouté. On obtient ainsi un algorithme de complexité
O(n ln n).

2 Revêtements
Dans cette partie, on présente les revêtements de l’espace euclidien qui nous intéressent ensuite. Ces revêtements
ont été initialement introduits pour calculer l’enveloppe convexe [HaPo, 2004] et une pseudo-triangulation initiale
[HaPo, 2006] d’un ensemble de disques. Nous présentons ici (§ 2.2) leur utilisation dans deux situations :
– le calcul d’enveloppe convexe par la marche de Jarvis sans donnée initiale d’une droite d’appui de l’enveloppe
convexe,
– l’étude des problèmes géométriques (enveloppe convexe, diagramme de Voronoi et triangulation de Delaunay) en
présence d’obstacles.

2.1 Définition
On fixe deux entiers non nuls m et ν. Soit Rm l’espace euclidien orienté de dimension m.
On considère un complexe polyèdral pur de codimension 1 plongé dans Rm que l’on note C. On appelle facettes les
faces de dimension m − 1 de C. On associe à chaque facette f de C une permutation πf de {1, . . . , ν} et une orientation
transverse uf .
On découpe l’espace Rm euclidien suivant les facettes du complexe C et on note X le résultat obtenu et q : X → Rm
la projection canonique. Pour chaque facette f de C, on appelle relevé droit de f (resp. relevé gauche de f ) le relevé
de f pointé par le vecteur uf (resp. −uf ). On considère ensuite ν copies (Xi )i∈{1,...,ν} de X. On note E l’espace obtenu
en recolant le relevé droit dans Xi de chaque facette f de C avec le relevé gauche dans Xπf (i) de f via l’application
qπ−1
f (i)
◦ qi (fig. 9). On note p : E → Rm la projection canonique.

8
 L’espace E est muni de la structure plate avec singularités : on remonte la structure euclidienne de Rm dans E.
Une droite (resp. demi-droite, resp. segment ) de E est une partie de E homéomorphe à une droite (resp. demi-droite,
resp. segment) de Rm via la projection p. En particulier, on dit qu’une partie A de E est convexe si tout segment dont
les extrémités sont contenues dans A est inclus dans A, et on définit l’enveloppe convexe d’un ensemble A comme le
plus petit convexe (au sens de l’inclusion) contenant A.

complexe polyèdral C

uf
Rm euclidien πf=(123)
face f,
- orientation transverse uf
- permutation πf Є Sν

Feuillet 1 Feuillet 2 Feuillet 3

un chemin dans E

Fig. 9 – Revêtement de Rm

2.2 Motivations
Marche de Jarvis. Soit S un ensemble de points de R2 en position générale. On suppose donnée une droite d’appui
de l’enveloppe convexe de S en un point p ∈ S. L’algorithme de la marche de Jarvis consiste à trouver le point q
suivant p sur le bord de l’enveloppe convexe de S (c’est le point de S dont l’angle avec la droite d’appui de l’enveloppe
convexe de S en p est minimal) puis à recommencer jusqu’à ce que l’on retombe sur le point p. On obtient alors un
cycle d’arêtes qui forme le bord de l’enveloppe convexe de S (fig. 10) en temps O(nh), où n désigne le nombre de
points de S et h le nombre de sommets de l’enveloppe convexe de S.

Fig. 10 – Étapes successives de la marche de Jarvis dans le plan

Cependant, on ne peut pas toujours supposer connaı̂tre une droite d’appui initiale de l’enveloppe convexe de S
(par exemple lorsque le seul prédicat autorisé est le chirotope des points). Ce problème d’initialisation de l’algorithme
motive l’introduction d’un revêtement du plan : on choisit arbitrairement un point p de S et une demi-droite ∆ issue de
p, et on construit le revêtement obtenu par découpage, copie et recollements le long du complexe polyèdral C = (m, ∆),
pour lequel on a associé à ∆ la permutation (12) et une orientation arbitraire. On relève alors les points de S situés
à gauche de ∆ sur les deux feuillets, et ceux situés à droite sur le premier feuillet uniquement (fig. 11). On obtient
une configuration S̃ de points dans le revêtement pour laquelle le point p est un sommet de l’enveloppe convexe. On

9
a ainsi construit une configuration dans laquelle on connaı̂t une droite d’appui initiale. On peut alors effectuer une
marche de Jarvis dans le revêtement pour obtenir le bord de l’enveloppe convexe de S̃. On en déduit ensuite le bord
de l’enveloppe convexe de l’ensemble S initial (c’est la projection de la partie du bord de l’enveloppe convexe de S̃
située entre deux relevés d’un même point).

branche inutile
∆

Feuillet 1 Feuillet 2

bord de l'enveloppe convexe

Fig. 11 – Revêtement rendant m extrémal

Problèmes contraints. On considère l’espace Rm euclidien dans lequel est plongé un complexe polyèdral pur C de
codimension 1 que l’on appelle complexe des contraintes et que l’on s’interdit de traverser. Étant donné un ensemble
de points S de cet espace, on peut s’intéresser à différents objets géométriques qui lui sont associés :
1. Enveloppe convexe - la plus petite partie convexe (au sens de la visibilité) contenant S.
2. Diagramme de Voronoi - le diagramme de Voronoi de S au sens de la longueur visible

d(x, y) si x et y sont visibles
lv(x, y) =
∞ sinon.

3. Triangulation de Delaunay - la triangulation de Delaunay de S au sens de la longueur visible.

Ces trois objets géométriques en présence de contraintes peuvent être interprétés par la construction d’un revê-
tement de l’espace Rm . On note f1 , . . . , fν les facettes du complexe des contraintes, et on associe à la face fi une
orientation transverse arbitraire et la permutation πfi = (1, i + 1). On construit alors le revêtement de Rm à ν + 1
feuillets associé au complexe C, et on relève tous les objets que l’on veut étudier sur le premier feuillet X1 . Intuitive-
ment, si l’on assimile la présence de contraintes à l’existence de murs, cette opération revient à remplacer les murs par
des escaliers donnant sur d’autres étages : comme tout se passe au premier niveau, passer dans un niveau supérieur
revient à se déplacer dans un univers parallèle.
Ainsi, l’étude de ces objets dans les revêtements et l’élaboration d’algorithmes pour les déterminer permet en
particulier de traiter les problèmes géométriques en présence d’obstacles : on aura remplacé les obstacles par des
points de ramification.

3 Diagrammes de Voronoi et triangulation de Delaunay dans les revê-

tements
Dans cette partie, on s’intéresse au diagramme de Voronoi et à la triangulation de Delaunay d’un ensemble de
points dans un revêtement obtenu par découpage, copie et recollements le long d’un complexe polyèdral. Les méthodes
utilisées ici sont très similaires avec celles de la première partie : on veut généraliser les résultats connus dans le cadre
d’un espace euclidien. On montrera cependant les limites de la généralisation dans ces revêtements.

3.1 Définitions
Soit E un revêtement obtenu par découpage, copie et recollements le long d’un complexe polyèdral C, et p la
projection associée. Dans ce revêtement, la notion d’éloignement est mesurée par la longueur visible

d(p(x), p(y)) si x et y sont visibles
lv(x, y) =
∞ sinon.

10
Notons que cette fonction ne définit pas une distance puisqu’elle ne vérifie pas l’inégalité triangulaire. On peut ce-
pendant définir le lv-diagramme de Voronoi et la lv-triangulation de Delaunay de la même façon que dans l’espace
Rm : soit S un ensemble de points de E. On définit la fonction φlv S : E 7→ ℘(S) qui à un point x ∈ E associe
{y ∈ S | lv(x, y) = minz∈S lv(x, z)}, c’est-à-dire l’ensemble de ses plus proches voisins dans S au sens de la longueur
visible.
Définition 3 (lv-diagramme de Voronoi). Pour toute partie R de S, on appelle lv-cellule de Voronoi de R (dans S)
lv
l’image réciproque de R par φlv
S , que l’on note VorS (R).
On appelle lv-diagramme de Voronoi de S l’ensemble Vorlv (S) des cellules de Voronoi non vides de parties de S.
Notons que dans les revêtements, il peut arriver qu’un point n’ait aucun plus proche voisin (si tous les points de
S sont cachés par des contraintes). On peut donc avoir des lv-cellules correspondant à l’ensemble vide. Par ailleurs, la
lv-cellule de Voronoi d’une partie R de S n’est plus nécessairement connexe.
Définition 4 (lv-triangulation de Delaunay). Pour toute partie R de S telle qu’il existe une lv-boule circonscrite à R
qui ne contient aucun site de S autre que les points de R, on définit la lv-face de Delaunay Dellv
S (R) comme l’enveloppe
convexe de R.
On appelle lv-triangulation de Delaunay de S l’ensemble Dellv (S) des lv-faces de Delaunay de S.
Notons que la lv-triangulation de Delaunay n’existe pas toujours comme c’était le cas dans l’espace euclidien Rm .
En effet, à partir de la dimension 3, il existe des configurations de contraintes qui ne sont pas triangulables (donc en
particulier, il existe des ensembles de points dans certains revêtements qui ne sont pas triangulables). Citons l’exemple
du polyèdre de Schönhart obtenu en faisant tourner légèrement l’une des bases d’un prisme à base triangulaire et en
imposant les contraintes internes obtenues (fig. 12).

vue de côté vue de dessus

Fig. 12 – Polyèdre de Schönhart

Dans ce qui suit, nous supposerons donc toujours l’existence de la lv-triangulation de Delaunay, pour pouvoir en
étudier les propriétés.
Notons encore que le lv-diagramme de Voronoi et la lv-triangulation de Delaunay de S, même quand elle existe,
ne sont plus des complexes cellulaires duaux l’un de l’autre.

3.2 Linéarisation
L’espace Ẽ. On rappelle que l’on s’est donné un complexe polyèdral pur C de codimension 1 dans Rm dont on a
muni chaque facette f d’une orientation transverse uf et d’une permutation πf de {1, . . . , ν}, et que l’on a construit
un revêtement p : E → Rm par découpage, copie et recollement le long du complexe polyèdral C.
On considère maintenant le produit cartésien E × R. On note q la projection canonique de E × R sur E.
En fait, ce produit se construit comme un revêtement de Rm+1 de la manière suivante. On considère l’espace Rm+1
euclidien, et on note q̃ : Rm+1 → Rd la projection canonique. L’ensemble
n o
C̃ = f˜ = f × R | f ∈ C

est un complexe polyèdral pur de dimension m de Rm+1 . On munit chaque facette f˜ = f ×R de l’orientation transverse
uf˜ = (uf , 0) et de la permutation πf˜ = πf . On note Ẽ l’espace obtenu par découpage, copie et recollements de Rm+1
le long de C̃ et p̃ : Ẽ → Rm+1 le revêtement correspondant. L’espace Ẽ est alors le produit E × R.

11
 Pour résumer, on a le diagramme suivant :

p̃
Ẽ / Rm+1
q q̃
 p 
E / Rm

L’interprétation du produit E × R par un revêtement Ẽ construit par découpage, copie et recollements permet de
ne pas redéfinir la convexité dans E × R.

Paraboloı̈de dans Ẽ. On se place dans l’espace Ẽ = E × R et on considère le paraboloı̈de P de Rm+1 d’équation
m
X
P : xm+1 = x2i .
i=1

On appellera paraboloı̈de de E son image réciproque P par p̃

lv-diagramme de Voronoi. Comme dans les espaces euclidiens, le lv-diagramme de Voronoi d’un ensemble de
points du revêtement va s’interpréter comme projection d’une intersection de demi-espaces en dimension supérieure.
Donnons d’abord la définition des demi-espaces utilisés dans les revêtements.
Définition 5 (Demi-espace supérieur tangent associé à un point). Soit x ∈ E. On appelle relevé de x sur le paraboloı̈de
P le point x̃ = (x, kp(x)k2 ) = q −1 (x) ∩ P. On appelle demi-espace supérieur tangent associé à x la partie

Dx = p̃−1 (Dp̃(x̃) ) ∩ vis(x̃),

où Dy désigne le demi-espace supérieur de Rm+1 délimité par l’hyperplan tangent à P en y (pour y ∈ P ) et vis(x̃)
désigne l’ensemble des points de Ẽ visibles par x̃.
On obtient alors le théorème suivant, similaire au théorème 1 (fig. 13).

Théorème 4. Le lv-diagramme de Voronoi d’un ensemble de points S de E est la projection de l’intersection des
demi-espaces supérieurs tangents associés aux points de S.

Démonstration. Soit x ∈ E.
−1
Si x n’est visible d’aucun point de S, alors il n’est
T dans aucune lv-cellule de Voronoi de S. Or, q (x) n’est visible
−1
d’aucun relevé ỹ d’un point de S, donc q (x) ∩ ( y∈S Dy ) = ∅, donc la projection de l’intersection des demi-espaces
supérieurs tangents associés aux points de S ne rencontre pas x.
Si vis(x) ∩ S 6= ∅, alors

inf{lv(x, y) | y ∈ S} = inf{lv(x, y) | y ∈ vis(x) ∩ S}

= inf{d(p(x), p(y)) | y ∈ vis(x) ∩ S}.

Or dans Rm , le point p(y) qui réalise cette borne inférieure est celui tel que l’hyperplan tangent à P en son relevé
est au-dessus des hyperplans tangents à P en les relevés de tous les autres points. Par conséquent, le demi-espace
supérieur tangent Dy associé à y est au-dessus de tous les autres demi-espaces supérieurs tangents associés aux points
de S, et la lv-cellule de Voronoi qui contient x est bien la projection de la facette de l’intersection des demi-espaces
supérieurs tangents associés aux points de S qui se trouve au-dessus de x.

Notons que contrairement au cas de l’espace euclidien, nous n’avons pas ici de borne sur la complexité l’intersection
des demi-espaces supérieurs tangents au paraboloı̈de. On n’obtient donc pas de borne sur la complexité d’un lv-
diagramme de Voronoi dans le revêtement. C’est une question qu’il reste à traiter.

lv-triangulation de Delaunay. On suppose ici que l’ensemble de départ S contient tous les points de ramification.
On obtient alors le théorème suivant, similaire au théorème 3 (fig. 14).

Théorème 5. La lv-triangulation de Delaunay d’un ensemble de points S ⊂ E (lorsqu’elle existe) est la projection de
l’enveloppe convexe inférieure des relevés des points de S.

12
 plan tangent associé à x
~
complexe polyèdral C
complexe polyèdral C ~ lv-cellule de Voronoi de x
paraboloïde P
relevé de x

x
~
x
Vorlv,M(x)
Feuillet 1

Feuillet 2

Espace de départ Relèvement Plans tangents associés Diagramme de Voronoi

Fig. 13 – Diagramme de Voronoi par relèvement sur le paraboloı̈de

~
complexe polyèdral C
~
paraboloïde P
complexe polyèdral C relevé de x

x ~
x

Feuillet 1

Feuillet 2

Espace de départ Relèvement Triangulation de Delaunay

Fig. 14 – Triangulation de Delaunay par relèvement sur le paraboloı̈de

13
Démonstration. Les ensembles A = Dellv (S) et B = {q(f ) | f face de conv− (S̃)} sont deux complexes simpliciaux
dont le domaine est l’enveloppe convexe de S. Il suffit donc de vérifier qu’un simplexe de B est un simplexe de A. Soit
s un simplexe de l’enveloppe convexe inférieure de S̃ et Vert(s) l’ensemble de ses sommets. Soit g̃ ∈TRm+1 le centre
du cercle circonscrit à l’ensemble p̃(Vert(s)) et r son rayon. On note G̃ ∈ Ẽ un point de p̃−1 (g̃) ∩ x̃∈Vert(s) vis(x̃),
g = q̃(g̃) et G = q(g̃) ∈ E. Résumons ces notations sur le diagramme :

m+1
Ẽ p̃
/ R
G̃ g̃
q q̃
 
m
E / R
G p g

Soit x ∈ S̃ et x̃ son relevé sur P. Si x est un point de la lv-boule (de E) de centre G et de rayon r, alors p(x) est
dans la boule (de Rm ) de centre g et de rayon r. Il en résulte classiquement que q −1 (p(x)) ∩ P est situé en-dessous de
l’hyperplan de Rm+1 passant par les points p̃(z), z sommet de s. Mais q̃ −1 (p(x)) = {p̃(x̃)}, donc pour ne pas oublier
le point x̃, le simplexe s ne peut pas être un simplexe de l’enveloppe convexe inférieure de S̃.
Par conséquent, la sphère de centre G et de rayon r est une lv-sphère de Delaunay de q(s), donc q(s) ∈ Dellv (M )
ce qui montre le résultat.

Notons que comme dans le cas du plan euclidien, on peut définir un ordre sur les triangulations complètes de S,
correspondant à l’ordre sur les surfaces associées aux triangulations. On montre ainsi de la même manière que dans
le cas du plan que la triangulation de Delaunay est caractérisée par une condition locale : c’est la triangulation dont
aucune arête n’admet un flip de Delaunay.

3.3 Cônes d’influence et algorithme de balayage

On propose ici une généralisation de l’algorithme de calcul du diagramme de Voronoi par balayage de Fortune.
Pour cela, on donne d’abord une généralisation de la notion de cône d’influence d’un point du plan. On rappelle
que l’on a appelé cône d’influence d’un point P de Rm le cône CP de Rm+1 d’angle π/4, de direction verticale et de
sommet P .

Définition 6 (lv-cône d’influence). Soit P un point du revêtement E. On appelle lv-cône d’influence de P la partie
de Ẽ définie par
C̃P = p̃−1 (Cp̃(P ) ) ∩ vis(P ).

lv-cône d'influence de x

Feuillet 1 Feuillet 2

Fig. 15 – lv-cône d’influence dans un revêtement

Le lv-diagramme de Voronoi d’un ensemble S de points dans le revêtement est alors la projection verticale de
l’enveloppe convexe inférieure de l’union des lv-cônes d’influence des points de S. De la même manière que dans le cas
du plan, on peut alors mettre en place un algorithme de calcul du lv-diagramme de Voronoi d’un revêtement du plan
par balayage. On va calculer la projection de l’enveloppe convexe inférieure des lv-cônes d’influence des points de S
parallèlement à la direction (0, 1, −1) en balayant par un revêtement de droite (on balaie Rm par une droite δ et E
par ∆ = p̃−1 (δ)).
Certains points restent à vérifier :

14
 – le lv-diagramme de Voronoi de S et le lv-diagramme obtenu par projection parallèlement à la direction (0, 1, −1)
doivent avoir la même structure combinatoire de sorte qu’il puisse être possible d’obtenir le lv-diagramme de
Voronoi à partir de cette projection.
– la projection de l’enveloppe convexe inférieure des lv-cônes d’influence des points de S parallèlement à la direc-
tion (0, 1, −1) peut s’obtenir par balayage. Ici, les opérations élémentaires du balayage seront non seulement la
rencontre des points de S et l’intersection de deux arcs en cours, mais aussi la rencontre de points de ramification.
Par ailleurs, il reste à étudier la complexité d’un tel algorithme. Cette question est à rapprocher de la question
concernant la complexité combinatoire d’un lv-diagramme de Voronoi dans un revêtement.

Conclusion

Les diagrammes de Voronoi et les triangulations de Delaunay sont des objets largement étudiés en géométrie
combinatoire et algorithmique. On a vu que certaines de leurs propriétés peuvent être étendues au cas des revêtements
ramifiés de l’espace euclidien et on a soulevé certaines questions qui restent à mettre au point : complexité du lv-
diagramme de Voronoi, algorithme de balayage, étude des applications aux problèmes contraints,...
La démarche que l’on a présentée a été le fil directeur de mon travail de master : étudier de manière systématique
la généralisation des résultats classiques de géométrie combinatoire et algorithmique au cas des revêtements. Dans
cette optique, d’autres questions sont encore à traiter : calcul efficace de l’enveloppe convexe dans les revêtements (en
utilisant uniquement le prédicat du chirotope), énumération des triangulations,...

Bibliographie

[BKOS, 1997] m. de Berg, m. van Kreveld, m. Overmars & o. Schwarzkopf, Computational Geometry,
Algorithms and Applications, Springer, 1997.
[Edel, 1987] h. Edelsbrunner, Algorithms in Combinatorial Geometry, Springer-Verlag, 1987.
[Fort, 1997] s. Fortune, Voronoi diagrams and Delaunay Triangulation, in j.e. Goodman & j. O’Rourke,
Handbook of Discrete and Computational Geometry, CRC, 1997.
[HaPo, 2004] l. Habert & m. Pocchiola, Computing the Convex Hull of Disks Using only their Chirotope,
Abstracts 10th European Workshop Computational Geometry, p. 111-114, 2004.
[HaPo, 2006] l. Habert & m. Pocchiola, Computing Pseudo-Triangulation via Branched Coverings of the
Euclidean Plane, en préparation, 2006.
[Klei, 1989] r. Klein, Concrete and Abstract Voronoi Diagrams, Lecture Notes in Computer Science, Springer-
Verlag, 1989.
[YvBo, 1995] m. Yvinec & j.-d. Boissonnat, Géométrie algorithmique, Ediscience International, 1995.

15