INF562Introduction a la geometrie algorithmique et ses applicationsLuca Castelli Aleardi et Steve Oudotfevrier 2020Table des matieresI Les fondamentaux de la geometrie algorithmique 11 Geometrie discrete et algorithmique: introduction 31.
1) Graphes, cartes et maillages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.1. 1) Graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.1. 2) Cartes et subdivisions planaires . . . . . . . . . . . . . . . . . . . . . . . . 31.1. 3) Arbres . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.1. 4) Triangulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51.1. 5) Complexes et maillages . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51. 2) Formule d'Euler en dimension 2 . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61. 3) Representations de donnees geometriques . . . . . . . . . . . . . . . . . . . . . . 91.3. 1) Structures de donnees abstraites pour la geometrie . . . . . . . . . . . . . 91.3. 2) Quelques structures de donnees pour les maillages . . . . . . . . . . . . . 91.3.2. 1) Maillages surfaciques (polygonaux): Half-edge . . . . . . . . . . 101.3.2. 2) Une structure de donnees pour les triangulations . . . . . . . . . 101.3.2. 3) Quad-edge data structure . . . . . . . . . . . . . . . . . . . . . . 101. 4) Un probleme classique: localisation planaire . . . . . . . . . . . . . . . . . . . . . 111. 5) Geometrie convexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131.5. 1) Coordonnees barycentriques . . . . . . . . . . . . . . . . . . . . . . . . . . 131.5. 2) Enveloppes anes, enveloppes convexes . . . . . . . . . . . . . . . . . . . 131.5. 3) Theoremes fondamentaux: Radon, Helly et Caratheodory . . . . . . . . . 141.5. 4) Existence de center points . . . . . . . . . . . . . . . . . . . . . . . . . . . 161.5. 5) Combinatoire des Polytopes . . . . . . . . . . . . . . . . . . . . . . . . . . 171. 6) Enveloppes convexes en 2D: algorithmes et complexite . . . . . . . . . . . . . . . 171.6. 1) Algorithme de Jarvis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 181.6. 2) Approche par balayage : l'algorithme de Graham-Andrew . . . . . . . . . 181.6. 3) Approche parDivision-Fusion. . . . . . . . . . . . . . . . . . . . . . . . 201.6. 4) Borne inferieure sur la complexite . . . . . . . . . . . . . . . . . . . . . . 221. 7) Enveloppes convexes en dimension superieure . . . . . . . . . . . . . . . . . . . . 221. 8) Arrangements de droites dans le plan . . . . . . . . . . . . . . . . . . . . . . . . . 231.
9) Robustesse des algorithmes geometriques . . . . . . . . . . . . . . . . . . . . . . . 242 Triangulations de Delaunay et diagrammes de Vorono 292.
1) Denitions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292.1. 1) Triangulations de Delaunay . . . . . . . . . . . . . . . . . . . . . . . . . . 302.1. 2) Diagrammes de Vorono . . . . . . . . . . . . . . . . . . . . . . . . . . . . 312. 2) Quelques proprietes remarquables . . . . . . . . . . . . . . . . . . . . . . . . . . . 312.2. 1) Localement Delaunay contre globalement Delaunay . . . . . . . . . . . . . 312.2. 2) Optimisation de l'angle minimal et de la sequence des angles . . . . . . . 332.2.
3) Arbre couvrant minimal . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34iii Luca Castelli Aleardi & Steve Oudot2.
3) Taille et calcul de la triangulation de Delaunay . . . . . . . . . . . . . . . . . . . 352.3. 1) Taille de la triangulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 352.3. 2) Calcul de la triangulation . . . . . . . . . . . . . . . . . . . . . . . . . . . 362.
4) Extensions et notes bibliographiques . . . . . . . . . . . . . . . . . . . . . . . . . 393 Aspects geometriques des graphes (planaires) 433.
1) Introduction et motivations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 433. 2) Graphes: le point de vue combinatoire . . . . . . . . . . . . . . . . . . . . . . . . 433.2. 1) Cartes (planaires ou plongees sur des surfaces) . . . . . . . . . . . . . . . 433.2. 2) Graphes et 3-connexite. . . . . . . . . . . . . . . . . . . . . . . . . . . . . 453. 3) Deux celebres caracterisations des graphes planaires . . . . . . . . . . . . . . . . 463.3. 1) Theoreme de Kuratowski . . . . . . . . . . . . . . . . . . . . . . . . . . . 463.3. 2) Theoreme de Koebe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 473. 4) Theorie algebrique des graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 513. 5) Dessin de graphes planaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 523.5. 1) Representation d'un graphe dansRd. . . . . . . . . . . . . . . . . . . . . 523.5. 2) Representations convexes et methode de Tutte . . . . . . . . . . . . . . . 533.5.2. 1) Matrice laplacienne et methode de Tutte . . . . . . . . . . . . . 553.5. 3) Dessiner un graphe en minimisant son energie . . . . . . . . . . . . . . . . 573.5.3. 1) Dessin spectral . . . . . . . . . . . . . . . . . . . . . . . . . . . . 573.5. 4) Dessins sur une grille et methode de Schnyder . . . . . . . . . . . . . . . . 593.5. 5) Preuve du Theoreme barycentrique de Tutte (Lemme 3.21) . . . . . . . . 613.5. 6) Notes bibliographiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 633. 6) Graphes et petits separateurs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 633.6. 1) Separateurs et graphes planaires . . . . . . . . . . . . . . . . . . . . . . . 643.6. 2) Separateurs geometriques . . . . . . . . . . . . . . . . . . . . . . . . . . . 663. 7) Applications algorithmiques des separateurs . . . . . . . . . . . . . . . . . . . . . 683.7. 1) Localisation planaire . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 683.7.
2) Compression et codage de graphes . . . . . . . . . . . . . . . . . . . . . . 69II Les developpements plus recents 734 Reconstruction de formes geometriques 754.
1) Reach d'une forme geometrique . . . . . . . . . . . . . . . . . . . . . . . . . . . . 764. 2) Triangulation de Delaunay restreinte . . . . . . . . . . . . . . . . . . . . . . . . . 794. 3) Complexe de temoins et reconstruction multi-echelles . . . . . . . . . . . . . . . . 814.3. 1) Le complexe de temoins . . . . . . . . . . . . . . . . . . . . . . . . . . . . 824.3. 2) L'algorithme de reconstruction multi-echelles . . . . . . . . . . . . . . . . 844.3. 3) Correction de l'algorithme . . . . . . . . . . . . . . . . . . . . . . . . . . . 854.
4) Extensions et notes bibliographiques . . . . . . . . . . . . . . . . . . . . . . . . . 885 Problemes de proximite 935.
1) Localisation planaire en petite dimension . . . . . . . . . . . . . . . . . . . . . . 935.1. 1) Methode du Slab . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 935.1. 2) Triangulations hierarchiques . . . . . . . . . . . . . . . . . . . . . . . . . . 945. 2) Range searching et recherche du plus proche voisin . . . . . . . . . . . . . . . . . 965.2. 1) Range trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 975.2.1. 1) Orthogonal Range Search en dimension superieure . . . . . . . . 995.2.1.
2) Amelioration: Fractional Cascading . . . . . . . . . . . . . . . . 99INF562 { Introductiona la geometrie algorithmique et ses applicationsiii5.2.2 kd-trees: plus proche voisin . . . . . . . . . . . . . . . . . . . . . . . . . . 1006 Algorithmes d'approximation geometrique 1056.
1) Quelques mots sur la complexite des algorithmes . . . . . . . . . . . . . . . . . . 1056. 2) Le probleme du voyageur de commerce . . . . . . . . . . . . . . . . . . . . . . . . 1076.2. 1) Metric-TSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1086.2. 2) Euclidean-TSP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1106.2.2. 1) Renormalisation et projection . . . . . . . . . . . . . . . . . . . 1116.2.2. 2) Construction du quadtree . . . . . . . . . . . . . . . . . . . . . . 1116.2.2. 3) Mise en place des portails . . . . . . . . . . . . . . . . . . . . . . 1126.2.2. 4) Calcul du plus court cycle polygonal respectant les portails . . . 1126.2.2. 5) Modication du cycle polygonal en cycle hamiltonien surP. . . 1166.2.2.
6) Final . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116iv Luca Castelli Aleardi & Steve OudotTable des gures1.
1) Graphes et cartes planaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41. 2) Subdivisions planaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51. 3) Triangulations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61. 4) Formule d'Euler pour les graphes planaires . . . . . . . . . . . . . . . . . . . . . 71. 5) Operations d'Euler . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91. 6) Representation avec demi-ar^etes . . . . . . . . . . . . . . . . . . . . . . . . . . . . 101. 7) Representation de maillages triangulaires . . . . . . . . . . . . . . . . . . . . . . 111. 8) Quad-Edge data structure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121.
9) Localisation par marche aleatoire . . . . . . . . . . . . . . . . . . . . . . . . . . . 121.10 Coordonnees barycentriques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131.11 Theoreme de Radon . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141.12 Theoreme Helly . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 151.13 Theoreme du center point . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161.14 Enveloppe convexe: algorithme par balayage de Graham-Andrew . . . . . . . . . 191.15 Enveloppe convexe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 211.16 Enveloppe convexe 3D . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231.17 Executions erronees de l'algorithme de Jarvis . . . . . . . . . . . . . . . . . . . . 252.
1) Diagramme de Vorono et triangulation de Delaunay duale . . . . . . . . . . . . . 322. 2) Pour les preuves des theoremes 2.7 et 2.9 . . . . . . . . . . . . . . . . . . . . . . 332.
3) Insertion d'un sommet dans une triangulation de Delaunay . . . . . . . . . . . . 372.4 Zone de conit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 383.
1) Maillages, surfaces discretes et graphes planaires . . . . . . . . . . . . . . . . . . 443. 2) Cartes combinatoires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 453. 3) Graphes et cartes planaires . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 463. 4) Cartes planaires enracinees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 463. 5) Representation de Koebe-Andreev-Thurston de graphes planaires . . . . . . . . . 473. 6) Theoreme de Koebe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 483. 7) Preuve du theoreme de Koebe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 493. 8) Matrice d'adjacence et matrice laplacienne . . . . . . . . . . . . . . . . . . . . . . 513.
9) Representation d'un graphe . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 523.10 Methode barycentrique de Tutte . . . . . . . . . . . . . . . . . . . . . . . . . . . 533.11 Theoreme barycentrique de Tutte . . . . . . . . . . . . . . . . . . . . . . . . . . . 553.12 Dessin spectral de graphes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 583.13 For^ets de Schnyder . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 603.14 Interpretation geometrique des for^ets de Schnyder . . . . . . . . . . . . . . . . . 603.15 Separateurs de graphes planaires . . . . . . . . . . . . . . . . . . . . . . . . . . . 643.16 Separateurs de graphes planaires . . . . . . . . . . . . . . . . . . . . . . . . . . . 65vvi Luca Castelli Aleardi & Steve Oudot3.17 Theoreme de Koebe sur la sphere . . . . . . . . . . . . . . . . . . . . . . . . . . . 663.18 Separateurs geometriques et theoreme de Koebe . . . . . . . . . . . . . . . . . . 674.
1) Processus de numerisation d'un objet en 3d . . . . . . . . . . . . . . . . . . . . . 754. 2) Quelques formes geometriques et leurs axes medians . . . . . . . . . . . . . . . . 774. 3) Quelques formes geometriques a reach positif ou nul . . . . . . . . . . . . . . . . 784. 4) Delaunay restreint a une courbe plane . . . . . . . . . . . . . . . . . . . . . . . . 804. 5) Quelques nuages de points representant des structures multi-echelles . . . . . . . 814. 6) Sequence de reconstructions produite par l'algorithme de Guibas et Oudot . . . . 824. 7) Denition du complexe de temoins . . . . . . . . . . . . . . . . . . . . . . . . . . 834. 8) Premieres etapes de l'algorithme de Guibas et Oudot . . . . . . . . . . . . . . . . 854.
9) Diagramme d'evolution des nombres de Betti . . . . . . . . . . . . . . . . . . . . 864.10 Pour la preuve du lemme 4.14 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 864.11 Complexe de temoins sur une surface . . . . . . . . . . . . . . . . . . . . . . . . . 895.
1) Point location: methode du slab . . . . . . . . . . . . . . . . . . . . . . . . . . . . 945. 2) Triangulations hierarchiques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 955. 3) Range search en dimension 1 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 975. 4) Range Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 985.
5) Fractional cascading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 995.6kd-trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1016.
1) Etapes de l'algorithme de Christodes . . . . . . . . . . . . . . . . . . . . . . . . 1096. 2) Etapes de l'algorithme d'Arora . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1116. 3) Le quadtree construit par l'algorithme d'Arora . . . . . . . . . . . . . . . . . . . 1126. 4) Pour la preuve du lemme 6.7 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1136.
5) La table de requ^etes construite par l'algorithme d'Arora . . . . . . . . . . . . . . 115Premiere partieLes fondamentaux de la geometriealgorithmique1Chapitre 1Geometrie discrete etalgorithmique : introduction1.
1) Quelques notions sur les graphes, cartes et maillagesIci nous essayons de fournir des notions precises et de clarier les dierences et pointscommuns entre graphes, cartes et maillages, compte tenu des themes et domaines divers abordesdans cet ouvrage.
Nous proposons egalement des algorithmes et des structures de donneesqui, dans la mesure du posible, peuvent s'appliquer indistinctement aux trois types d'objetsmentionnes ci-dessus, ou tout du moins aux cartes et maillages qui, du point de vue combinatoireet en faisant abstraction des proprietes geometriques, peuvent representer dierents aspects d'unm^eme objet.1.1.
1) GraphesDenition 1.1.UngrapheG= (V;E)est une paire constituee de :| un ensemble desommetsV= (v1;:::;vn)| une familleE= (e1;:::;em)d'elements du produit cartesienVV=f(u;v)ju2V;v2Vgappelesar^etes.Uneboucleest une ar^ete dont les extremites concident (u=v).
Si une ar^ete appara^tplusieurs fois dansEalors il s'agit d'unear^ete multiple. Un graphe est ditsimples'il ne contientpas d'ar^etes multiples ni de boucles. Un graphe estk-connexes'il faut supprimer au moinsksommets pour qu'il ne soit plus connexe.1.1.
2) Cartes et subdivisions planairesBien que deja interessants d'un point de vue algorithmique, les graphes ne susent pas acapturer les proprietes d'objets communs en geometrie.
Par exemple, dans le cas des maillages,il est usuel de parler de "faces", notion qui n'appara^t pas dans la denition de graphe donneeprecedemment.Denition 1.2.Etant donne un grapheG, undessin planaireest un plongement cellulaire deGdansR2, qui satisfait les conditions suivantes :(i)les sommets du graphe sont representes par des points;(ii)les ar^etes sont representees par des arcs de courbes ne se coupant qu'aux sommets;(iii)le complementS n Gest une union disjointe de regions appeleesfaces, ne contenant nisommets ni ar^etes, qui ont toutes sauf une l
