Jean-Daniel Boissonnat est directeur de recherche à Inria, Sophia Antipolis. Il est le responsable du projet Gudhi (Geometric Understanding in Higher Dimensions) de l’European Research Council. Il est le tout nouveau titulaire de la Chaire « Informatique et sciences numériques » du Collège de France où il présente aujourd’hui un cours intitulé « Géométrie algorithmique : données, modèles, programmes ». Pénétrons avec lui dans le monde des données géométriques qui prennent une place si considérable dans notre vie quotidienne, avec les films d’animation et les jeux vidéo et, comme l’explique Jean-Daniel dans sa leçon, dans les sciences modernes. Cet article est publié en collaboration avec le Blog Binaire.
L’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 créer un outil informatique simple qui permette aux dessinateurs de modéliser des surfaces en trois dimensions comme des carrosseries de voitures et qui facilite la programmation des machines à commande numérique. Créer un modèle virtuel de formes 3D est une idée nouvelle qui permet de s’affranchir des maquettes physiques lourdes et encombrantes, et des représentations 2D (plans, dessins industriels, coupes, projections). Ces nouveaux modèles tridimensionnels simplifient radicalement traitement, reproduction et transmission des objets 3D. Ils ouvrent de nouveaux champs d’application aux créateurs de formes tridimensionnelles, ingénieurs, médecins, architectes et artistes.
L’invention de capteurs permettant de numériser des objets 3D va constituer une deuxième étape décisive dans le développement de la modélisation 3D. En donnant accès à la troisième dimension, la numérisation 3D a modifié le regard que nous portons sur le monde. Les images du corps humain en sont un exemple et de nombreux moyens de mesure 3D permettent aujourd’hui de mesurer des formes de l’échelle atomique à l’échelle astronomique. 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 essentiel dans de très nombreux domaines comme 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, la conception de médicaments.
Comment représenter les objets 3D que nous pouvons maintenant numériser ? Comment construire des modèles informatiques des formes complexes de la nature ou des statues de Michel Ange ? Comment utiliser ces modèles dans les nombreuses applications qui demandent de manipuler des formes 3D ? Notre cerveau est prodigieusement doué pour cartographier notre environnement et en construire des représentations internes qui vont lui permettre de planifier des actions.
Peut-on imaginer construire in silico des représentations qui intègrent les mesures géométriques et permettent d’effectuer des calculs efficacement ? Les formes sont très variées, les données massives : plusieurs centaines de milliers, voire des millions de points peuvent être nécessaires pour représenter précisément un objet complexe. Les questions de complexité des représentations et des algorithmes sont donc critiques. La géométrie algorithmique va fournir quelques clés essentielles à travers l’étude de structures de données géométriques comme les diagrammes de Voronoï et les triangulations de Delaunay qui ont une portée universelle et permettent de modéliser des formes très variées dans tous les domaines scientifiques.
Algorithmes de choix en géométrie
La difficulté de traduire les algorithmes théoriques en programmes efficaces et robustes a conduit à l’invention de nouveaux paradigmes algorithmiques et à la création de la bibliothèque logicielle CGAL (Computational Geometry Algorithms Library), dont j’ai été un des initiateurs. Un de ces paradigmes consiste à utiliser des algorithmes dits randomisés, qui effectuent des choix aléatoires au cours de leur déroulement et sont souvent simples et efficaces, ce qui en fait souvent les algorithmes de choix en géométrie.
Les algorithmes de triangulation de CGAL sont, par exemple, des algorithmes randomisés. Le développement de CGAL a été une longue aventure scientifique et humaine qui a engagé six universités en Europe et en Israël pendant 20 ans et se poursuit encore aujourd’hui. CGAL est un logiciel de grande envergure qui comporte plusieurs millions de lignes de code, diffusé dans le monde académique et intégré à de nombreux logiciels industriels dans des domaines d’application variés : géomodélisation, systèmes d’information géographiques, conception assistée par ordinateur, traitement d’images, calcul scientifique.
Echantillonage géométrique
Au-delà de la définition de structures de données géométriques et de la conception d’algorithmes efficaces pour les construire se pose la question du passage du continu au discret. Cette question a été étudiée depuis les années 1950 en traitement du signal et des images. En comparaison, l’étude du lien continu-discret en géométrie est beaucoup plus récente et ce n’est que dans les années 2000 qu’a émergé une théorie de l’échantillonnage géométrique. Une question centrale est celle de la reconstruction des formes à partir de mesures et plus généralement de l’inférence géométrique : sous quelles conditions un échantillon fini de points pris sur une forme permet-il de construire une bonne approximation de cette forme, d’en estimer des propriétés ?
Les fléaux de la dimension et du coût des calculs
Une question liée est celle du maillage de surfaces ou de volumes tridimensionnels. Pour visualiser des formes complexes ou simuler des phénomènes physiques, il est nécessaire de décomposer les phénomènes étudiés en éléments simples. Ces éléments doivent vérifier des propriétés de taille et de régularité souvent difficiles à respecter. Au-delà du cas des surfaces et des domaines tridimensionnels, il est également nécessaire de savoir représenter des formes de plus grandes dimensions comme les espaces de configurations de robots ou de molécules.
On doit alors faire face au fléau de la dimension et à l’explosion du coût des calculs. C’est un sujet qui soulève des questions de nature mathématique, algorithmique et informatique qui font l’objet de recherches actuelles en géométrie algorithmique. Si 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, en général, ont pris une place essentielle dans la science moderne et, au-delà, dans la société tout entière. De façon peut-être un peu inattendue, la géométrie algorithmique a des modèles et des programmes à proposer pour explorer le monde vertigineux des données, y compris non géométrique.
Analyse topologique des données
Une donnée est un ensemble de valeurs associées à certains paramètres comme la pression ou la température. On peut donc considérer une donnée comme un point dans un espace de paramètres qu’on appellera l’espace des observations. Si on sait définir une notion de proximité entre les données, on peut aborder l’analyse des données d’un point de vue géométrique. Les données sont en général corrélées et ne sont pas uniformément distribuées dans l’espace des observations. Une image n’est pas une matrice aléatoire. La recherche de structures géométriques peut fournir des modèles pour décrire les données et les analyser et, au-delà, comprendre le système qui les a produites.
Il s’agit d’un problème qui ressemble au problème de reconstruction 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, en général bruité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. Des approximations de nature topologique peuvent alors être utiles. L’analyse topologique des données et, en particulier, l’homologie persistante apportent de nouveaux outils pour comprendre l’organisation spatiale des nuages de points. De nouvelles connexions avec d’autres branches des mathématiques, notamment avec les statistiques, sont très prometteuses et les nouveaux concepts et algorithmes de l’analyse topologique des données commencent à être utilisés dans des domaines variés comme l’analyse de matériaux poreux, la modélisation des structures à grandes échelles de l’univers, la biologie structurale, les neurosciences ou l’analyse musicale.
Mon cours abordera les questions évoquées ci-dessus. Les séminaires apporteront des éclairages complémentaires. Ils seront donnés par de brillants jeunes chercheurs qui témoigneront de la dynamique de la communauté française de géométrie algorithmique. Les deux colloques donneront l’occasion d’écouter de grands noms du domaine et aussi de présenter les recherches que nous menons dans le cadre du projet Gudhi.
