Table des matières
1 Introduction 5
2 Aperc¸u de topologie des surfaces 7
2.1 Surfaces topologiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7
2.2 Classification des surfaces . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
2.3 Triangulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9
2.4 Caractéristique d’Euler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11 3
Diagramme de Vorono¨? et triangulation de Delaunay : définitions et pro-
priétés 13
3.1 Diagramme de Vorono¨? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.1.1 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.1.2 Propriétés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14
3.2 Triangulation de Delaunay . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.2.1 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
3.2.2 Propriétés simples . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17
3.2.3 Propriété fondamentale . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18
3.2.4 Propriété angulaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
4 Diagramme de Vorono¨? et triangulation de Delaunay : algorithmes 21
4.1 Vorono¨? : intersection de demi-plans . . . . . . . . . . . . . . . . . . . . . . . . . 21
4.2 Vorono¨? : construction incrémentale . . . . . . . . . . . . . . . . . . . . . . . . . . 21
4.3 Vorono¨? : diviser pour régner . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
4.4 Vorono¨? : algorithme par balayage . . . . . . . . . . . . . . . . . . . . . . . . . . 23
4.5 Delaunay : construction incrémentale . . . . . . . . . . . . . . . . . . . . . . . . . 24
4.6 Quelques applications . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
4.6.1 Problème des bureaux de Poste . . . . . . . . . . . . . . . . . . . . . . . . 26
4.6.2 Cristallographie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
4.6.3 Planification de trajectoire . . . . . . . . . . . . . . . . . . . . . . . . . . 26
4.6.4 Méthode des éléments finis . . . . . . . . . . . . . . . . . . . . . . . . . . 26
4.6.5 Arbre couvrant minimal . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26
4.6.6 Reconstruction de surface . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
5 Extension : diagramme de Laguerre 29
5.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
5.2 Définitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
5.3 Propriétés . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
Annexe : lexique anglais-franc¸ais 33
Bibliographie 35
4 TABLE DES MATIERES`
Chapitre 1
Ce polycopié a pour but d’accompagner les quelques heures d’introduction à la géométrie algorithmique du cours de modélisation surfacique. La géométrie algorithmique (en anglais : computational geometry), comme son nom l’indique, a pour but le développement et l’étude d’algorithmes pour résoudre des problèmes de géométrie. C’est une discipline très ancienne, car Euclide en faisait déjà sans le savoir! De manière plus récente, la géométrie algorithmique s’est développée à partir des années 1970 en réponse à des problèmes de conception assistée par ordinateur (C.A.O.), de robotique, de géographie (planification de trajectoires, ), d’informatique graphique, de conception de circuits intégrés, etc.
Dans ce polycopié, nous nous restreignons à l’étude de deux structures de données classiques en géométrie algorithmique : le diagramme de Vorono¨? et la triangulation de Delaunay. Le premier chapitre donne un bref aperc¸u de notions de topologie des surfaces utiles pour la suite (variété, simplexe, triangulation, ). Le deuxième introduit les deux concepts de diagramme de Vorono¨? et de triangulation de Delaunay, et en présente quelques propriétés. Le troisième chapitre est consacré à l’étude de quelques algorithmes de calcul de ces structures. Enfin, le quatrième et dernier chapitre aborde une extension du diagramme de Vorono¨?, appelée diagramme de Laguerre.
6 CHAPITRE 1. INTRODUCTION
Chapitre 2
Le but de ce chapitre est notamment de répondre à la question suivante : qu’est-ce qu’une surface?
Vaste question Tous les objets suivants, plongés dans R3, peuvent être considérés, à des degrés divers, comme des surfaces, même si le premier n’est pas connexe, si le deuxième possède un trou, si le troisième n’est pas orientable (il n’y a pas d’intérieur et d’extérieur!) et si le quatrième n’est pas borné.
(a) (b) (c) (d)
Fig. 2.1 – (a) Surface non connexe. (b) Tore. (c) Bouteille de Klein. (d) Cylindre infini.
En topologie, une surface va être définie comme un espace topologique particulier.
Définition 1 (Espace topologique).Un espace topologique est un ensemble X et un système X de sous-ensembles de X tels que :
• ?,X ? X ;
• une union d’éléments de X est dans X ;
• une intersection finie d’éléments de X est dans X.
X est appelé une topologie et les éléments de X sont appelés les ouverts de X. Un sous-espace topologique (Y,Y ) de (X,X) est constitué d’un sous-ensemble Y ? X et de la topologie de sous-espace définie par Y = {Y ? A,A ? X}
Exemple. L’espace euclidien à d dimensions Rd est un espace topologique.
8 CHAPITRE 2. APERC¸U DE TOPOLOGIE DES SURFACES
Nous nous intéressons maintenant à des espaces topologiques particuliers. Nous rappelons qu’un voisinage d’un point x ? X est simplement un ensemble ouvert contenant x.
Définition 2 (Variété).Un espace topologique X est une k-variété si tout point x ? X possède un voisinage V dans X homéomorphe a` Rk (c’est-a`-dire qu’il existe une fonction f : V ? Rk bijective, continue et d’inverse continue).
Définition 3 (Variété à bord).Soit Hk le demi-espace a` k dimensions : Hk = {x = (x1, ,xk) ? Rk,x1 ? 0}. Un espace X est une k-variété à bord si tout point x ? X possède un voisinage dans X homéomorphe a` Rk ou a` Hk. La frontière (ou le bord) de X est l’ensemble des points de X qui ont un voisinage homéomorphe a` Hk. C’est soit une (k ? 1)-variété (sans bord), soit l’ensemble vide.
La définition 2 implique que si M est une k-variété, alors on peut trouver un nombre dénombrable d’ensembles ouverts Ui et d’homéomorphismes ?i : Ui ? Rk, tels que M = SUi.
Définition 4 (Plongement, immersion).On appelle plongement d’une k-variété X dans Rn une application f : X ? Rn dont la restriction a` l’image de X est un homéomorphisme. Si une telle application existe, on dit que X est plongée dans Rn. Si f est simplement injective de X dans Rn, on dit que f est une immersion.
Nous pouvons maintenant définir une surface.
Définition 5 (Surface).Une surface est une 2-variété.
Définition 6 (Surface à bord).Une surface à bord est une 2-variété a` bord.
Nous allons maintenant utiliser les définitions précédentes afin de classer les surfaces. Les surfaces que nous allons étudier seront compactes, connexes et plongées dans R3.
Définition 7 (Ensemble compact).Un sous-ensemble de Rn,n ? 1, est dit compact s’il est a` la fois fermé (c’est-a`-dire que son complémentaire dans Rn est un ouvert) et borné (inclus dans une boule euclidienne de rayon fini).
Définition 8 (Surface connexe).Une surface est dite connexe si deux points quelconques sur la surface peuvent être connectés par une courbe continue contenue dans la surface.
Nous allons étudier les propriétés topologiques de telles surfaces. Deux surfaces seront considérées comme topologiquement équivalentes s’il existe un homéomorphisme entre elles. Il se trouve que, graˆce à cette relation d’équivalence, il est possible de classer les surfaces.
Théorème 9 (Classification des surfaces).Toute surface (sans bord) compacte connexe est homéomorphe soit a` une sphère a` g trous, g ? 0, soit a` une sphère a` g bonnets croisés, g ? 1. Une surface du premier type ne peut pas être homéomorphe a` une surface du second type, et deux surfaces de même type mais avec des valeurs de g différentes ne peuvent pas être homéomorphes.
Exemple. L’exemple de la figure 2.1 (a) n’est pas connexe, mais est composé de deux sphères. Le tore est lui homéomorphe à une sphère à un trou, et la bouteille de Klein à une sphère à un bonnet croisé. Le cylindre infini ne peut pas être classé selon le théorème précédent, car ce n’est pas une surface compacte (il n’est pas borné).
2.3. TRIANGULATIONS 9
(a) (b)
Fig. 2.2 – (a) Ruban de M¨obius. (b) Bonnet croisé.
Définition 10 (Genre).g est appelé le genre de la surface.
Définition 11 (Surface orientable).Une surface homéomorphe a` une sphère a` g trous, g ? 0, est dite orientable, et une surface homéomorphe a` une sphère a` g bonnets croisés, g ? 1, est dite non orientable.
Propriété 12.Une surface orientable peut être plongée dans R3. Une surface non-orientable ne peut pas être plongée dans R3, mais peut y être immergée.
Les deux sections précédentes nous ont permis de définir rigoureusement une surface, d’un point de vue topologique. Nous allons maintenant nous restreindre au cas des surfaces discrètes, c’està-dire définies à partir d’un nombre fini de points. En effet, on travaille souvent en informatique sur de telles surfaces, qui sont généralement des approximations de surfaces réelles ou idéales : par exemple, le lapin de la figure 2.3 – le célèbre bunny de Stanford – est une surface maillée, créée en scannant un modèle réel en argile (le scanner détecte la position géométrique d’un certain nombre de points du modèle, et ces points sont ensuite reliés trois à trois pour former des triangles, graˆce à un algorithme adéquat).
(a) (b)
Fig. 2.3 – (a) Le bunny de Stanford. (b) Zoom sur les oreilles du bunny.
10 CHAPITRE 2. APERC¸U DE TOPOLOGIE DES SURFACES
Fig. 2.4 – De gauche à droite : 0-simplexe, 1-simplexe, 2-simplexe et 3-simplexe de R3.
Définition 13 (Simplexe).Soit e0, ,en un ensemble de n+1 points linéairement indépendants dans un espace euclidien Em,m ? n ? 0. On appelle n-simplexe de sommets e0, ,en l’enveloppe convexe ? de ces points. n est la dimension de ?. Par ailleurs, on appelle ?1-simplexe l’ensemble vide.
Exemple. Dans R3, un 0-simplexe est un sommet, un 1-simplexe une arête, un 2-simplexe un triangle et un 3-simplexe un tétraèdre (cf. figure 2.4).
Définition 14 (Face).Soit S un ensemble de points linéairement indépendants et ? son enveloppe convexe. Alors l’enveloppe convexe ? de tout sous-ensemble T de S est également un simplexe, sous-ensemble de ?. On dit que ? est une face de ?, et on note ? ? ?.
Définition 15 (Complexe simplicial).Un complexe simplicial est une collection K de faces d’un nombre fini de simplexes, tels que :
• ? ? K ? ? ? ? ? ? ? K ; • ?,? ? K ? ? ? ? ? ?,?.
Autrement dit, si ? est dans K alors toute face de ? est aussi dans K, et si ? et ? sont dans K alors leur intersection est a` la fois une face de ? et une face de ?.
La dimension d’un complexe simplicial est la dimension de son plus grand simplexe.
Nous définissons maintenant deux notions importantes concernant la structure locale d’un complexe simplicial.
Définition 16 (Etoilé, lien).Soit K un complexe simplicial et ? un simplexe dans K. L’étoilé de ? est l’ensemble des simplexes de K contenant ? : St(?) = {? ? K,? ? ?}. Notons
le plus petit sous-complexe de K contenant St(?). Le lien de ? est l’ensemble des faces des simplexes de l’étoilé de ? n’intersectant pas.
Exemple. La figure 2.5 représente l’étoilé et le lien d’un sommet dans R3.
Restreignons-nous maintenant aux espaces euclidiens Rn.
Nous allons maintenant établir un lien entre la topologie d’un ensemble de points et la topologie combinatoire, plus exactement entre les notions d’espace topologique et de complexe simplicial. Rappelons que ?n ? 1,Rn est un espace topologique.
Définition 17 (Polyèdre).Soit K un complexe simplicial dans Rn. L’union |K| de tous les simplexes de K avec la topologie de sous-espace de Rn est appelée le polyèdre (ou parfois l’espace sous-jacent) de K.
2.4. CARACTERISTIQUE D’EULER´ 11
Fig. 2.5 – Exemple de complexe simplicial comportant six sommets, dix arêtes et cinq triangles. A gauche les arêtes en gras et les triangles grisés appartiennent à l’étoilé de s; à droite les sommets et arêtes en gras appartiennent au lien de s.
Définition 18 (Triangulation).La triangulation d’un espace topologique X est un complexe simplicial K dont le polyèdre |K| est homéomorphe a` X. Si un tel complexe simplicial existe, on dit que X est triangulée.
Exemple. Une surface triangulée est une 2-variété homéomorphe au polyèdre d’un complexe simplicial.
Nous allons maintenant voir que les notions de surface triangulée et de surface topologique sont liées.
Définition 19 (Caractéristique d’Euler).La caractéristique d’Euler ?K d’un complexe simplicial K est la somme alternée du nombre de ses simplexes suivant leur dimension :
d
?K = X(?1)isi, (2.1)
i=0
ou` d est la dimension de K et ?0 ? i ? d,si est le nombre de i-simplexes dans K.
Remarque. On peut réécrire ?K sous la forme : ?K = X (?1)dim(?), avec ?? ? K,dim(?)
??K,?6=?
la dimension de ?.
Exemple. Pour une surface triangulée, ?K = V ? E + F, avec V le nombre de sommets de la triangulation, E son nombre d’arêtes et F son nombre de faces.
Propriété 20.Soient A et B deux complexes simpliciaux. Alors ?A?B = ?A + ?B ? ?A?B.
Théorème 21 (Relation d’Euler).La caractéristique d’Euler d’une surface M compacte, connexe, de genre g et a` bc bonnets croisés vaut ?M = 2 ? 2g ? bc.
Théorème 22 (Relation d’Euler généralisée).La caractéristique d’Euler d’une surface M compacte, connexe, a` bord, de genre g et a` bc bonnets croisés et dont la frontière est constituée de bo composantes connexes (les bords) vaut ?M = 2 ? 2g ? bc ? bo.
Ces deux théorèmes nous indiquent en particulier que pour une surface triangulée, la quantité V ? E + F ne dépend que de sa topologie.
12 CHAPITRE 2. APERC¸U DE TOPOLOGIE DES SURFACES
Chapitre 3
Diagramme de Vorono¨? et triangulation de Delaunay : définitions et propriétés
Nous nous intéressons maintenant au problème suivant : étant donné un ensemble E de points du plan ou de l’espace, quelle est la “meilleure” triangulation possible de E ?
La réponse à cette question dépend bien entendu de l’application visée, mais généralement trois propriétés de la triangulation sont particulièrement recherchées :
• celle-ci doit être robuste (l’ajout ou la suppression d’un point à E ne nécessite pas la modification complète de la triangulation);
• elle doit être rapide à calculer;
• elle doit contenir le moins possible de triangles allongés.
Cette dernière propriété est particulièrement intéressante pour de nombreuses applications, comme nous le verrons dans le chapitre suivant. Ce chapitre a pour but l’étude de la triangulation de Delaunay, dont nous prouverons qu’elle est la meilleure pour ce critère, et de sa structure duale, le diagramme de Vorono¨?.
Le diagramme de Vorono¨?, parfois appelé tessellation de Dirichlet, est une des structures géomé– triques les plus importantes en pratique, avec l’enveloppe convexe. Il a été introduit, dans le cas de R2 et de R3, par le mathématicien allemand Johann Peter Gustav Lejeune Dirichlet (18051859) en 1850. Le mathématicien russo-ukrainien Georgy Vorono¨? (1868-1908) a formalisé cette notion dans le cas général en 1908.
Soit E un espace vectoriel euclidien. Soit P = {pi,1 ? i ? n} un ensemble fini de points de E.
Définition 23 (Cellule de Vorono¨?, germe).On appelle cellule de Vorono¨? du point pi ? P, et on note Ci, l’ensemble des points de E plus proches de pi que de tout autre point de P : Ci = {q ? E,?j 6= i,||qpi|| ? ||qpj||}. Le point pi associé a` une cellule Ci est appelé germe de cette cellule.
Définition 24 (Diagramme de Vorono¨?).On appelle diagramme de Vorono¨? de l’ensemble P, et on note V or(P), la subdivision de E en les cellules Ci associées aux points pi de P :
13
V or(P) = [ Ci.
pi?P
Définition 25 (Sommet, arête et face de Vorono¨?).Soit d la dimension de E. L’intersection de d+1 cellules de Vorono¨?, si elle est non vide, est appelée sommet de Vorono¨?. L’intersection de d cellules de Vorono¨?, si elle est non vide, est appelée arête de Vorono¨?. L’intersection de i cellules de Vorono¨?, 2 ? i ? d ? 1, si elle est non vide, est appelée face de Vorono¨?.
Remarque. Dans la littérature, on trouve parfois seulement le terme face de Vorono¨? employé : dans ce cas, l’intersection de i cellules de Vorono¨?, 2 ? i ? d + 1, est appelée face de Vorono¨?.
Exemple. La figure 3.1 donne des exemples de diagramme de Vorono¨? de (a) 2, (b) 3 et (c) 27 points du plan. On remarquera que certaines cellules sont bornées et d’autres non.
(a) (b) (c)
Fig. 3.1 – Diagrammes de Vorono¨? d’ensembles de points du plan.
Nous nous restreignons dorénavant au cas du plan : E = R2. Les propriétés suivantes sont néanmoins généralisables à un espace euclidien de dimension d > 2.
Propriété 26.Une arête de Vorono¨?, séparant deux cellules Ci et Cj, est portée par la médiatrice du segment pipj.
Démonstration. En effet, tous les points situés sur cette arête de Vorono¨? sont à égale distance de pi et de pj. Ils sont donc sur la médiatrice de pipj.
Propriété 27.Le sommet de Vorono¨? séparant trois cellules Ci, Cj et Ck est le centre du cercle circonscrit au triangle de sommets pi, pj et pk.
Démonstration. Ce sommet est à égale distance des trois points pi, pj et pk.
Remarque. Dans le cas ou` les trois points pi, pj et pk sont alignés, le sommet de Vorono¨? n’existe pas.
Lemme 28.L’intersection d’un nombre fini de demi-plans est une région convexe.
Démonstration. Soit une intersection d’un nombre fini de demi-plans. Soient a,b ?
C. Un demi-plan est trivialement une région convexe. Donc ?i, comme, on
a ?t ? [0,1],ta +(1?t)b ? DPi. Donc finalement ?t ? [0,1],ta +(1?t)b ? \ DPi = C : C est
i=1 bien une région convexe.
Propriété 29.Une cellule de Vorono¨?, si elle est bornée, est un polygone convexe.
Démonstration. Soit Ci une cellule de Vorono¨?. Ci est l’intersection d’un nombre fini de demiplans (les demi-plans {x ? R2,||xpi|| ? ||xpj||}), c’est donc une région convexe. La frontière de Ci est constituée d’une suite d’arêtes de Vorono¨? et de sommets de Vorono¨?. Si Ci est bornée, sa frontière est fermée; Ci est donc un polygone.
La propriété suivante nous sera utile au chapitre 4, pour calculer les couˆts des algorithmes.
Propriété 30.Si n ? 3, le nombre V de sommets d’un diagramme de Vorono¨? a` n germes est au plus 2n ? 5, et son nombre E d’arêtes est au plus 3n ? 6.
Démonstration. Nous allons utiliser la relation d’Euler généralisée (théorème 22), mais celleci n’étant valable que pour des surfaces compactes, il faut d’abord transformer le diagramme de Vorono¨?. Ajoutons virtuellement un sommet de Vorono¨? s? à l’infini et relions-y toutes les arêtes de Vorono¨? dont une extrémité est à l’infini (voir figure 3.2) : on a transformé le plan en surface homéomorphe à une sphère, donc le théorème 22 nous dit que ?V or = 2. De plus, la définition 19 nous dit que ?V or = V? ? E + F, avec F le nombre de cellules de Vorono¨? du diagramme étendu et V? son nombre de sommets : V? = V + 1 et F = n, puisqu’on a ajouté un sommet sans créer ni supprimer de cellule. Comme chaque arête de Vorono¨? a exactement deux sommets extrémités, on a 2E = Xdegre(si) (le degré d’un sommet est son nombre de
si
voisins). Si les germes ne sont pas alignés, on sait par définition que chaque sommet correspond à l’intersection de trois cellules, donc est voisin d’au moins 3 autres sommets, ce qui se traduit par Xdegre(si) ? 3(V +1). On a donc 2E ? 3(V +1) et V +1?E +n = 2, d’ou` V ? 2n?5
si et E ? 3n ? 6.
Remarque. Une arête de Vorono¨? étant adjacente à exactement deux cellules, une cellule de
Vorono¨? a donc en moyenne moins de 6 côtés (car
La notion de triangulation de Delaunay a été proposée en 1934 par un mathématicien russe élève de Georgy Vorono¨? : Boris Delaunay (d’ou` son nom).
Définition 31 (Triangulation de Delaunay).On appelle triangulation de Delaunay de l’ensemble P, et on note Del(P), le dual du diagramme de Vorono¨? de P : les sommets de la triangulation de Delaunay sont les points pi ? P, et deux sommets sont reliés par une arête dans la triangulation si les cellules de Vorono¨? correspondantes sont voisines.
(a) (b) (c)
Fig. 3.3 – Triangulations de Delaunay duales des diagrammes de Vorono¨? de la figure 3.1.
Remarque. Même si cette définition est valide dans le cas d’un espace euclidien E de n’importe quelle dimension, le terme triangulation fait référence au cas du plan. Dans le cas de R3, on parle parfois de tétraédrisation de Delaunay.
Définition 32 (Sommet de Delaunay, arête de Delaunay).Les sommets d’une triangulation de Delaunay sont appelés sommets de Delaunay. Si E = R2, les arêtes d’une triangulation de Delaunay sont appelées arêtes de Delaunay.
Exemple. La figure 3.3 montre les triangulations de Delaunay duales des diagrammes de Vorono¨? de la figure 3.1 : dans le premier cas (2 points), la triangulation n’est constituée que des deux points et d’une arête, et dans le deuxième cas (trois points), la triangulation n’est constituée que des trois points, de 3 arêtes et d’un triangle.
Propriété 33.Si les points de P sont en position générale, c’est-a`-dire si un sommet de Vorono¨? n’est jamais incident a` plus de trois cellules, alors la triangulation de Delaunay correspond a` une triangulation (au sens de la définition 18).
Nous allons montrer cette propriété dans le cas du plan.
Démonstration. Par définition, les sommets de Del(P) co¨?ncident avec P. Comme Del(P) est le dual de V or(P) et que les sommets de V or(P) ont tous exactement trois voisins (puisqu’ils sont incidents à trois cellules), les régions de Del(P) sont des triangles. Del(P) est donc une décomposition de R2 en triangles, dont les sommets sont exactement les points de P. Le fait que l’intersection de deux triangles ? et ? est soit vide, soit un sommet commun à ? et à ?, soit une arête commune à ? et à ?, ainsi que le fait qu’un sous-ensemble borné de R2 n’intersecte qu’un nombre fini de triangles, se montrent aisément.
Remarque. Dans le cas contraire, on parle parfois de diagramme de Delaunay.
Les propriétés suivantes se montrent de manière triviale.
Propriété 34.La frontière de la triangulation de Delaunay d’un ensemble de points P est l’enveloppe convexe de P.
Propriété 35.La cellule de Vorono¨? Ci associée a` un germe pi n’est pas bornée si et seulement si pi appartient a` l’enveloppe convexe de P.
Pour les deux propriétés suivantes, nous nous plac¸ons dans le cas de R2.
Propriété 36.Le cercle centré en un sommet de Vorono¨? et passant par les trois germes voisins pi, pj et pk est le cercle circonscrit au triangle de Delaunay pipjpk.
Propriété 37.Soit pi ? P. Le point pj de P le plus proche de pi est tel que pipj est une arête de Delaunay.
De la même manière, nous énonc¸ons cette propriété dans le cas du plan, mais elle peut être étendu à un espace euclidien de dimension d quelconque.
Théorème 38 (Caractérisation des triangulations de Delaunay).Soient pi, pj et pk trois points de P. Alors le triangle de sommets pi, pj et pk est un triangle de la triangulation de Delaunay de P si et seulement si le cercle circonscrit a` ce triangle ne contient aucun autre point de P.
Démonstration. Le triangle pipjpk est un triangle de Del(P) si et seulement si il est le dual d’un sommet de Vorono¨?s de V or(P). Par définition, si s existe, il est à égale distance des trois points pi, pj et pk. C’est donc forcément le centre du cercle circonscrit à pipjpk. Or ce point est bien un sommet de Vorono¨? si et seulement si il n’y a pas d’autre point de P plus près de lui que pi, pj et pk. Donc pipjpk est un triangle de Del(P) si et seulement si le cercle circonscrit à ce triangle ne contient aucun autre point de P.
De la même manière, on peut montrer la propriété suivante :
Propriété 39.Soient pi et pj deux points de P. Alors le segment pipj est une arête de la triangulation de Delaunay de P si et seulement si il existe un cercle passant par pi et pj tel que le disque correspondant ne contienne aucun autre point de P.
Démonstration. Supposons que pipj est une arête de Delaunay. Les cellules Ci et Cj sont donc voisines; prenons un point q sur l’arête de Vorono¨? séparant Ci de Cj : par définition de cette arête, il n’y a aucun point de P à l’intérieur du cercle de centre q et passant par pi et pj (en effet sinon q appartient à la région de Vorono¨? associée au point de P correspondant). Supposons maintenant qu’il existe un cercle C passant par pi et pj tel que le disque correspondant ne contienne aucun autre point de P, et montrons que pipj est une arête de Delaunay. Soit q le centre de C. Comme q est équidistant de pi et de pj et qu’il n’existe pas d’autre point de P plus proche de q, q appartient à l’intersection des cellules de Vorono¨? Ci et Cj. Comme il n’y a pas d’autre point de PsurC, on peut agrandir ou rétrécir ce cercle de manière continue et infinitésimale en conservant le fait que pi et pj soient les seuls points de P sur C. Cela revient à déplacer q sur la médiatrice de pipj : ceci engendre un segment non réduit à un point séparant Ci de Cj, donc pipj est une arête de Delaunay.
Fig. 3.4 – Illustration de la caractérisation des triangulations de Delaunay.
Nous nous restreignons à nouveau au cas du plan. Soit P un ensemble de points du plan, et T une triangulation quelconque de P. Le nombre m de triangles de T ne dépend que du nombre de points de P, d’après la relation d’Euler appliquée au plan (quitte à ajouter un sommet virtuel à l’infini, comme pour la démonstration de la propriété 30). Trions les 3m angles des triangles de T par ordre croissant : ceci nous donne un 3m-uplet (?1(T),?2(T), ,?3m(T)) caractéristique de T, parmi toutes les triangulations de P. Nous pouvons donc ordonner les triangulations de P, selon l’ordre lexicographique sur les 3n-uplets : T1> T2 si et seulement si il existe k ? [1,3m] tel que (?i < k,?i(T1) = ?i(T2)) et (?k(T1) > ?k(T2)).
Théorème 40 (Maximisation des angles).La triangulation de Delaunay d’un ensemble de points P est maximale pour l’ordre lexicographique des angles.
La démonstration de ce théorème est assez longue et nécessiterait l’introduction d’une nouvelle définition (triangulation localement de Delaunay) et de plusieurs lemmes; elle n’est donc pas présentée ici. Elle utilise notamment le théorème 38 et la propriété 39.
La triangulation de Delaunay d’un ensemble de points est donc celle qui évite le mieux la création de triangles aplatis : les triangles ont, autant que possible, une forme proche d’un triangle équilatéral.
Fig. 3.5 – Deux triangulations d’un même ensemble de points du plan. Celle de gauche est la triangulation de Delaunay : l’angle minimum dans un triangle de cette triangulation est plus grand que l’angle minimum dans un triangle de la triangulation de droite.
20CHAPITRE 3. DIAGRAMME DE VORONO¨I ET TRIANGULATION DE DELAUNAY : DEFINITIONS ET PR´
Chapitre 4
Nous présentons dans ce chapitre quelques algorithmes de calcul d’un diagramme de Vorono¨? ou d’une triangulation de Delaunay, dans le cas du plan. L’objectif est bien suˆr d’obtenir l’algorithme le plus rapide possible; cependant l’algorithme doit pouvoir être implémentable! Notons également qu’une fois qu’une des deux structures a été calculée, l’autre peut en être déduite automatiquement, par dualité.
L’idée la plus naturelle pour construire un diagramme de Vorono¨? est de construire chaque cellule Ci de manière indépendante, comme intersection des n?1 demi-plans définis par les médiatrices des segments pipj,?j 6= i. Cette construction est duale de la construction de l’enveloppe convexe de n ? 1 points du plan (en effet, le dual d’un point (x,y) est la droite d’équation b = xa ? y et le dual d’une droite y = ax + b est le point (a,b)), et comme (peut-être) vu en cours d’algorithmique 2 de première année Ensimag, cette enveloppe convexe peut être calculée en temps O(nlogn).
La construction du diagramme de Vorono¨? se fait donc en temps O(n2 logn).
Une autre idée afin de construire un diagramme de Vorono¨? consiste à procéder de manière incrémentale : supposons que le diagramme de Vorono¨? d’un ensemble Pn?1 = {p1, ,pn?1} de n ? 1 points du plan a été construit; que faut-il modifier à ce diagramme pour construire le diagramme d’un ensemble P = Pn?1 ? {pn}?
Intuitivement, on comprend aisément que l’insertion d’un point pn ne va modifier le diagramme de Vorono¨? que localement. Quels sont les sommets de Vorono¨? qui vont disparaˆ?tre lors de cette insertion? Ce sont ceux dont le cercle associé (circonscrit aux germes voisins) contient pn, car on sait que l’intérieur des cercles centrés aux sommets de Vorono¨? et circonscrits aux germes voisins doit toujours être vide. Ces sommets sont dans une zone limitée du diagramme, ce qui conduit à un algorithme rapide (en O(n)) pour insérer pn et mettre à jour le diagramme de Vorono¨?. Cet algorithme, proposé par Green et Sibson en 1978 [7], fonctionne de la manière suivante :
21
1. trouver le germe pi tel que pn ? Ci ;
2. tracer la médiatrice du segment pipn et calculer ses intersections x1 et x2 avec la frontière de Ci (il n’y en a que deux car Ci est convexe);
3. x1x2 est, par construction, una arête de Vorono¨? du diagramme de P ; c’est même l’arête séparant Ci de Cn. x2 est lui sur une arête de Vorono¨? du diagramme de Pn?1, séparant Ci d’une autre cellule Cj ;
4. recommencer le processus en remplac¸ant pi par pj ;
5. itérer jusqu’à retomber sur x1 ;
6. on a ainsi construit la frontière de Cn ; mettre à jour les arêtes de Vorono¨? qu’elle intersecte, en supprimant les morceaux à l’intérieur de Cn.
(a) (b)
Fig. 4.1 – Construction incrémentale du diagramme de Vorono¨?. (a) Détection de la cellule Ci contenant pn et construction de la médiatrice de pipn. (b) Construction itérative de la frontière de Cn.
La cellule Cn peut avoir au pire n ? 1 arêtes; le temps de calcul de cette cellule est donc en O(n). Puisqu’il y a n diagrammes de Vorono¨? successifs à calculer, la complexité totale de cet algorithme est en O(n2).
La complexité en O(n2) n’est pas optimale : un algorithme en O(nlogn) a été proposé par Shamos et Hoey dès 1975 [10], avant celui de Green et Sibson. Cependant, cet algorithme n’est jamais utilisé en pratique car trop compliqué à implémenter. Il repose sur la stratégie bien connue “diviser pour régner” (cf. cours d’algorithmique 2 de première année Ensimag) : l’ensemble P est divisé en deux sous-ensembles P1 et P2 de tailles identiques, regroupant les points respectivement les plus “à gauche” et les plus “à droite” du plan. Les diagrammes de Vorono¨? de P1 et de P2 sont calculés récursivement, et toute la difficulté réside ensuite en la fusion de ces deux diagrammes pour obtenir celui de P. Ceci peut être fait en temps linéaire, mais nécessite quelques précautions.
4.4. VORONO¨I : ALGORITHME PAR BALAYAGE
L’algorithme le plus utilisé actuellement pour calculer un diagramme de Vorono¨? est du à Steven Fortune [5]. En effet, il est plus rapide que l’algorithme de Green et Sibson car il calcule un diagramme de Vorono¨? de n points en temps O(nlogn), plus simple que l’algorithme de Shamos et Hoey, et facilement implémentable.
Cet algorithme est dit par balayage car il “balaie” progressivement le plan par une ligne et selon une certaine direction, de telle manière qu’à tout moment, dans la zone déjà balayée, le diagramme de Vorono¨? est construit de manière définitive. Cela peut sembler impossible, car l’apparition d’un nouveau point de P lors du balayage va modifier certaines cellules de Vorono¨? avant ce point (voir figure 4.2). L’idée géniale de Fortune consiste à utiliser une troisième dimension, afin d’“anticiper” les modifications du diagramme (en quelque sorte, de “voir l’avenir”).
Fig. 4.2 – Algorithme par balayage.
Notons ??x et ??y les directions du plan, avec ??x la direction de balayage. A chaque germe pi, on associe le cône Ci de sommet pi, d’axe la troisième direction ??z = ??x ???y , et d’angle (le choix de cet angle est très important!). Intuitivement, si on interprète la direction ??z comme étant le temps, un cône Ci représente un cercle centré sur pi et grossissant à vitesse constante : à z = t0, si on suppose que l’équation du plan est z = 0, son rayon est de t0 (car l’angle est de
L’intersection de deux cônes voisins Ci et Cj sera une branche d’hyperbole, et comme les deux cônes ont même direction et même angle, celle-ci sera incluse dans le plan perpendiculaire au plan z = 0 et portant la médiatrice du segment pipj (voir figure 4.3 (a)). Ainsi, les arêtes de Vorono¨? correspondent aux intersections des cônes, projetées sur le plan z = 0.
L’algorithme proposé par Fortune balaie les cônes de x = ?? à x = +? avec un plan ? incliné de par rapport au plan x = cst (voir figure 4.3 (b)). Le fait que ? ait la même inclinaison que les cônes est très important : ? rencontre un cône Ci exactement quand la droite de balayage
(a) (b) (c)
Fig. 4.3 – Algorithme de Fortune. (a) L’intersection de deux cônes se projette sur la médiatrice du segment reliant les deux germes correspondants. (b) Les cônes sont balayés par un plan ? incliné d’un angle identique à l’angle des cônes. (c) Vue du dessous : l’intersection du plan incliné ? avec l’ensemble des cônes correspond à un front parabolique.
(c’est-a`-dire l’intersection de ? et du plan z = 0) rencontre le germe pi. Ainsi une arête de Vorono¨?, qui correspond à l’intersection de deux cônes voisins Ci et Cj, ne sera créée qu’à partir du moment ou` la droite de balayage a rencontré les deux germes correspondant pi et pj.
L’intersection d’un plan avec un cône étant une parabole, la projection orthogonale sur le plan z = 0 de l’intersection de ? avec l’ensemble des cônes donne ce qu’on appelle un front parabolique (voir figure 4.3 (c)). Le diagramme de Vorono¨? n’est en fait pas construit à tout instant dans toute la zone déjà balayée, mais seulement “à gauche” du front parabolique. La mise à jour du diagramme ne concerne que ce front, qui est de taille O(n), et peut se faire en temps O(nlogn), en représentant le front par un arbre binaire de recherche équilibré (les ajouts et suppressions se font alors en temps O(logn)). On a donc bien un temps de calcul en pire cas en O(nlogn).
La triangulation de Delaunay peut être construite simplement à partir d’un des algorithmes précédents, puisqu’il s’agit du dual du diagramme de Vorono¨?. Il existe néanmoins quelques algorithmes de construction “purement Delaunay”. Nous allons en étudier un à présent.
Cet algorithme, proposé par Guibas, Knuth et Sharir [8], commence avec un triangle p?1p?2p?3 englobant l’ensemble des points de P (voir figure 4.4 (a)). Il construit ensuite la triangulation de
Delaunay de P ?{p?1,p?2,p?3}, puis supprime p?1,p?2,p?3 et les arêtes et triangles incidents en ces trois sommets.
L’approche de Guibas, Knuth et Sharir est incrémentale : supposons la triangulation construite pour m?1 points, et ajoutons un germe pm. pm appartient soit à l’intérieur d’un triangle pipjpk, soit à l’intérieur d’une arête pipl. Dans chacun des cas, nous divisons le ou les triangles incidents (voir figure 4.4 (b)). La triangulation obtenue n’est pas forcément de Delaunay; pour la rendre de Delaunay, il suffit de procéder à des échanges (“flips”) d’arêtes, entre d’un côté les arêtes du triangle ou du quadrilatère entourant pm, et de l’autre côté de nouvelles arêtes partant de
4.5. DELAUNAY : CONSTRUCTION INCREMENTALE´
(a) (b) (c)
Fig. 4.4 – Construction incrémentale de la triangulation de Delaunay. (a) P est englobé dans un triangle p?1p?2p?3. (b) Lors de l’ajout d’un nouveau germe, le ou les triangles incidents sont subdivisés. (c) Flip d’arêtes.
pm (voir figure 4.4 (c)). En effet, une propriété importante de la triangulation de Delaunay dit que parmi les deux triangulations possibles d’un quadrilatère quelconque, une des deux est de Delaunay. Ainsi ici, si un ou des triangles ne vérifient pas la condition de Delaunay, il suffit de les supprimer en échangeant une de leurs arêtes dans un quadrilatère.
Ce qui est assez surprenant, c’est qu’on peut prouver que le nombre total de triangles créés (puis éventuellement détruits) par cet algorithme lors de l’ajout successif de tous les germes est inférieur ou égal à 9n ?1. Ainsi, l’algorithme a un couˆt linéaire en mémoire, et le nombre total d’échanges d’arêtes est également en O(n). L’algorithme est cependant en temps O(nlogn), car il faut ajouter le couˆt des recherches successives de l’emplacement du germe à ajouter pm. Pour cela, la structure de données utilisée est un DAG (graphe orienté sans cycle, cf. cours d’algorithmique 2 de première année Ensimag) : ses feuilles sont les triangles de la triangulation courante, ses nœuds internes les triangles des triangulations précédentes qui ont été détruits (voir figure 4.5). Il est à noter que chaque nœud interne a au plus trois fils, puisqu’un triangle est divisé en au plus trois sous-triangles. Pour savoir dans quel triangle est situé pm, il suffit de parcourir récursivement le DAG en partant de la racine.
Fig. 4.5 – Utilisation d’un DAG pour la construction incrémentale de la triangulation de Delaunay.
Nous présentons maintenant quelques applications pratiques du calcul du diagramme de Vorono¨? et de la triangulation de Delaunay dans le plan.
Supposons que, dans une ville, on connaisse la position de tous les bureaux de Poste (ils sont par exemple indiqués sur une carte), et qu’on doive se rendre d’urgence dans le bureau le plus proche du lieu ou` on se trouve afin de poster un important colis. Comment trouver ce bureau de Poste? Et si on se déplace, quel sera le nouveau bureau de Poste le plus proche? Pour répondre à ces questions, il suffit de calculer le diagramme de Vorono¨? de l’ensemble des bureaux de Poste de la ville : en effet, le bureau de Poste le plus proche sera le germe de la cellule ou` on se trouve au moment ou` on se pose la question. Il est intéressant de noter que le même diagramme de Vorono¨? indiquera également le bureau de Poste le plus proche de toute position : construire un seul diagramme de Vorono¨? suffit.
Dans le cas de la croissance d’un cristal (ou en biologie, d’un ensemble de cellules) à partir de germes, si la croissance se fait de manière uniforme sur les germes, un diagramme de Vorono¨? de ces germes représente l’aspect de l’ensemble des cristaux lorsque la croissance n’est plus possible.
Supposons que l’on dispose d’un robot devant évoluer dans un environnement jalonné d’obstacles ponctuels. Alors, afin de toujours être situé le plus loin possible d’un obstacle, le robot doit se déplacer sur les arêtes du diagramme de Vorono¨? des obstacles (voir figure 4.6 (a)). Il est à noter que des généralisations du diagramme de Vorono¨? existent, qui permettent de traiter le cas d’obstacles non ponctuels (par exemples polygonaux, ou circulaires).
La méthode des éléments finis permet d’approcher une fonction sur un certain domaine du plan, en ne connaissant sa valeur (graˆce à des expérimentations) que sur un ensemble de points P bien précis du domaine. Pour cela, le domaine est décomposé en éléments simples (par exemple des triangles), appelés mailles, délimités par les points de P. La valeur de la fonction en tout autre point du domaine est alors calculée comme combinaison des valeurs aux sommets de la maille à laquelle appartient le point. La triangulation de Delaunay de P est souvent utilisée afin de décomposer le domaine en mailles (figure 4.6 (b)), car elle garantit l’absence de mailles “aplaties” (théorème 40), pour lesquelles le calcul peut être problématique (instabilités, erreurs d’arrondis).
Définition 41 (Arbre couvrant minimal).Etant donné un ensemble P de points du plan, on appelle arbre couvrant minimal (minimum spanning tree) le graphe connexe, sans cycle, dont les sommets sont les points de P, et de longueur minimale (la longueur d’un graphe étant la somme des longueurs de ses arêtes).
4.6. QUELQUES APPLICATIONS
(a) (b)
Fig. 4.6 – (a) Un chemin possible pour un robot souhaitant traverser un champ de mines en étant à chaque instant le plus loin possible d’elles. (b) Méthode des éléments finis : après déformation sous l’effet de forces physiques, les paramètres d’une poutre sont calculés à partir d’expérimentations en différents points et en construisant une triangulation de Delaunay.
Calculer un arbre couvrant minimal est un problème qui arrive fréquemment, par exemple lorsqu’on veut relier plusieurs machines entre elles à travers un réseau informatique, en utilisant le moins de câble possible.
Théorème 42.L’arbre couvrant minimal d’un ensemble de points P du plan est inclus dans sa triangulation de Delaunay.
Démonstration. Il suffit de montrer que toutes les arêtes de cet arbre sont des arêtes de Delaunay. Soit pq une arête de l’arbre couvrant minimal : si on l’enlève, celui-ci est déconnecté (sinon on aurait un autre arbre vérifiant les mêmes hypothèses et de longueur strictement inférieure). Appelons Pp et Pq les points de P appartenant à la partie de l’arbre connectée respectivement à p et à q. Le disque de centre p et de rayon pq ne contient pas de point r de Pq, car dans le cas contraire l’arbre obtenu en remplac¸ant l’arête pq par l’arête pr vérifierait les mêmes hypothèses et serait de longueur strictement inférieure à celle de notre arbre. De manière identique, le disque de centre q et de rayon pq ne contient pas de point de Pp. Comme le disque de diamètre pq est inclus dans l’intersection de ces deux disques, il ne contient aucun point de P en son intérieur, et l’arête pq est donc bien une arête de Delaunay d’après la propriété 39.
Ce théorème conduit à un algorithme très rapide pour calculer l’arbre couvrant minimal. En effet, avant qu’on s’intéresse aux triangulations de Delaunay, le meilleur algorithme connu pour construire l’arbre couvrant minimal d’un ensemble de points était du à Kruskal (1956) et fonctionnait en temps O(n2 logn). En effet, cet algorithme calcule l’arbre couvrant minimal d’un graphe, et le graphe utilisé pour un ensemble quelconque de points était le graphe complet (tous les nœuds sont reliés par des arêtes) :
1. Trier les arêtes du graphe par longueur croissante : e1,e2, pour un graphe complet ? O(n2 logn2) = O(n2 logn)
2. Initialiser l’arbre couvrant minimal ACM à l’ensemble vide.
3. i := 1.
4. Tant qu’il reste des sommets non atteints par ACM faire :
(a) si ACM ? {ei} est sans cycle alors ajouter ei à ACM ;
(b) i := i + 1;
? O(n2) pour un graphe complet
Fig. 4.7 – Un arbre couvrant minimal.
Si on calcule l’arbre couvrant minimal par l’algorithme de Kruskal en remplac¸ant le graphe complet par la triangulation de Delaunay de l’ensemble de points, nous n’avons plus que O(n) arêtes au lieu de O(n2) (propriété 30, et par dualité entre diagramme de Vorono¨? et triangulation de Delaunay). Par conséquent, le tri s’effectue en temps O(nlogn), et la boucle “tant que” en temps O(n). Comme le calcul de la triangulation de Delaunay s’effectue en temps O(nlogn), la complexité totale est en O(nlogn).
Dans de nombreux domaines (C.A.O., imagerie médicale, archéologie, exploration pétrolière, ), on a besoin de reconstituer virtuellement une surface en ne connaissant qu’un certain nombre de points de cette surface. Pour résoudre ce problème, de nombreuses méthodes utilisent la triangulation de Delaunay et le diagramme de Vorono¨?. Une surface ainsi construite est une bonne approximation de la surface de départ, graˆce aux propriétés des triangulations de Delaunay (notamment le théorème 40), et le calcul s’effectue de manière très rapide.
Parmi les méthodes existantes, citons l’algorithme du Crust et du Power Crust de N. Amenta et ses collaborateurs, Cocone et ses successeurs de T.K. Dey, S. Goswami et J. Giesen, ainsi que les algorithmes développés par J.-D. Boissonnat, F. Cazals et leurs collaborateurs à l’INRIA Sophia-Antipolis et implémentés dans la bibliothèque CGAL. Voir [4] pour plus de détails sur cette application.
Chapitre 5
Le diagramme de Vorono¨? a été généralisé de différentes manières. Par exemple, on peut étendre l’ensemble P afin qu’il contienne non plus seulement des points, mais également des segments : le diagramme contiendra une cellule associée à l’intérieur de chaque segment, plus une cellule associée à chaque point, extrémités des segments comprises. Dans ce cas, les arêtes du diagramme sont soit des segments, soit des arcs de parabole (voir figure 5.1 (a)).
(a) (b)
Fig. 5.1 – (a) Diagramme de Vorono¨? de points et segments. (b) Diagramme de Vorono¨? à poids additifs. Les cercles représentent les poids respectifs associés à chaque germe. Certains germes (ceux dont le cercle est en pointillés) ont une cellule associée vide.
On peut également vouloir donner une “influence” différente à chaque point de P. Pour ce faire, on associe un poids wi à chaque point pi. Intuitivement, ceci revient à remplacer chaque germe par une sphère (un disque dans le cas de points du plan) centrée en ce germe et de rayon proportionnel à son poids. Néanmoins, il reste à définir une distance pour ces “germes pondérés”. Les deux solutions les plus simples consistent à définir la distance entre un point quelconque x et un germe pi par respectivement . Les dia-
29
CHAPITRE 5. EXTENSION : DIAGRAMME DE LAGUERRE
grammes correspondant s’appellent respectivement diagramme de Vorono¨? a` poids additifs et diagramme de Vorono¨? a` poids multiplicatifs, et ont été proposés respectivement en 1985 par M. Sharir et en 1984 par F. Aurenhammer et H. Edelsbrunner. Ils sont aussi connus sous le nom générique de diagrammes d’Apollonius, du nom d’un géomètre grec de l’Antiquité (Apollonius de Perge, 262-190 av. J.-C.). La figure 5.1 (b) montre un exemple de diagramme à poids additifs.
Nous allons maintenant nous intéresser à une autre extension du diagramme de Vorono¨?, qui pondère également chaque germe par un poids. Cette extension, qui prend le nom de diagramme de Laguerre (du nom d’un mathématicien franc¸ais du XIXème siècle) ou de diagramme de puissance, a été proposée pour la première fois par F. Aurenhammer en 1987 et est plus utilisée en pratique que les précédentes. La distance associée sera définie par d(x,pi) = ||x ? pi||2 ? wi2.
Il existe des généralisations encore plus complexes du diagramme de Vorono¨?, pour lesquelles on introduit deux poids wi et wi? associés à chaque point (voir [3] pour plus de détails) : d(x,pi) = wi?||x?pi||?wi (diagramme de Vorono¨? à poids composés) ou d(x,pi) = wi?||x?pi||2 ?wi2 (diagramme de M¨obius). Ces diagrammes ont notamment des applications en biologie moléculaire.
Définition 43 (Puissance d’un point).On appelle puissance d’un point x par rapport a` une sphère C de centre c et de rayon r le réel positif défini par ?C(x) = ||x ? c||2 ? r2 = ||x ? t||2(voir figure 5.2 (a)).
Propriété 44.?C(x) < 0 si et seulement si x est intérieur a` la sphère C de centre c et de rayon r.
Définition 45 (Diagramme de Laguerre).Le diagramme de Laguerre (ou diagramme de puissance) associé a` un ensemble de sphères Ci de centres ci et de rayons ri est la décomposition de l’espace euclidien E en cellules Ci associées a` chaque sphère, une cellule Ci contenant l’ensemble des points x de E dont la puissance par rapport a` la sphère Ci est inférieure a` la puissance par rapport aux autres sphères : Ci = {x ? E,?j 6= i,?Ci ? ?Cj}.
Exemple. La figure 5.2 (b) donne un exemple de diagramme de Laguerre associé à quatre sphères. On remarquera qu’une cellule associée à une sphère ne contient pas forcément le centre de cette sphère.
Propriété 46.L’ensemble des points de E qui ont même puissance par rapport a` deux sphères Ci et Cj est un hyperplan.
Démonstration. Soit x un tel point : on a l’égalité ||x ? ci||2 ? ri2 = ||x ? cj||2 ? rj2, ce qui en développant donne x2 ?2x.ci +c2i ?ri2 = x2 ?2x.cj +c2j ?rj2, qui peut se réécrire 2(cj ?ci).x = (c2j ? rj2) ? (c2i ? ri2) : c’est l’équation d’un hyperplan.
Exemple. La figure 5.3 donne trois exemples de tels hyperplans, dans le cas ou` E = R2 (donc ces hyperplans sont des droites).
5.3. PROPRIET´ ES´ 31
(a) (b)
Fig. 5.2 – (a) Puissance d’un point par rapport à une sphère. (b) Diagramme de Laguerre.
Fig. 5.3 – Trois exemples de droites des points ayant même puissance par rapport à deux sphères.
Contrairement aux trois types de diagrammes de Vorono¨? étendus présentés en introduction de ce chapitre, les cellules d’un diagramme de Laguerre ressemblent aux cellules de Vorono¨?.
Propriété 47.Une cellule du diagramme de Laguerre est soit vide, soit un polytope convexe, éventuellement non borné.
Démonstration. Dans le cas ou` une cellule Ci est non vide, son intersection avec toute autre cellule étant un hyperplan, Ci est une intersection de demi-espaces, et est donc convexe.
Comme dit en introduction, le diagramme de Laguerre est plus utilisé en pratique que les autres extensions du diagramme de Vorono¨?. Cela est principalement du au résultat suivant, qui montre qu’un diagramme de Laguerre peut représenter des choses très générales.
Définition 48 (Diagramme affine).Soient P un ensemble fini d’objets dans un espace euclidien Rn et d une fonction continue entre n’importe quel point de Rn et P (d n’est pas nécessairement une distance : en particulier, l’inégalité triangulaire n’est pas requise). Supposons que, quelques soient les objets Oi et Oj de P, l’ensemble des points x de Rn tels que d(x,Oi) = d(x,Oj) est un hyperplan. On appelle diagramme affine de P la partition de Rn en cellules Ci regroupant les points de Rn dont la valeur pour d par rapport a` Oi est inférieure a` la valeur pour d par rapport a` tous les autres objets Oj.
Théorème 49 (Aurenhammer, 1987).Tout diagramme affine de Rn est le diagramme de Laguerre d’un ensemble de sphères de Rn.
32 CHAPITRE 5. EXTENSION : DIAGRAMME DE LAGUERRE
|
English |
Franc¸ais |
|
Cell |
Cellule |
|
Circumcircle |
Cercle circonscrit |
|
Connected |
Connexe |
|
Convex hull |
Enveloppe convexe |
|
Cross cap |
Bonnet croisé |
|
Divide and conquer |
Diviser pour régner |
|
Edge |
Arête |
|
To embed |
Plonger |
|
Embedding |
Plongement |
|
Genus |
Genre |
|
Link |
Lien |
|
Manifold |
Variété |
|
Manifold with boundary |
Variété à bord |
|
Minimum spanning tree |
Arbre couvrant de poids minimal |
|
Polyhedron |
Polyèdre |
|
Seed |
Germe |
|
Simplex |
Simplexe |
|
Simplices |
Simplexes |
|
Simplicial complex |
Complexe simplicial |
|
Star |
Etoilé |
|
To sweep |
Balayer |
|
Vertex |
Sommet |
|
Vertices |
Sommets |
33
34 CHAPITRE 5. EXTENSION : DIAGRAMME DE LAGUERRE
[1] M. de Berg, M. van Kreveld, M. Overmars, O. Schwarzkopf. Computational Geometry : Algorithms and Applications. Springer-Verlag, 2000.
[2] J.-D. Boissonnat, M. Yvinec. Géométrie Algorithmique. Ediscience International, 1995.
[3] J.-D. Boissonnat, C. Wormser, M. Yvinec. Curved Voronoi diagrams. in Effective Computational Geometry for Curves and Surfaces, Springer, 2006.
[4] T.K. Dey. Curve and Surface Reconstruction : Algorithms with Mathematical Analysis. Cambridge University Press, 2006.
[5] S. Fortune. A Sweepline Algorithm for Voronoi Diagrams. Symposium on Computational Geometry, p. 313-322, 1986. Egalement dans Algorithmica, vol. 2, p. 153-174, 1987.
[6] J. Goodman, J. O’Rourke eds. Handbook of Discrete and Computational Geometry. CRC Press, 1997.
[7] P. J. Green, R. R. Sibson. Computing Dirichlet Tessellations in the Plane. Computer Journal, vol. 21 nr 2, p. 168-173, 1978.
[8] L. Guibas, D. Knuth, M. Sharir. Randomized Incremental Construction of Delaunay and Voronoi Diagrams. Algorithmica, vol. 7, p. 381-413, 1992.
[9] J. O’Rourke. Computational Geometry in C. Cambridge University Press, 1998.
[10] M. Shamos, D. Hoey. Closest-Point Problems. 16th Annual Symposium on Foundations of Computer Science, p. 151-162, 1975.
[11] Computational Geometry Algorithms Library (CGAL).
35
Un bonnet croisé (cross cap en anglais) est une surface sans bord analogue à un ruban de M¨obius (figure 2.2)
[2] En fait, on peut même montrer que cet algorithme est optimal : il existe une certaine configuration de n points pour laquelle n’importe quel algorithme aura besoin d’un temps au moins proportionnel à nlogn pour calculer le diagramme de Vorono¨? des n points.
En faisant une hypothèse de randomisation : au niveau de l’ordre d’insertion des points, toutes les permutations sont supposées équiprobables, et le temps est calculé en moyenne.
Evidemment, P est ici un ensemble de points de R3, et non plus du plan.
http
