Version classiqueVersion mobile

Géométrie algorithmique : des données géométriques à la géométrie des données

 | 
Jean-Daniel Boissonnat

Géométrie algorithmique : des données géométriques à la géométrie des données

Leçon inaugurale prononcée le jeudi 23 mars 2017

Jean-Daniel Boissonnat

Texte intégral

1L’un des plus grands géomètres du xxe siècle, Harold Coxeter, écrivait en 1967 :

La géométrie possède encore l’attrait esthétique qu’elle a toujours eu, et la beauté de ses résultats ne s’est pas estompée. En fait, elle est plus utile et même plus nécessaire aux savants et aux mathématiciens qu’elle ne le fut jamais.

Au cours des siècles, la géométrie s’est développée. De nouveaux concepts, de nouvelles méthodes d’action furent forgés. Par les moyens qui nous conviendront le mieux, revenons donc à Euclide ; et découvrons quelques-uns des plus récents résultats. Peut-être pourrons-nous, ainsi, retrouver un peu de l’intimidation émerveillée que suscita en nous le premier contact avec la géométrie.

2Quel plus bel endroit que le Collège de France pour répondre à l’invitation d’Harold Coxeter et présenter un nouveau développement de la géométrie ?

  • 1 Computational geometry en anglais.
  • 2 Michel Serres, Les Origines de la géométrie : tiers livre des fondations, Paris, Flammarion, 1993.

3Le sujet de ce cours, que les professeurs du Collège me font l’honneur de me confier, est la géométrie algorithmique1. La géométrie, dont les origines se confondent avec celles de l’humanité2, ne pouvait pas ignorer les évolutions spectaculaires de l’informatique et des sciences numériques décrites ici même par Gérard Berry et mes prédécesseurs à cette chaire. Cette leçon inaugurale est une invitation à découvrir le rôle que la géométrie joue dans notre monde devenu numérique et quelques-unes des questions émergeant du rapprochement de la géométrie et de l’informatique.

1. Les origines de la géométrie algorithmique

La conception assistée par ordinateur

4L’histoire de la géométrie algorithmique commence dans les années 1970 avec la conception assistée par ordinateur (CAO). Il s’agit de résoudre un problème industriel : créer un outil informatique simple qui permette aux dessinateurs de modéliser des surfaces en trois dimensions (3D), comme des carrosseries de voitures, et qui facilite la programmation des machines à commande numérique. Deux ingénieurs français, Pierre Bézier, qui travaillait chez Renault, et Paul de Casteljeau, qui travaillait chez Citroën, fondent le sujet. Leurs contributions sont majeures : les courbes et les surfaces de Bézier, ainsi que les algorithmes de Casteljeau qui les construisent, sont universellement utilisés aujourd’hui.

  • 3 Nicholas Ayache, Des images médicales au patient numérique, Paris, Collège de France/Fayard, coll. (...)
  • 4 Marie-Paule Cani, Façonner l’imaginaire : de la création numérique 3D aux mondes virtuels animés, (...)

5En utilisant l’informatique, science de l’immatériel, les ingénieurs ont franchi un pas décisif : la CAO s’affranchit des maquettes physiques, lourdes et encombrantes, et des représentations 2D réductrices – plans, dessins industriels, coupes ou projections. Elle leur substitue une véritable représentation 3D, virtuelle mais effective. Ces nouveaux modèles objectivent la représentation de formes tridimensionnelles et en simplifient radicalement le traitement, la reproduction et la transmission. Ils ouvrent de nouveaux champs d’application aux créateurs de formes tridimensionnelles – ingénieurs, médecins3 ou artistes4.

L’invention de la numérisation 3D

6Une deuxième étape décisive dans le développement de la modélisation 3D fut l’invention de capteurs permettant de numériser des formes tridimensionnelles. Permettez-moi d’évoquer un souvenir personnel. C’était en 1980 à l’Iria, l’Institut de recherche en informatique et en automatique, alors dirigé par Jacques-Louis Lions. Je venais d’être recruté comme chercheur dans le groupe de François Germain. Avec Georges Kryzé, François Germain avait inventé un capteur 3D novateur pour l’époque. Ce capteur comportait un faisceau laser dont la direction était contrôlée à l’aide de deux miroirs, et de trois caméras linéaires qui repéraient le point éclairé par le laser, ce qui permettait de calculer par triangulation les coordonnées dans l’espace du point éclairé. Plus besoin de palpeurs et de systèmes mécaniques complexes ; pour la première fois, un système simple, rapide et précis permettait de mesurer des formes tridimensionnelles.

  • 5 Monique Sicard, La Fabrique du regard. Images de science et appareils de vision (xve-xxe siècle), (...)

7Les progrès de la numérisation 3D ont ensuite été spectaculaires. Des descendants du prototype de F. Germain et G. Kryzé se trouvent aujourd’hui sur les étagères de grandes surfaces et seront bientôt intégrés dans nos téléphones portables. De nombreux autres systèmes de numérisation 3D ont été inventés, révolutionnant de nombreuses applications : la tomographie, très utilisée en imagerie médicale ainsi qu’en géophysique, en astrophysique et en mécanique des matériaux ; la télédétection par laser (Lidar) ; la microscopie confocale, couramment utilisée en biologie et en science des matériaux ; la cryomicroscopie électronique qui permet d’étudier la structure de complexes macromoléculaires. On mesure aujourd’hui de façon routinière des formes tridimensionnelles, de l’échelle atomique à l’échelle astronomique, donnant ainsi accès à une dimension inaccessible à l’œil humain. Cette « fabrique du regard » en 3D (pour reprendre l’expression de Monique Sicard5) ouvre des applications inédites. Le monde numérique n’est maintenant plus limité au texte, au son et aux images, et les représentations numériques de formes tridimensionnelles jouent un rôle central dans de très nombreux domaines. Citons, parmi bien d’autres, l’ingénierie, la cartographie, le cinéma et les jeux vidéo, l’architecture, la préservation du patrimoine culturel, l’exploration pétrolière, la médecine ou encore la conception de médicaments.

La question de la complexité algorithmique

8L’approche des ingénieurs de la CAO est avant tout destinée à la modélisation de formes relativement simples. Elle est bien résumée par la jolie expression « Formes et formules ». Mais elle ne permet pas de modéliser les formes complexes de la nature ou les statues de Michel-Ange. L’apparition de données 3D va changer la perspective. Les formes sont très variées, les données massives : plusieurs millions de points peuvent être nécessaires pour représenter précisément un objet complexe. La taille des données et la complexité des algorithmes deviennent alors critiques.

9Ces questions sont au centre de la thèse que Michael Shamos soutient à Yale en 1978 et qu’il intitule Computational Geometry. M. Shamos est un théoricien de l’algorithmique qui veut étudier les interactions entre géométrie et calcul. Son objectif est de fonder un nouveau sujet en étudiant de manière systématique les problèmes géométriques du point de vue algorithmique. Voici un extrait de la préface de sa thèse :

Cette thèse examine les questions qui se posent quand on cherche à résoudre des problèmes géométriques avec un ordinateur, ce qui nous oblige à considérer des aspects du calcul géométrique qui ne sont simplement pas abordés par les mathématiques classiques. De nouvelles méthodes sont requises.

  • 6 La notation ignore la constante de proportionnalité pour mettre en évidence l’ordre de grandeur de (...)

10Un problème résolu par M. Shamos va permettre de comprendre sa démarche. Il s’agit de trouver dans un ensemble de n points du plan les deux points qui sont les plus proches. C’est une question en apparence simple. Il suffit de considérer tous les segments reliant deux points et de retenir le plus court. Comme il y a n × (n − 1) / 2 paires de points, cet algorithme naïf a une complexité quadratique. L’algorithme de Shamos évite de calculer toutes les paires et effectue un nombre d’opérations élémentaires proportionnel à n log n. On dit que sa complexité est en O (n log n)6. Le temps de calcul se trouve divisé par un facteur considérable quand n est grand : par exemple, si n = 10 000 000 (le nombre de pixels dans un appareil photo ordinaire), le temps de calcul passe de la semaine à la seconde.

2. Structures de données géométriques

11À la différence des images numériques, les données 3D sont peu ou pas structurées car les informations qu’on peut recueillir sur une forme 3D ne sont en général que partielles et il est nécessaire de combiner les données acquises de plusieurs points de vue : Flatland, le chef d’œuvre d’Edwin Abbott, est une démonstration pédagogique brillante de cette limitation. Si la thèse de M. Shamos ne répond pas à la question de la modélisation des formes géométriques 3D à partir de mesures, elle va fournir quelques clés essentielles à travers la définition et la construction de structures de données géométriques. En informatique, une structure de données est une manière d’organiser les données en un modèle interne qui permet de les traiter plus facilement. Cette notion n’est pas très éloignée de celle de la représentation en psychologie et du modèle interne en neurosciences. Notre cerveau est prodigieusement doué pour cartographier notre environnement et en construire des représentations internes qui vont lui permettre de planifier des actions. C’est ce que fait un enfant qui apprend à marcher. C’est aussi ce que fait un chirurgien qui regarde des images tomographiques et doit, à partir de ces images bidimensionnelles, construire une représentation mentale tridimensionnelle de l’organe qu’il va opérer.

  • 7 Marc Jeannerod, Le Cerveau volontaire, Paris, Odile Jacob, 2009.

12Peut-on imaginer construire in silico des représentations qui intègrent les mesures géométriques aujourd’hui disponibles et permettent d’effectuer des calculs efficacement, reprenant le schéma représentation-plan-programme que décrit Marc Jeannerod dans son livre Le Cerveau volontaire7 ?

13Un des succès de la géométrie algorithmique est d’avoir identifié et étudié quelques structures géométriques discrètes fondamentales qui vont permettre de structurer les données.

Polyèdres convexes, mosaïques et triangulations

14Un premier exemple d’une telle structure géométrique discrète est celui des polyèdres convexes, qui sont connus depuis la Haute Antiquité et n’ont cessé depuis de fasciner les plus brillants mathématiciens, comme l’attestent les gravures de Léonard de Vinci et de Johannes Kepler. Représenter le monde qui nous entoure avec des polyèdres convexes peut sembler outrageusement réducteur et réservé aux amateurs de beauté formelle. Pourtant, comme on le verra plus loin, les polyèdres convexes jouent un rôle central en modélisation géométrique. On peut y voir un nouvel exemple de la déraisonnable efficacité des mathématiques dans les sciences.

15Un deuxième exemple de modèle géométrique discret est celui des diagrammes (ou mosaïques) de Voronoï, du nom du mathématicien ukrainien Georges Voronoï. En mathématiques, un diagramme de Voronoï est un découpage en cellules à partir d’un ensemble fini de points qu’on va appeler « germes », les points rouges sur la figure 1. Chaque cellule enferme un seul germe, et forme l’ensemble des points du plan plus proches de ce germe que des autres. Les diagrammes de Voronoï représentent des relations de proximité et permettent de modéliser des phénomènes de croissance en toutes dimensions. Bien avant Voronoï, Descartes les avait dessinés pour décrire le système solaire. Les diagrammes de Voronoï ont été utilisés (sous différents noms) pour modéliser des territoires en écologie, en épidémiologie et en sciences humaines. Les géographes peuvent les observer sur le sol plat du salar d’Uyuni, les zoologistes sur le dos des girafes réticulées et les carapaces des tortues, les botanistes sur les méristèmes, les chimistes dans les mousses.

Figure 1

Figure 1

Le diagramme de Voronoï d’un ensemble fini de germes (à gauche) et la triangulation de Delaunay duale (à droite).

16Les triangulations sont un troisième exemple de modèle géométrique discret universel, au cœur de l’interaction entre géométrie et calcul. En approchant la géométrie des objets par des assemblages de simplexes – triangles, tétraèdres, ou leurs analogues en dimensions supérieures –, les triangulations permettent de visualiser les objets, de faire des calculs sur ces objets, de résoudre des équations aux dérivées partielles, de simuler numériquement des phénomènes physiques. Pour des besoins très différents et avec des contraintes qui leur sont propres, l’analyse numérique, l’informatique graphique, la robotique triangulent leurs objets d’étude – espaces fonctionnels, mondes virtuels ou espaces de configuration.

  • 8 Boris Delaunay, « Sur la sphère vide », Izvestia Akadademia Nauk SSSR, Otdelenie Matematicheskii i (...)

17Un ensemble de points admet de très nombreuses triangulations. L’une d’elles se détache par la richesse de ses propriétés mathématiques et de ses applications. C’est la triangulation de Delaunay8, définie en 1934 par Boris Delaunay, un mathématicien russe qui a dédié son article fondateur à Georges Voronoï. La triangulation de Delaunay est duale du diagramme de Voronoï ; dont elle se déduit de celui-ci en reliant les germes dont les cellules de Voronoï partagent une arête (fig. 1).

18Une correspondance très utile peut être établie entre diagrammes de Voronoï, triangulations de Delaunay et polyèdres convexes. Il faut, pour cela, quitter l’espace de départ qui contient les points de données et se placer dans un espace qui a une dimension de plus. Le diagramme de Voronoï de n points du plan apparaît alors comme la projection d’un polyèdre convexe, intersection de n demi-espaces de l’espace à trois dimensions (fig. 2). Et la triangulation de Delaunay de ces mêmes points apparaît comme la projection d’un polyèdre convexe dual. Ce polyèdre est défini en relevant les points de départ dans cet espace de dimension 3, et en prenant leur enveloppe convexe, c’est-à-dire le plus petit convexe qui les contient. Ainsi les diagrammes de Voronoï et les triangulations de Delaunay du plan ne sont que des polyèdres convexes de dimension 3 déguisés. De même, les diagrammes de Voronoï et les triangulations de l’espace de dimension 3 sont la projection de polyèdres de dimension 4. D’une manière générale, la construction d’une triangulation de Delaunay dans l’espace de dimension d ou, par dualité, d’un diagramme de Voronoï, se ramène à la construction d’une enveloppe convexe en dimension d + 1. Il est donc important de pouvoir construire efficacement des enveloppes convexes de points, et de pouvoir le faire au-delà de la dimension 3.

Figure 2

Figure 2

Correspondance entre diagrammes de Voronoï, triangulations de Delaunay et polyèdres convexes.

Algorithmes

19Une enveloppe convexe de n points de l’espace à deux dimensions est une suite d’au plus n arêtes reliées par des points de données. Pour la calculer, le mathématicien Ronald Graham a proposé un algorithme optimal très simple qui pourrait être étudié dans les collèges. On commence par ordonner les points autour d’un point central, ce qui forme un polygone qui passe par tous les points. On parcourt ce polygone dans le sens trigonométrique à partir de son point le plus à gauche. On avance tant qu’on tourne à gauche. Si on tourne à droite, on recule en éliminant le sommet concave. Il est facile de voir que la complexité de cet algorithme est O (n log n). En effet, il est bien connu que la complexité du tri initial est O(n log n). Le coût du parcours qui suit est linéaire puisque soit on avance le long du polygone, soit on recule, et, dans ce cas, on supprime un point qu’on n’examinera plus.

  • 9 Peter McMullen, « The maximum numbers of faces of a convex polytope », Mathematika, vol. 17, no 2, (...)

20La situation se complique un peu en dimension 3. Une enveloppe convexe de points est un assemblage de facettes (en général triangulaires) attachées par des arêtes qui elles-mêmes ont pour extrémités des points de données. Combien y a-t-il d’arêtes et de facettes ? La réponse à cette question est donnée par la fameuse formule d’Euler : s − a + f = 2 qui relie les nombres de sommets s, d’arêtes a et de facettes f de tout polyèdre convexe. On peut en déduire facilement que les nombres d’arêtes et de faces dépendent linéairement du nombre de sommets. On dira que la complexité combinatoire de l’enveloppe convexe est linéaire. On déduit de la correspondance vue plus haut que la complexité combinatoire du diagramme de Voronoï de points du plan est linéaire, et il en va de même par dualité pour la triangulation de Delaunay. Il faut faire un saut dans le temps de plus de 200 ans pour que ces résultats soient étendus en toutes dimensions et pour borner la complexité combinatoire d’un polyèdre convexe de dimension d qui a n sommets. Comme le montre Peter McMullen en 19719, les polyèdres convexes voient leurs nombres de faces (de toutes dimensions, de 0 jusqu’à d − 1) croître de manière exponentielle avec la dimension d de l’espace ambiant. On en déduit que la complexité des diagrammes de Voronoï et des triangulations est quadratique en dimension 3 dans le pire cas, et qu’elle croît de manière exponentielle avec la dimension d de l’espace, ce qui est une difficulté majeure si on veut utiliser les diagrammes de Voronoï en grandes dimensions.

21Maintenant qu’on connaît la complexité combinatoire d’une enveloppe convexe, il reste à la calculer. L’algorithme de Graham résout le problème dans le plan de façon optimale. Qu’en est-il en dimension 3 ? On a vu que l’enveloppe convexe de n points en dimension 3 a un nombre linéaire d’arêtes et de faces, mais peut-on la calculer en temps O (n log n), ce qui serait optimal ? La réponse est positive mais les algorithmes connus qui ont cette complexité sont difficiles à programmer. En revanche, il existe un algorithme incrémental très simple qui insère les points un à un et met à jour l’enveloppe convexe après chaque insertion. Cet algorithme est quasiment aussi simple que l’algorithme de Graham et pourrait lui aussi être enseigné au collège. Mais cet algorithme n’est pas optimal et sa complexité en dimension 3 est quadratique dans le pire cas. Comment concilier le point de vue du programmeur, qui recherche un algorithme simple et efficace en pratique, et celui du théoricien, qui recherche un algorithme optimal dans tous les cas, ce qui peut conduire à des constructions complexes peu efficaces pour les valeurs de n utilisées en pratique ?

  • 10 Bernard Chazelle, L’Algorithmique et les Sciences, Paris, Collège de France/Fayard, coll. « Leçons (...)
  • 11 Un mot français ancien moins usité que sa version anglaise, qui a la même racine que randonner.
  • 12 Kenneth L. Clarkson et Peter Shor, « Applications of random sampling in computational geometry II  (...)
  • 13 Jean-Daniel Boissonnat, Olivier Devillers, René Schott, Monique Teillaud et Mariette Yvinec, « App (...)

22C’est l’introduction d’une part de hasard qui va permettre de concilier les points de vue et de constituer une des avancées les plus fécondes en géométrie algorithmique et, au-delà, dans toute l’algorithmique10. Le premier algorithme randomisé11 est un algorithme géométrique dû à Michael Rabin, prix Turing en 1976, mais ce sont Kenneth Clarkson et Peter Shor12 qui, dans les années 1990, ont introduit un cadre général pour concevoir et analyser des algorithmes géométriques randomisés. Ils montrent en particulier que si les points sont insérés dans un ordre aléatoire, l’algorithme incrémental de construction d’une enveloppe convexe est optimal en toutes dimensions. L’algorithme effectue des choix aléatoires mais il fournit toujours la solution exacte, et aucune hypothèse n’est faite sur les données d’entrée. C’est uniquement le déroulement de l’algorithme – et non son résultat – qui comporte une part de hasard. L’introduction de hasard a donc permis d’adapter un algorithme très simple et, tout en conservant sa simplicité, de le rendre optimal en moyenne et très efficace en pratique (on peut calculer la triangulation de Delaunay d’un million de points en dimension 3 en quelques secondes). De très nombreux travaux, auxquels nous avons participé activement13, ont permis d’étendre le travail fondateur de Clarkson et Shor. Plusieurs livres ont été écrits sur le sujet et les algorithmes randomisés occupent aujourd’hui une place essentielle en géométrie algorithmique.

Le calcul géométrique

23Calculer vite est important mais calculer de manière fiable l’est encore plus. Cette question a été ignorée des premiers travaux de géométrie algorithmique ; la thèse de M. Shamos utilise pour analyser la complexité des algorithmes un modèle d’ordinateur capable d’effectuer toutes les opérations élémentaires sur les nombres réels exactement et en un coût unitaire, ce qui n’est pas réaliste puisque les ordinateurs ne savent représenter que des nombres de précision finie. Le modèle simpliste de M. Shamos, en évacuant les questions arithmétiques, permet d’utiliser la puissance du continu et de s’appuyer aveuglément sur un immense corpus de résultats mathématiques. Ceci a conduit à un essor rapide des aspects théoriques de la géométrie algorithmique, et ce modèle reste le modèle standard dans le domaine. Mais un algorithme correct pour ce modèle de calcul ne l’est plus si on utilise pour représenter les nombres réels leur approximation par des nombres « machine ». On pourrait penser que la très grande précision fournie par les ordinateurs est suffisante en pratique et qu’il suffit d’ajuster quelques ε. En fait, il n’en est rien.

24La difficulté vient du fait que les structures géométriques ont une double nature, combinatoire et géométrique. Pour bien comprendre cette question, revenons au calcul de l’enveloppe convexe de points du plan. Le déroulement de l’algorithme est contrôlé par l’évaluation d’une seule opération numérique, qu’on appelle un prédicat, qui décide si un triangle est orienté positivement (s’il tourne vers la gauche) ou négativement (s’il tourne vers la droite). L’évaluation d’un prédicat aussi simple que le prédicat d’orientation peut poser des problèmes lorsque les points sont presque alignés et qu’on utilise l’arithmétique flottante des ordinateurs. Plus grave, d’infimes erreurs d’arrondi peuvent se propager et avoir des conséquences fatales, parfois bien plus tard, dans le déroulement de l’algorithme. Il est donc indispensable d’évaluer exactement le prédicat d’orientation si l’on veut construire une enveloppe convexe de manière fiable.

25Cette question des liens entre géométrie et arithmétique n’est pas nouvelle et nous sommes un peu dans la même situation que les Grecs, qui savaient démontrer par l’absurde que √2, la longueur de la diagonale d’un carré de côté unité, n’est pas un nombre rationnel. √2 n’était donc pas représentable dans leur système arithmétique (qui ne connaissait que les nombres entiers et les fractions) alors que des approximations étonnamment précises étaient connues depuis longtemps, comme en témoignent des tablettes babyloniennes. Le programmeur est comme l’esclave Ménon : il ne dispose que des nombres « machine » représentés dans son ordinateur, typiquement les nombres entiers et les nombres flottants, et il ne peut pas représenter exactement certaines quantités qui interviennent dans les algorithmes géométriques.

  • 14 The Computational Geometry Algorithms Library : www.cgal.org

26Évaluer un prédicat revient en général à évaluer le signe +, − ou 0 d’un polynôme. Pour éliminer les problèmes numériques, il suffirait d’évaluer ce polynôme de manière exacte en utilisant du calcul formel. Mais les polynômes en jeu peuvent être de degré élevé (le degré du prédicat d’orientation est d en dimension d) et cette solution serait très coûteuse et ralentirait beaucoup les programmes. Il est alors important de calculer le signe du polynôme sans évaluer le polynôme lui-même. Ceci suffit pour construire la structure combinatoire recherchée et assurer la robustesse des programmes. De plus, on peut tirer parti du fait que le signe du polynôme est facile à évaluer quand on est loin des situations dégénérées, comme trois points alignés dans le cas du prédicat d’orientation dans le plan. Les situations dégénérées requièrent des méthodes plus coûteuses pour être traitées exactement, mais sont rares en pratique. On dispose aujourd’hui de méthodes très performantes qui permettent de faire du calcul géométrique rigoureusement fiable sans pénaliser de façon significative les temps de calcul en pratique. Ces avancées ont fait le succès de la bibliothèque d’algorithmes géométriques CGAL14, qui apporte à ses utilisateurs la sécurité et l’efficacité des algorithmes théoriques.

CGAL

27C’est en 1995 qu’est né le projet d’une bibliothèque logicielle implémentant sous une forme cohérente les principaux algorithmes de géométrie algorithmique. L’objectif était double : d’une part, confronter les modèles théoriques à la réalité et les faire évoluer dans une dialectique vertueuse ; d’autre part, diffuser un savoir hautement spécialisé sous une forme facilement accessible et utile aux autres domaines scientifiques et à l’industrie.

28Le développement de CGAL a été une longue aventure scientifique et humaine qui a engagé plusieurs universités et instituts de recherche européens pendant vingt ans. Les principaux contributeurs sont l’École polytechnique fédérale de Zurich, l’Institut Max-Plank de Sarrebruck, l’université de Tel Aviv et mon équipe à l’Inria.

29Le développement de logiciels de grande envergure comme CGAL est un travail de nature fondamentale et de longue haleine qui se distingue de la programmation d’applications. Il est mené dans le cadre de la recherche académique, au moins dans une (longue) phase initiale. Il a un rôle structurant pour la discipline avant d’être un produit exportable vers les autres sciences et le monde industriel. La mise au point de CGAL n’a été possible qu’en réunissant des compétences scientifiques variées en algorithmique, en programmation, en arithmétique des ordinateurs, ainsi que des compétences touchant à l’organisation du travail de développement (ce à quoi les chercheurs ne sont pas nécessairement bien préparés).

30CGAL comporte aujourd’hui 700 000 lignes de code, une documentation de 3 000 pages et rassemble plus de 1 000 utilisateurs. CGAL est devenu le standard de fait en calcul géométrique. La bibliothèque est distribuée sous une licence open source, ce qui a permis sa large diffusion dans le milieu de la recherche et de l’enseignement. Également commercialisée par une startup d’Inria, Geometry Factory, elle est intégrée à de nombreux produits commerciaux dans des domaines variés à travers le monde.

3. Maillage de surfaces

Passage continu-discret

31Maintenant que les bases de la géométrie algorithmique ont été posées, revenons aux questions que nous nous posions au début de cette leçon. Comment représenter les objets, les organes, les monuments, les molécules que nous pouvons maintenant numériser ? Comment construire des modèles informatiques de ces formes complexes ? Ces modèles doivent avoir une complexité finie pour au moins deux raisons. Tout d’abord, un algorithme ne peut traiter qu’une quantité finie d’informations. D’autre part, l’objet d’étude n’est souvent connu qu’à travers un nombre fini de mesures.

32Comment représenter les formes géométriques continues par des modèles discrets ? Cette question du passage du continu au discret a suscité de nombreuses recherches picturales et occupe une place centrale en traitement du signal et des images, après les travaux fondateurs de Claude Shannon dans les années 1950. En comparaison, l’étude du lien continu-discret en géométrie est beaucoup plus récente. Les données géométriques étant par nature des ensembles plutôt que des fonctions, les méthodes de l’analyse numérique se révèlent dans une large mesure inadaptées, et une théorie de l’échantillonnage géométrique est requise.

Maillages de surfaces

33Commençons par examiner le cas des surfaces qui interviennent dans les multiples applications de la visualisation d’objets tridimensionnels. Mailler une surface consiste à échantillonner la surface et à relier ces points de façon à former une surface triangulée dans l’espace de dimension 3.

34On comprend que, pour offrir des garanties, l’échantillon devra être suffisamment dense et l’échantillon devra être d’autant plus dense que la forme que l’on veut mailler est complexe. Pour caractériser la complexité d’un objet géométrique, Herbert Federer, le fondateur de la théorie de la mesure géométrique, a introduit une quantité, baptisée la « portée » (reach en anglais), qui résume en une seule valeur la façon dont l’objet est géométriquement plongé dans l’espace. La portée se définit comme le plus petit nombre r tel que tout point à distance au plus r de l’objet a un unique plus proche point sur l’objet. Le concept de portée prend en compte la courbure de l’objet (une notion locale), mais aussi son étranglement (une notion globale).

35Quelles sont les qualités attendues d’un maillage ? On veut tout d’abord contrôler la distance entre la surface et le maillage. La distance habituelle pour comparer deux ensembles est la distance de Hausdorff : M et M′ sont à distance de Hausdorff d si tout point de M est à distance au plus d d’un point de M′ et vice versa. On voudrait également que les facettes du maillage soient proches des plans tangents à la surface. Ceci n’est pas nécessairement vrai, même si les facettes sont petites, comme l’illustre le cas du lampion de Schwarz (fig. 3). Le lampion de Schwarz est un polyèdre dont les sommets sont placés sur un cylindre et dont les faces sont aussi petites et proches que l’on veut du cylindre, mais disposées en accordéon. Une telle approximation serait catastrophique si on voulait rendre de manière réaliste la façon dont la lumière est réfléchie par le cylindre ou si on voulait estimer son aire en calculant celle du polyèdre. Enfin, il faut que l’approximation respecte la connectivité de la surface, son nombre de composantes, le nombre de trous. On veut que le maillage ait le même type topologique que la surface, c’est-à-dire qu’on puisse déformer continûment l’un en l’autre, sans coupure ni déchirure.

Figure 3

Figure 3

Le lampion de Schwarz.

36Pour répondre à ces exigences, les géomètres algorithmiciens ont adapté la notion de triangulation de Delaunay au cas d’une surface, à travers le concept de triangulation de Delaunay restreinte. La figure 4 montre un ensemble de points pris sur une courbe du plan et son diagramme de Voronoï en rouge. On indique en traits pleins bleus les arêtes du diagramme qui coupent la courbe et leurs arêtes duales dans la triangulation de Delaunay des points. L’ensemble des arêtes en traits pleins bleus constitue la triangulation de Delaunay des points restreinte à la courbe. Comme on le voit, c’est une bonne approximation de la courbe. La notion de triangulation de Delaunay restreinte s’étend au cas des surfaces de l’espace de dimension 3. On obtient dans ce cas un ensemble de triangles, chaque triangle étant dual d’une arête de Voronoï qui traverse la surface.

Figure 4

Figure 4

La triangulation de Delaunay restreinte à une courbe.

  • 15 Nina Amenta et Marshall Bern, « Surface reconstruction by Voronoi filtering », Discrete and Comput (...)

37Une série de travaux initiés par Amenta et Bern15 ont montré que, si P est un échantillon suffisamment dense d’une surface, la triangulation restreinte à cette surface est une excellente approximation qui satisfait tous les critères évoqués plus haut.

  • 16 Jean-Daniel Boissonnat et Steve Oudot, « Provably good sampling: and meshing of surfaces », Graphi (...)

38Avec Steve Oudot16, nous avons prolongé ce résultat et proposé un algorithme qui échantillonne et maille des surfaces. Cet algorithme utilise un oracle qui sonde la surface en lançant des rayons le long de certaines arêtes de Voronoï, un peu comme un aveugle découvre à tâtons son environnement, et raffine progressivement l’approximation jusqu’à satisfaire les conditions du théorème. Cet algorithme a été utilisé avec succès dans de nombreuses applications. Il peut, par exemple, être utilisé pour mailler des surfaces de niveau dans des images médicales tridimensionnelles ou des horizons sismiques dans des images géologiques, ou pour reconstruire des surfaces à partir de nuages de points (fig. 5).

Figure 5

Figure 5

Reconstruction d’une pièce mécanique.

39Les maillages bidimensionnels suffisent pour visualiser des surfaces mais, pour planifier des opérations chirurgicales robotisées ou simuler des phénomènes physiques, il est nécessaire de mailler non seulement les surfaces qui limitent les objets, mais également les volumes qu’elles délimitent. Il faut alors utiliser des maillages tétraédriques. La méthodologie utilisée pour les surfaces reste valide et le raffinement de la triangulation de Delaunay utilisé pour les surfaces peut être étendu au cas de volumes tridimensionnels limités par des surfaces. Bien que la génération de maillages de domaines tridimensionnels complexes soit beaucoup plus délicate que celle de maillages plans ou surfaciques, les progrès réalisés au cours des dix dernières années ouvrent la voie à de nouvelles applications. Dans le domaine médical, des maillages construits à partir d’images 3D permettent de visualiser les organes, de simuler des phénomènes physiologiques ou de planifier des interventions chirurgicales. Un autre exemple d’application est la reconstruction de modèles 3D à partir de vues du sol et de vues aériennes. On peut reconstruire ainsi des bâtiments, des villes ou des usines et créer des modèles 3D de l’environnement dans lequel doivent s’intégrer de nouvelles infrastructures comme des routes ou des voies ferrées.

Au-delà de la dimension 3

  • 17 Shawn Martin, Aidan Thompson, Evangelos A. Coutsias et Jean-Paul Watson, « Topology of cyclo-octan (...)

40On n’a considéré jusqu’ici que les surfaces de l’espace de dimension 3, mais certains problèmes se posent dans les dimensions supérieures à 3, et il est utile de trianguler des surfaces plongées dans des espaces de plus grandes dimensions. Celles-ci se rencontrent naturellement quand on s’intéresse aux systèmes dynamiques et à la modélisation du mouvement de systèmes articulés. Un exemple est donné par l’étude des paysages énergétiques des molécules. Une molécule est un ensemble d’atomes animés de mouvements les uns par rapport aux autres. Les différentes positions prises par la molécule lorsque ces déformations se produisent s’appellent les « conformations de la molécule ». On peut produire un grand nombre de conformations d’une molécule en simulant la dynamique moléculaire. Si la molécule est formée de n atomes, une conformation sera caractérisée par la donnée de 3n coordonnées qui repèrent la position dans l’espace de chaque atome, et on peut représenter chaque conformation comme un point dans un espace à 3n dimensions. L’ensemble des conformations obtenues par dynamique moléculaire sera un nuage de points dans ce grand espace. Récemment, des mathématiciens et des chimistes ont pu décrire précisément l’espace des conformations du cyclo-octane C8H16, un alcane cyclique utilisé dans la fabrication de plastiques et étudié depuis plus de quarante ans17. En analysant un ensemble d’un million de points de l’espace de dimension 72, chacun décrivant une conformation du cyclo-octane, les auteurs ont établi que l’espace des conformations du cyclo-octane est une surface de dimension 2 composée d’une sphère et d’une bouteille de Klein (une surface non orientable qu’on ne peut pas plonger en dimension 3). Au-delà de son intérêt intrinsèque, cette découverte ouvre de nouvelles pistes pour comprendre le paysage énergétique du cyclo-octane. Étendre ce type d’analyse aux plus grandes molécules, en particulier aux protéines, aurait des implications considérables.

41Lorsque l’espace ambiant est de grande dimension, on doit faire face à ce que l’on appelle, à la suite du mathématicien Richard Bellman, le fléau de la dimension : l’explosion combinatoire du coût de résolution d’un problème lorsque la dimension augmente. En géométrie algorithmique, ce phénomène se traduit notamment par le fait que les structures géométriques utilisées en petites dimensions, même les plus simples, comme les polyèdres, les triangulations ou les grilles, voient leur taille grossir de façon exponentielle avec la dimension de l’espace. Si on choisit une résolution d’un millième, une image 2D aura 1 million d’éléments (pixels), une image 3D en aura 1 milliard, et une image en dimension 6 en aura 1 018. On ne peut donc pas trianguler un espace de grande dimension comme l’espace de dimension 72 dans lequel sont données les conformations du cyclo-octane. On peut en revanche contourner la difficulté lorsque la structure qu’on cherche à trianguler est une variété de petite dimension, comme c’est le cas du cyclo-octane, dont l’espace des conformations est une surface de dimension 2.

42La notion de variété topologique généralise celle de courbe et de surface, qui sont les variétés de dimensions 1 et 2. D’une manière générale, une variété de dimension m est un objet non linéaire tel que le voisinage de tout point peut être déformé en un morceau de plan de dimension m topologiquement équivalent. La dimension m de la variété ne doit pas être confondue avec la dimension de l’espace ambiant dans laquelle cette variété est plongée. Comme on l’a vu, les conformations du cyclo-octane forment une surface de dimension 2 qui est plongée dans un espace de dimension 72. Lorsque la dimension de la variété est petite, il est utile de développer des algorithmes dont la complexité dépend essentiellement de la dimension intrinsèque m, non de la dimension de l’espace ambiant. On peut ainsi contourner le fléau de la dimension.

43La question de la triangulation des variétés a traversé tout le xxe siècle mathématique. Beaucoup d’illustres mathématiciens s’y sont penchés et en particulier Hassler Whitney, qui a démontré en 1957 que toutes les variétés différentiables sont triangulables. Il est intéressant de noter que sa démonstration est constructive malgré sa complexité algorithmique inaccessible.

  • 18 Jean-Daniel Boissonnat, Ramsay Dyer et Arijit Ghosh, « Delaunay triangulation of manifolds », Jour (...)

44Avec mes collaborateurs Ramsay Dyer et Arijit Ghosh18, nous avons élaboré les éléments d’une théorie de la triangulation de Delaunay des variétés. Contrairement au cas des surfaces, il ne suffit pas de raffiner l’échantillon pour assurer l’existence d’une triangulation de Delaunay sur une variété de dimension supérieure à 2. En revanche, sous des conditions plus fortes, on peut prouver l’existence de telles triangulations et les construire efficacement. Pour cela, on calcule des triangulations de Delaunay dans des cartes locales autour de chaque point de donnée, ce qu’on peut faire quasiment aussi rapidement que si l’on calculait une triangulation dans un espace linéaire de la même dimension que celle de la variété. Il faut ensuite recoller ces triangulations locales en une triangulation globale. Le fait que la triangulation de Delaunay soit canonique va le permettre si l’échantillon est assez dense. En fait, il faut assurer que les triangulations locales restent stables quand on passe d’un point à un point voisin sur la variété. Il est intéressant d’observer que la question de la stabilité de la triangulation de Delaunay qui est, comme on l’a vu, critique pour la robustesse des algorithmes, l’est également pour contourner le fléau de la dimension dans les problèmes de reconstruction des variétés. On voit, sur la figure 6, le maillage d’une surface de Riemann plongée en dimension 8. Trianguler cette surface a permis d’en calculer la caractéristique d’Euler et de conforter une conjecture mathématique.

Figure 6

Figure 6

Triangulation d’une surface de Riemann.

4. Analyse géométrique et topologique des données

  • 19 Serge Abiteboul, Sciences des données : de la logique du premier ordre à la toile, Collège de Fran (...)

45Si les données géométriques ont révolutionné notre perception et notre interaction avec le monde tridimensionnel, d’une manière plus générale, les données, géométriques ou non, ont pris une place essentielle dans la science moderne et, au-delà, dans la société toute entière19. De façon peut-être un peu inattendue, la géométrie algorithmique a un rôle à jouer dans ce contexte. Développer une approche géométrique et topologique de l’analyse des données, en construire les fondements mathématiques et algorithmiques, mettre au point et diffuser des programmes informatiques rapides et fiables constituent quelques-uns des nouveaux objectifs de la géométrie algorithmique.

Géométrie des données

46Les données géométriques fournissent les coordonnées de points dans l’espace. Plus généralement, une donnée est un ensemble de valeurs associées à certains paramètres comme la pression, la température ou le temps ; elle peut être représentée par un point dans un espace de paramètres qu’on appellera l’« espace des observations ». Cet espace des observations ne ressemble pas nécessairement à notre espace euclidien mais, si on sait définir une notion de proximité ou de ressemblance entre les données, on va pouvoir aborder l’analyse des données d’un point de vue géométrique.

47Le nombre de paramètres qui caractérisent une donnée est souvent grand et l’espace des observations est alors de grande dimension. Mais cette grande dimension n’est qu’apparente car les données sont en général corrélées et ne sont pas uniformément distribuées dans l’espace des observations. Comprendre la forme des données est alors utile pour mieux comprendre le système physique sous-jacent, comme on l’a vu dans le cas du cyclo-octane.

48Un autre exemple est celui des structures à grandes échelles de l’Univers (fig. 7). Plusieurs grands relevés de galaxies, comme le Redshift Survey, ont montré que la matière n’est pas distribuée de façon uniforme dans l’Univers : les galaxies semblent plutôt distribuées selon des filaments et des feuillets entourant des zones gigantesques quasiment vides de galaxies. L’univers apparaît aujourd’hui comme une structure évoquant celle d’une gigantesque éponge ou d’une toile d’araignée. Au-delà de l’observation toujours plus fine de l’Univers, un des buts de la cosmologie moderne est de comprendre ces structures à grandes échelles et de pouvoir les reproduire par simulation numérique. Il s’agit d’un problème qui ressemble à celui de la reconstruction discuté plus haut, mais la démarche n’est pas la même : il ne s’agit pas de reconstruire un objet dont l’existence est avérée, comme un organe ou une pièce mécanique, mais d’inférer une structure plausible à partir de données. C’est moins la précision de l’approximation qui nous intéressera que la recherche de nouvelles formes de symétrie et d’informations qualitatives robustes.

Figure 7

Figure 7

La toile cosmique.

© Springel et al. (2005).

Homologie persistante

49Rassembler les données en clusters, c’est-à-dire en groupes de données voisines, est une première question importante pour comprendre l’organisation spatiale des données. Quand les clusters ont une forme complexe, une méthode couramment utilisée consiste à estimer localement la densité des données et à rechercher des pics de cette densité. En pratique, l’estimation de la densité est bruitée ; il s’agit d’en détecter les modes significatifs et de les distinguer de ceux qui sont peu importants ou dus au bruit. Cette question n’est pas sans rappeler la notion de hauteur de culminance des alpinistes, qui est la différence d’altitude entre un sommet et le col le plus élevé permettant d’atteindre une cime encore plus haute. On peut ainsi distinguer l’aiguille du Midi – qui est un sommet majeur – des sommets voisins qui ont presque la même hauteur. Une question de même nature se pose en traitement du signal et en analyse d’images. Elle se pose également en modélisation géométrique : comment distinguer les détails (qui peuvent n’être que du bruit) des structures importantes ?

50L’homologie persistante apporte des réponses à cette question. Cette théorie prend ses racines dans la théorie de Morse, « cet énigmatique monolithe qui domine un bonne part du paysage mathématique contemporain », comme le disait René Thom. Remplaçons les points de données par des boules dont le rayon va jouer le rôle d’un facteur d’échelle, et faisons croître la valeur de ce rayon. L’union des boules va grossir, des composantes peuvent fusionner, des trous se créer puis disparaître, comme on le voit sur la figure 8. En des dimensions supérieures, des caractéristiques topologiques de plus grandes dimensions peuvent aussi apparaître et disparaître.

Figure 8

Figure 8

Évolution de l’union des boules centrées aux points de données.

51Ces caractéristiques topologiques peuvent être calculées grâce à l’homologie. On peut voir la formule d’Euler pour les polyèdres comme un premier résultat de la théorie de l’homologie, mais c’est Henri Poincaré qui en a vraiment bâti les fondations. L’homologie peut être décrite par des nombres que l’on appelle les « nombres de Betti ». Le premier nombre de Betti, β0, compte le nombre de composantes ; β1, le nombre de cycles indépendants ; β2, le nombre de cavités. Les nombres de Betti suivants comptent les « trous » de plus grandes dimensions. En analyse de données, β0 pourra compter les clusters ; β1, les cycles qui apparaissent, notamment quand des phénomènes périodiques sont en jeu ; β2, les cavités, qui sont en particulier importantes dans les structures poreuses.

52L’homologie est une notion plus grossière que l’équivalence topologique, mais elle conduit à des algorithmes efficaces d’algèbre linéaire quand on représente les espaces par des complexes simpliciaux. La notion de complexe simplicial généralise celle de graphe et de surface triangulée. Un complexe simplicial est défini comme un assemblage de simplexes (arêtes, triangles, tétraèdres, etc.) qui se recollent le long de faces communes de dimensions plus petites.

53Un complexe simplicial utile est le complexe de Čech, qui se définit à partir d’un ensemble de boules de la manière suivante. Si deux boules ont une intersection commune, on crée une arête joignant leurs centres. Si trois boules ont une intersection commune, on crée un triangle. Et, d’une manière générale, si k boules ont une intersection commune, on crée le simplexe de dimension k − 1 dont les sommets sont les k centres associés. Il faut considérer ce complexe comme une structure combinatoire abstraite qui n’est pas nécessairement plongée dans l’espace contenant les points.

  • 20 Jean Leray, « Sur la forme des espaces topologiques et sur les points fixes des représentations », (...)

54Le théorème du nerf de Jean Leray, éminent mathématicien qui a enseigné ici-même au Collège de France entre 1947 et 1978, va établir un pont entre la topologie des objets géométriques et les complexes simpliciaux20. Il découle du théorème du nerf que le complexe de Čech d’un ensemble de boules a la même homologie que l’union des boules.

  • 21 Steve Y. Oudot, Persistence Theory: From Quiver Representations to Data Analysis, Providence (R.I. (...)

55Nous avons les principaux ingrédients pour construire l’algorithmique de l’homologie persistante. C’est à partir des années 2000, sous l’impulsion d’Herbert Edelsbrunner et de Gunnar Carlsson, que l’homologie persistante s’est vraiment développée et que les questions algorithmiques ont été abordées. L’homologie persistante est aujourd’hui un outil central en analyse topologique des données, et l’objet de recherches très actives de nature mathématique et algorithmique21.

56La chaîne de traitement de l’homologie persistante est la suivante. Partant d’un nuage de points, on construit une suite de complexes simpliciaux emboîtés qu’on appelle une « filtration ». On peut prendre par exemple le complexe de Čech que nous venons de définir et considérer la suite de complexes emboîtés obtenus quand on fait varier le rayon des boules. L’algorithme de persistance parcourt la filtration, repère les changements topologiques du complexe et construit un diagramme de persistance qui associe à une caractéristique topologique (composante connexe, cycle, cavité et leurs analogues en plus grandes dimensions) un point du plan ayant pour abscisse la valeur de la filtration à laquelle elle est apparue et pour ordonnée la valeur de la filtration à laquelle elle a disparu. Les points qui sont loin de la diagonale représentent des éléments topologiques qui perdurent au cours de la filtration. La figure 9 montre l’exemple d’un ensemble de points échantillonnant approximativement un cercle. Sur le diagramme à droite de la figure, les points bleus représentent les composantes. Au départ, il y a autant de composantes que de points. Les composantes fusionnent rapidement quand le rayon grandit et on obtient une seule composante qui ne disparaît jamais. Les cycles sont représentés par les points rouges. De nombreux cycles sont créés au début. Ils disparaissent rapidement, puis apparaît un cycle qui a une longue durée de vie : il correspond au cercle échantillonné. Ce cycle finit par disparaître quand le rayon des boules est suffisamment grand.

Figure 9

Figure 9

La chaîne de traitement de l’homologie persistante.

  • 22 David Cohen-Steiner, Herbert Edelsbrunner et John Harer, « Stability of persistence diagrams », Di (...)

57On peut se demander quel crédit accorder à une représentation aussi succincte d’un jeu de données. Une partie de la réponse vient d’un résultat de stabilité. Considérons les deux fonctions de la figure 10. Comme attendu, la fonction rouge, qui est lisse, a deux modes persistants indiqués par deux points rouges sur le diagramme de persistance. La fonction bleue bruitée a de nombreux maxima et minima, ce qui conduit à de nombreux points dans le diagramme de persistance, mais la plupart sont très proches de la diagonale. Pour une certaine distance appelée « distance d’étranglement » (la longueur du plus grand segment bleu sur la figure de droite), les deux diagrammes de persistance (en incluant la diagonale) sont proches. Cette observation est en fait un théorème important de David Cohen-Steiner, Herbert Edelsbrunner et John Harer22, qui ont montré que des fonctions proches ont des diagrammes de persistance qui sont proches pour la distance d’étranglement. Les composantes persistantes correspondent donc à des modes qui restent stables si on perturbe la fonction. Ce sont des modes significatifs qui se distinguent du bruit.

Figure 10

Figure 10

Stabilité des diagrammes de persistance.

  • 23 Frédéric Chazal, Léonidas J. Guibas, Steve Y. Oudot et Primoz Skraba, « Persistence-based clusteri (...)

58L’analyse topologique que fournit l’homologie persistante est intéressante à plus d’un titre. Elle est peu sensible au choix de la métrique, indépendante du choix des coordonnées, et elle fournit des informations intrinsèques globales sur les données sous la forme de diagrammes de persistance robustes au bruit. L’homologie persistante offre de nouveaux outils pour l’analyse de données. Une application est la détection de clusters23 illustrée sur la figure 11 : le diagramme de persistance présente deux points éloignés de la diagonale, ce qui permet de classer les points en deux clusters, bleu et rouge.

Figure 11

Figure 11

Détection de clusters.

59On a jusque-là considéré le diagramme de persistance d’un seul nuage de points, dont on voulait analyser la structure géométrique. Une question tout aussi importante est de comparer des jeux de données pour pouvoir les comparer ou les classer. On peut, pour cela, considérer les diagrammes de persistance comme des signatures de nuages de points et utiliser la distance d’étranglement. On construit ainsi une géométrie dans l’espace des diagrammes de persistance. C’est un nouveau champ de recherche passionnant mêlant topologie algorithmique et statistiques.

60La mise en œuvre de cette théorie dans des applications réelles demande une algorithmique spécifique pour l’ensemble de la chaîne de l’homologie persistante. C’est ce que nous développons dans le cadre du projet Gudhi, financé par le Conseil européen de la recherche24. Le calcul du complexe de Čech est impossible en pratique et il faut concevoir d'autres types de complexes simpliciaux qui aient de bonnes propriétés topologiques et soient facilement calculables. Il faut aussi savoir coder de façon optimale ces complexes simpliciaux et leurs filtrations de façon qu’ils occupent le moins de place-mémoire possible tout en pouvant néanmoins être utilisés comme structures de données efficaces pour le calcul de la persistance. Les algorithmes de persistance eux-mêmes sont l’objet de recherches très actives et on ne connaît pas encore précisément la complexité algorithmique du calcul de la persistance. D’autres questions essentielles portent sur le développement d’algorithmes approchés. Enfin, pour que ces nouvelles techniques soient réellement efficaces et accessibles aux autres domaines scientifiques, il faut également développer des outils logiciels robustes, efficaces et faciles d’utilisation.

Conclusion

61J’ai essayé de vous montrer comment la démarche algorithmique s’est imposée en géométrie sous la pression combinée des besoins en modélisation tridimensionnelle et de la recherche en informatique. Le traitement des formes géométriques tridimensionnelles est devenu une nouvelle forme du traitement de l’information qui trouve des retombées visibles dans tous les domaines. Ceci a été rendu possible non seulement par les développements technologiques spectaculaires des capteurs, des moyens de calcul et des systèmes de visualisation, mais aussi par l’invention de nouvelles représentations des formes et de nouveaux paradigmes de calcul.

  • 25 Les enregistrements audio et vidéo des cours et des colloques sont disponibles sur le site web du (...)

62On a vu que la modélisation géométrique ne se limite pas aux formes tridimensionnelles. En voulant modéliser le mouvement, on est amené à modéliser des espaces de configurations de dimensions plus grandes que 3. On a vu également que la géométrie algorithmique a des modèles et des programmes à proposer pour explorer le monde vertigineux des données. C’est un sujet en plein développement que j’ai seulement effleuré, mais qui sera développé dans le cadre du cours et des colloques qui suivront25, et qui constitue un champ de recherche pour les années à venir.

63Je voudrais, pour terminer, remercier mes collaborateurs, collègues et étudiants qui ont contribué aux résultats que j’ai évoqués dans cette leçon et que je ne peux pas tous citer ici. Je voudrais également remercier ceux qui m’ont encouragé et aidé avant que le mot de géométrie algorithmique n’existe : Claude Puech, qui dirigeait à l’époque le département d’informatique de l’École normale supérieure, Philippe Flajolet, un maître de l’informatique mathématique, disparu trop tôt mais qui reste un modèle scientifique et humain, Olivier Faugeras, qui m’a confié un jour la thèse de Michael Shamos et qui m’a encouragé à pénétrer dans le nouveau monde de la géométrie algorithmique.

64Je vous remercie pour votre attention et conclus sur ce mot d’Henri Poincaré :

Une géométrie ne peut être plus vraie qu’une autre, elle peut simplement être plus commode.

Je tiens à remercier Gérard Berry, Ève Boissonnat, Frédéric Chazal, Emmanuelle Fleury et Mariette Yvinec pour leur relecture attentive et leurs commentaires sur ce texte.

Bibliographie

Aurenhammer Franz, Klein Rolf et Lee Der-Tsai, Voronoi diagrams and Delaunay triangulations, World Scientific Publishing Co. Inc., 2013.

Boissonnat Jean-Daniel, Chazal Frédéric et Yvinec Mariette, Geometric and Topological Inference, Cambridge (U.K.), Cambridge University Press, 2017.

Boissonnat Jean-Daniel et Teillaud Monique (dir.), Effective Computational Geometry for Curves and Surfaces, Berlin, Springer, 2007.

Boissonnat Jean-Daniel et Yvinec Mariette, Algorithmic Geometry, Cambridge (U.K.), Cambridge University Press, 1998.

Cheng Siu-Wing, Dey Tamal Krishna et Shewchuk Jonathan Richard, Delaunay Mesh Generation, Boca Raton/London/New York, CRC Press, 2013.

Dey Tamal K., Curve and Surface Reconstruction: Algorithms with Mathematical Analysis, Cambridge (U.K.), Cambridge University Press, 2006.

Edelsbrunner Herbert et Harer John, Computational Topology: An Introduction, Providence (R.I.), American Mathematical Society, 2010.

Ghrist Robert, Elementary Applied Topology, Leipzig, Amazon, 2014.

Oudot Steve Y., Persistence Theory: From Quiver Representations to Data Analysis, Providence (R.I.), American Mathematical Society, Mathematical Surveys and Monographs Series, vol. 209, 2015.

Springel Volker, White Simon D.M., Jenkins Adrian, Frenk Carlos S., Yoshida Naoki, Gao Liang, Navarro Julio, Thacker Robert, Croton Darren, Helly John, Peacock John A., Cole Shaun, Thomas Peter, Couchman Hugh, Evrard August, Colberg Joerg et Pearce Frazer, « Simulations of the formation, evolution and clustering of galaxies and quasars », Nature, vol. 435, no 629, 2005.

Notes

1 Computational geometry en anglais.

2 Michel Serres, Les Origines de la géométrie : tiers livre des fondations, Paris, Flammarion, 1993.

3 Nicholas Ayache, Des images médicales au patient numérique, Paris, Collège de France/Fayard, coll. « Leçons inaugurales », no 247, 2015 ; Collège de France, 2015.

4 Marie-Paule Cani, Façonner l’imaginaire : de la création numérique 3D aux mondes virtuels animés, Paris, Collège de France/Fayard, coll. « Leçons inaugurales », no 254, 2015 ; Collège de France, 2016.

5 Monique Sicard, La Fabrique du regard. Images de science et appareils de vision (xve-xxe siècle), Paris, Odile Jacob, 1998.

6 La notation ignore la constante de proportionnalité pour mettre en évidence l’ordre de grandeur de la complexité pour n grand.

7 Marc Jeannerod, Le Cerveau volontaire, Paris, Odile Jacob, 2009.

8 Boris Delaunay, « Sur la sphère vide », Izvestia Akadademia Nauk SSSR, Otdelenie Matematicheskii i Estestvennyka Nauk [Bulletin de l’Académie des sciences de l'URSS. Département des sciences mathématiques et naturelles], vol. 7, 1934, p. 793-800.

9 Peter McMullen, « The maximum numbers of faces of a convex polytope », Mathematika, vol. 17, no 2, 1970, p. 179-184.

10 Bernard Chazelle, L’Algorithmique et les Sciences, Paris, Collège de France/Fayard, coll. « Leçons inaugurales », no 229, 2013 ; Collège de France, 2013.

11 Un mot français ancien moins usité que sa version anglaise, qui a la même racine que randonner.

12 Kenneth L. Clarkson et Peter Shor, « Applications of random sampling in computational geometry II », Discrete and Computational Geometry, vol. 4, no 5, 1989, p. 387-421.

13 Jean-Daniel Boissonnat, Olivier Devillers, René Schott, Monique Teillaud et Mariette Yvinec, « Application of random sampling to on-line algorithms in computational geometry », Discrete and Computational Geometry, vol. 8, no 1, 1992, p. 51-71.

14 The Computational Geometry Algorithms Library : www.cgal.org

15 Nina Amenta et Marshall Bern, « Surface reconstruction by Voronoi filtering », Discrete and Computational Geometry, vol. 22, no 4, 1999, p. 481-504.

16 Jean-Daniel Boissonnat et Steve Oudot, « Provably good sampling: and meshing of surfaces », Graphical Models, vol. 67, no 5, 2005, p. 405-451.

17 Shawn Martin, Aidan Thompson, Evangelos A. Coutsias et Jean-Paul Watson, « Topology of cyclo-octane energy landscape », The Journal of Chemical Physics, vol. 132, no 23, 234115, 2010.

18 Jean-Daniel Boissonnat, Ramsay Dyer et Arijit Ghosh, « Delaunay triangulation of manifolds », Journal of Foundations of Computational Mathematics, 2017.

19 Serge Abiteboul, Sciences des données : de la logique du premier ordre à la toile, Collège de France/Fayard, coll. « Leçons inaugurales », no 226, 2012 ; Collège de France, 2013.

20 Jean Leray, « Sur la forme des espaces topologiques et sur les points fixes des représentations », Journal de mathématiques pures et appliquées, vol. 24, 1945, p. 95-167.

21 Steve Y. Oudot, Persistence Theory: From Quiver Representations to Data Analysis, Providence (R.I.), American Mathematical Society, Mathematical Surveys and Monographs Series, vol. 209, 2015.

22 David Cohen-Steiner, Herbert Edelsbrunner et John Harer, « Stability of persistence diagrams », Discrete & Computational Geometry, vol. 37, no 1, 2007, p. 103-120.

23 Frédéric Chazal, Léonidas J. Guibas, Steve Y. Oudot et Primoz Skraba, « Persistence-based clustering in Riemannian manifolds », Journal of the ACM, vol. 60, no 6, 2011.

24 https://project.inria.fr/gudhi

25 Les enregistrements audio et vidéo des cours et des colloques sont disponibles sur le site web du Collège de France : http://www.college-de-france.fr/site/jean-daniel-boissonnat/index.htm

Table des illustrations

Titre Figure 1
Légende Le diagramme de Voronoï d’un ensemble fini de germes (à gauche) et la triangulation de Delaunay duale (à droite).
URL http://books.openedition.org/cdf/docannexe/image/5103/img-1.png
Fichier image/png, 290k
Titre Figure 2
Légende Correspondance entre diagrammes de Voronoï, triangulations de Delaunay et polyèdres convexes.
URL http://books.openedition.org/cdf/docannexe/image/5103/img-2.png
Fichier image/png, 386k
Titre Figure 3
Légende Le lampion de Schwarz.
URL http://books.openedition.org/cdf/docannexe/image/5103/img-3.jpg
Fichier image/jpeg, 331k
Titre Figure 4
Légende La triangulation de Delaunay restreinte à une courbe.
URL http://books.openedition.org/cdf/docannexe/image/5103/img-4.png
Fichier image/png, 323k
Titre Figure 5
Légende Reconstruction d’une pièce mécanique.
URL http://books.openedition.org/cdf/docannexe/image/5103/img-5.png
Fichier image/png, 1,3M
Titre Figure 6
Légende Triangulation d’une surface de Riemann.
URL http://books.openedition.org/cdf/docannexe/image/5103/img-6.png
Fichier image/png, 181k
Titre Figure 7
Légende La toile cosmique.
Crédits © Springel et al. (2005).
URL http://books.openedition.org/cdf/docannexe/image/5103/img-7.jpg
Fichier image/jpeg, 967k
Titre Figure 8
Légende Évolution de l’union des boules centrées aux points de données.
URL http://books.openedition.org/cdf/docannexe/image/5103/img-8.png
Fichier image/png, 612k
Titre Figure 9
Légende La chaîne de traitement de l’homologie persistante.
URL http://books.openedition.org/cdf/docannexe/image/5103/img-9.png
Fichier image/png, 116k
Titre Figure 10
Légende Stabilité des diagrammes de persistance.
URL http://books.openedition.org/cdf/docannexe/image/5103/img-10.png
Fichier image/png, 40k
Titre Figure 11
Légende Détection de clusters.
URL http://books.openedition.org/cdf/docannexe/image/5103/img-11.png
Fichier image/png, 342k

Auteur

Professeur invité, chaire annuelle d’Informatique et sciences numériques (2016-2017)

Le texte et les autres éléments (illustrations, fichiers annexes importés) sont sous Licence OpenEdition Books, sauf mention contraire.

Rechercher dans OpenEdition Search

Vous allez être redirigé vers OpenEdition Search