Navigation – Plan du site

AccueilVolumes117Cours et recherches des professeursIV. Chaires annuellesInformatique et sciences numériques

Cours et recherches des professeurs
IV. Chaires annuelles

Informatique et sciences numériques

Jean-Daniel Boissonnat
p. 555-565

Notes de la rédaction

La série de cours et séminaires « Géométrie algorithmique : données, modèles, programmes » est disponible, en audio et/ou en vidéo, sur le site internet du collège de France (https://www.college-de-france.fr/site/jean-daniel-boissonnat/course-2016-2017.htm) ainsi que la leçon inaugurale « Géométrie algorithmique : des données géométriques à la géométrie des données » (https://www.college-de-france.fr/site/jean-daniel-boissonnat/inaugural-lecture-2016-2017.htm) et les colloques « Computational geometry and topology in the sciences » (https://www.college-de-france.fr/site/jean-daniel-boissonnat/symposium-2016-2017.htm) et « Geometry understanding in higher dimensions » (https://www.college-de-france.fr/site/jean-daniel-boissonnat/symposium- 2016-2017__1.htm). La leçon inaugurale a été publiée sous forme imprimée (Collège de France/Fayard) et numérique (Collège de France). Texte intégral en ligne : https://books.openedition.org/CdF/5100.

Texte intégral

Enseignement

Cours et séminaires – Géométrie algorithmique : données, modèles, programmes

Introduction

1Le 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. On peut aujourd’hui modéliser les formes complexes de la nature de l’échelle microscopique à l’échelle astronomique, les statues de Michel-Ange ou des villes. Les formes qu’on peut représenter sur un ordinateur sont très variées et les données 3D qu’il faut traiter sont énormes. La conception d’algorithmes efficaces et l’étude de leur complexité est critique. C’est le sujet de la géométrie algorithmique.

2Dans une première partie, ce cours étudie les interactions entre géométrie et calcul, et étudie de manière systématique plusieurs structures géométriques fondamentales du point de vue algorithmique. Les algorithmes probabilistes jouent un rôle central et les questions de robustesse et de précision numérique sont discutées. Il faut s’appuyer sur des modèles de calcul suffisamment simples pour permettre d’effectuer les analyses mais suffisamment réalistes pour que celles-ci soient utiles en pratique.

3Dans une deuxième partie, on s’intéresse à la représentation des formes géométriques qu’on peut maintenant numériser. Comment construire des modèles informatiques de ces formes complexes et garantir la qualité des approximations ? Le cours s’intéresse d’abord aux maillages des surfaces dans l’espace tridimensionnel puis aborde le cas des objets de plus grandes dimensions qui posent des questions de nature topologique et algorithmique nouvelles. On peut alors développer les techniques de la géométrie algorithmique pour aborder l’analyse de données d’un point de vue géométrique original et fécond.

Cours 1 – Modèles géométriques discrets

4L’étude des structures géométriques discrètes fondamentales comme les polyèdres convexes, les diagrammes de Voronoï ou les triangulations de Delaunay est l’un des sujets centraux de la géométrie algorithmique. On établit une correspondance très utile entre diagrammes de Voronoï, triangulations de Delaunay et polyèdres convexes. Le théorème de McMullen qui majore le nombre de faces d’un polyèdre convexe permet alors de borner la complexité combinatoire des diagrammes de Voronoï et des triangulations de Delaunay.

5Au-delà de l’analyse des structures géométriques, le but de la géométrie algorithmique est de concevoir des algorithmes permettant de construire ces structures et de les représenter sous la forme de programmes informatiques. Le cours présente un premier algorithme simple qui permet de construire l’enveloppe convexe d’un ensemble fini de points dans un espace de dimension quelconque. Des résultats analogues se déduisent pour les diagrammes de Voronoï et les triangulations de Delaunay et permettent de traiter des questions connexes comme le calcul d’une union de boules ou des diagrammes de Voronoï pour différentes métriques.

Séminaire – Modèles géométriques pour la prédiction des interactions macromoléculaires

Frédéric Cazals (Inria, Sophia Antipolis), le 29 mars 2017

6Si les protéines et les acides nucléiques sont les éléments constitutifs fondamentaux d’un organisme, la biologie elle-même repose sur les interactions entre ces molécules. Comprendre afin de prédire, mais aussi contrôler ces interactions, requiert la modélisation de systèmes allant de milliers à des millions d’atomes, sur des échelles de temps d’intérêt biologique c’est-à-dire au-delà de la milliseconde.

7Cet exposé aborde la modélisation de tels phénomènes sous deux angles complémentaires. Dans la première partie, nous montrons comment des techniques d’apprentissage (régression) utilisant les diagrammes de Voronoï permettent sous certaines hypothèses de prédire de façon fiable des quantités thermodynamiques subtiles telles que l’affinité de liaison entre deux protéines. Dans la seconde, nous envisageons le calcul ab initio de telles quantités, dans le cadre du formalisme des paysages énergétiques.

8Cet exposé évoque plusieurs thèmes centraux traités dans le cours, à savoir les diagrammes de Voronoï, le calcul géométrique, la reconstruction de modèles, l’exploration d’espaces de grande dimension, la randomisation ou encore la persistance topologique ; thèmes qui, de façon remarquable, concourent à enrichir notre compréhension du rapport entre la structure, la dynamique et la fonction des biomolécules.

Cours 2 – La puissance de l’aléa. Algorithmes randomisés

9Pour traiter les énormes masses de données issues des applications, l’amélioration des performances des ordinateurs ne suffit pas et il est nécessaire de concevoir des algorithmes efficaces en théorie et en pratique. Dans cette course à la performance, l’introduction d’une part de hasard a constitué l’une des avancées les plus fécondes. On parle alors d’algorithmes randomisés. Les algorithmes randomisés comptent sur le hasard pour éviter, au moins en moyenne, les configurations complexes (en général rares) qui pénalisent les performances ; ils sont souvent à la fois simples et efficaces et constituent les algorithmes de choix en pratique. Si les algorithmes randomisés ont été inventés pour résoudre des problèmes géométriques, ils occupent maintenant une place importante dans tous les domaines de l’algorithmique.

10Le cours expose la théorie des algorithmes incrémentaux randomisés sur l’exemple du calcul de l’enveloppe convexe d’un ensemble fini de points. Contrairement à l’algorithme incrémental exposé au premier cours, cet algorithme est optimal en toutes dimensions et son analyse est élémentaire. Le cours présente d’autres exemples d’algorithmes incrémentaux randomisés et montre également comment le résultat central de la théorie, de nature probabiliste, conduit à des résultats combinatoires déterministes qu’on ne sait pas démontrer autrement.

Séminaire – Probabilités géométriques

Pierre Calka (université de Rouen), le 19 avril 2017

11Les probabilités géométriques portent sur l’étude de figures géométriques, en général euclidiennes, qui ont été générées aléatoirement. Ce domaine des mathématiques est apparu au xviiie siècle et a connu un essor récent, notamment en lien avec la conception et l’analyse d’algorithmes géométriques.

12Dans cet exposé, nous proposons une introduction générale à quelques modèles et méthodes classiques en probabilités géométriques. Nous nous intéressons plus particulièrement à l’étude asymptotique d’enveloppes convexes aléatoires et à certaines propriétés des mosaïques aléatoires, en particulier de type Poisson-Voronoï.

Cours 3 – Calcul géométrique

13Calculer vite est important mais calculer de manière fiable l’est peut-être encore plus. Cette question est moins simple qu’il n’y paraît. Les pionniers de la géométrie algorithmique ont analysé les performances des algorithmes en faisant l’hypothèse que toutes les opérations sur les nombres réels pouvaient être effectuées de façon exacte pour un coût unitaire. Un tel modèle de calcul permet de se concentrer sur l’estimation asymptotique de la complexité des algorithmes mais ignore complètement le fait que les ordinateurs travaillent avec des représentations finies des nombres.

14Ceci est particulièrement problématique en géométrie algorithmique où l’on cherche à construire des structures combinatoires (comme l’enveloppe convexe d’un ensemble fini de points) en se reposant sur des opérations numériques liées au plongement de ces structures. Cette dimension arithmétique du calcul géométrique a longtemps constitué un frein à la diffusion des techniques de la géométrie algorithmique.

15Ce cours distingue les prédicats des constructions géométriques et analyse précisément les besoins en précision numérique de quelques algorithmes géométriques fondamentaux. Une question-clé est l’évaluation exacte du signe de polynômes dont les variables sont les données d’entrée. Tous les algorithmes résolvant le même problème n’ont pas nécessairement la même complexité algébrique comme le montre l’exemple du calcul de l’arrangement de segments du plan. Un autre exemple est donné par le complexe à témoins qui n’utilise que des polynômes de degré 2 mais permet d’approcher, sous certaines conditions, une triangulation de Delaunay dont le degré est d + 2 et dépend de la dimension de l’espace de travail. Les développements théorique et pratique du calcul géométrique ont conduit à des avancées spectaculaires dont la bibliothèque logicielle CGAL est un exemple. On peut aujourd’hui certifier les résultats fournis par la plupart des algorithmes géométriques fondamentaux sans en dégrader significativement les performances.

Séminaire – La bibliothèque logicielle CGAL

Sylvain Pion, le 26 avril 2017

16CGAL – Computational Geometry Algorithms Library – est une bibliothèque logicielle d’algorithmes et de structures de données géométriques issue de projets de recherche européens. Après avoir présenté le projet, son histoire et son organisation, nous avons décrit les fonctionnalités principales de CGAL en lien avec des domaines d’applications. Nous avons ensuite détaillé les aspects techniques généraux de CGAL : généricité, robustesse et efficacité. Il s’agit, d’une part, de l’utilisation de la programmation générique en C++, qui permet d’abstraire l’implémentation des algorithmes des types de données sur lesquelles ils s’appliquent, et d’autre part, de calcul exact, qui garantit la robustesse des calculs et qui fait appel à des outils arithmétiques variés et efficaces.

Cours 4 – Génération de maillages

17Un maillage est une approximation d’un domaine en éléments simples qu’on appelle des simplexes : triangles dans le plan, tétraèdres en dimension 3 et leurs analogues en dimensions supérieures. La qualité de l’approximation dépend de la forme des simplexes utilisés. L’une des questions importantes est la construction de « bonnes » triangulations, c’est-à-dire des triangulations dont les éléments ne sont pas trop aplatis et ont des angles dièdres suffisamment grands. Cette question est centrale dès que l’on veut produire une image de synthèse réaliste ou simuler un phénomène physique complexe.

18Ce cours montre tout d’abord que, pour un ensemble de points donné, la triangulation de Delaunay est optimale de plusieurs points de vue. On peut améliorer la qualité d’un maillage en choisissant la position de ses sommets. On introduit pour cela la notion d’ε-net qui caractérise la qualité d’un ensemble fini de points échantillonnant un domaine. On montre que de tels échantillons peuvent être construits de manière efficace en toutes dimensions. Ce résultat est suffisant en dimension 2 pour assurer que la triangulation de Delaunay de tels échantillons est bonne, ce qui la rend très utile en pratique. Malheureusement, cette propriété n’est pas vraie en dimensions 3 et au-delà : les triangulations tridimensionnelles peuvent contenir des simplexes très aplatis quel que soit le raffinement du maillage. Si le problème est bien connu, aussi bien des mathématiciens qui cherchent à établir des garanties que des ingénieurs qui utilisent ces maillages pour faire des calculs, il est très difficile à résoudre. Le cours présente quelques-unes des avancées théoriques obtenues au cours des dix dernières années ainsi que des solutions heuristiques efficaces. Il présente notamment un algorithme randomisé qui permet de construire de bonnes triangulations de Delaunay en toutes dimensions. L’algorithme s’appuie sur une version algorithmique du lemme local de Lovász, un résultat algorithmique majeur dû à Moser et Tardos.

Séminaire – Les deux réductions de Voronoï et leur application aux équations aux dérivées partielles

Jean-Marie Mirebeau (CNRS, université d’Orsay), le 3 mai 2017

19Motivé par des applications en arithmétique, le mathématicien Voronoï souhaitait classifier les formes quadratiques modulo l’action du groupe des changements de variables à coefficients entiers. Pour cela il introduisit deux constructions invariantes par ce groupe, permettant la « réduction » à un domaine fondamental : la première est un certain programme d’optimisation linéaire, la seconde est le diagramme de Voronoï dont les sites sont les points à coordonnées entières et dont la fonction distance est donnée par la forme quadratique d’intérêt. Nous avons décrit ces réductions, ainsi que leurs applications à l’analyse numérique des équations aux dérivées partielles, du premier et du second ordre, où elles trouvent des applications aussi inattendues qu’efficaces. Les réductions de Voronoï, conçues pour étudier l’interaction d’une forme quadratique avec un réseau additif, se montrent en effet particulièrement adaptées pour concevoir des schémas de discrétisation d’opérateurs différentiels anisotropes sur des maillages cartésiens.

Cours 5 – Courbes et surfaces

20Les cours précédents ont posé les bases de la géométrie algorithmique. Les cours qui suivent vont s’attacher à la construction de modèles informatiques représentant les formes géométriques complexes que l’on peut aujourd’hui numériser comme des pièces mécaniques, des organes ou des monuments. Une question centrale est celle de l’échantillonnage géométrique et du passage du continu au discret. La question de l’échantillonnage – qui a une longue histoire en traitement du signal – et des images – après les travaux fondateurs de Claude Shannon dans les années 1950 – est beaucoup plus récente en géométrie et requiert de nouveaux outils théoriques.

21Ce cours aborde 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. Il faut tout d’abord caractériser un bon échantillon d’une surface : on comprend que pour offrir des garanties, l’échantillon doit être suffisamment dense et d’autant plus dense que la forme qu’on veut mailler est complexe. Il faut ensuite préciser les critères d’approximation qu’on attend d’un maillage, à la fois géométriques et topologiques. Reste à construire un bon maillage. On montre qu’on peut adapter la notion de triangulation de Delaunay et construire un algorithme de maillage de surface qui offre des garanties théoriques et se comporte très bien en pratique.

Séminaire – Reconstruction de surfaces

Pierre Alliez (Inria, Sophia Antipolis), le 10 mai 2017

22Les avancées technologiques des instruments de mesure ont révolutionné notre capacité à numériser le monde en 3D. Cette révolution a rendu possible l’essor de nouvelles applications comme l’interprétation automatique de scènes, la simulation de phénomènes physiques à l’échelle de villes et la documentation numérique du patrimoine architectural.

23Un sujet-clé au cœur de cette révolution est celui de la reconstruction de surfaces, qui consiste à convertir les mesures en une représentation géométrique interprétable par l’ordinateur. L’objectif est de construire une surface uniquement à partir de mesures le plus souvent ponctuelles, telle que la topologie et la géométrie de la surface reconstruite se rapprochent de la surface physique mesurée. C’est par essence un problème mal posé (avec des solutions non uniques), et la diversité des méthodes existantes reflète celle des connaissances a priori sur les surfaces physiques et des propriétés recherchées pour la surface reconstruite.

24Ce séminaire propose une introduction aux principales familles de méthodes de reconstruction de surfaces, sous l’angle des hypothèses utilisées pour rendre le problème mieux posé.

25Nous abordons ensuite les problèmes endurants posés par les données imparfaites, c’est-à-dire imprécises, peu denses, incomplètes voire aberrantes. La quête de robustesse à ces données imparfaites a motivé des méthodes variationnelles et des approches plus récentes inspirées par la théorie du transport optimal.

26Enfin, nous évoquons les défis scientifiques émergents en lien avec les nouveaux paradigmes d’acquisition des données (réseaux de capteurs, numérisation continue, données communautaires) et les impacts sociétaux de la démocratisation des méthodes de numérisation 3D.

Cours 6 – Espaces de configurations

27Le cours précédent a considéré les surfaces de l’espace de dimension 3 mais il est utile de trianguler des surfaces plongées dans des espaces de plus grandes dimensions. Des espaces de dimensions supérieures à 3 se rencontrent naturellement quand on s’intéresse aux systèmes dynamiques et à la modélisation du mouvement des 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 (d’ampleur limitée) 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. À chaque conformation, on peut associer une énergie. On obtient ainsi le paysage énergétique de la molécule dont la compréhension reste un défi majeur en chimie et en biologie. Le cours généralise les résultats du cours précédent et aborde l’approximation d’objets géométriques généraux de dimensions quelconques.

28Il faut pour cela introduire des concepts de topologie algorithmique et développer une théorie de l’échantillonnage géométrique au-delà du cas des surfaces de l’espace à trois dimensions. Ceci est fait à travers la notion de fonction distance qui conduit à des résultats mathématiques très généraux. Leur mise en œuvre algorithmique est cependant délicate et le fléau de la dimension rend les techniques utilisées en petites dimensions trop coûteuses en grandes dimensions (elles dépendent exponentiellement de la dimension ambiante). Le cours montre comment le fléau de la dimension peut être contourné si on restreint les objets d’étude à des variétés de complexité bornée. On peut notamment reconstruire efficacement des sous-variétés de petites dimensions intrinsèques à partir de nuages de points plongés dans des espaces de très grandes dimensions. On peut également construire des maillages anisotropes et construire des triangulations de Delaunay de variétés riemanniennes.

Séminaire – Dessin de graphes

Arnaud de Mesmay (CNRS, GIPSA-LAB), le 17 mai 2017

29Les graphes constituent la structure la plus élémentaire pour modéliser les relations entre divers objets. Cette simplicité est source d’ubiquité, et ils sont utilisés dans des contextes extrêmement divers, de la cartographie aux réseaux sociaux en passant par la linguistique. Une problématique-clé est alors celle de leur visualisation : c’est l’objet du dessin de graphes, un domaine visant à étudier les aspects théoriques, algorithmiques, mais aussi éminemment pratiques et même esthétiques des représentations de graphes. Dans cet exposé, nous présenterons un panorama de cette discipline foisonnante en insistant sur ses nombreuses connexions avec la géométrie, la topologie, et leurs pendants algorithmiques présentés dans le cours.

Cours 7 – Structures de données

30En 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. Un exemple important est celui de la recherche de plus proches voisins. Si P est un ensemble fini donné de points et x un point de requête, on veut déterminer le point de P le plus proche de x. On peut bien sûr examiner tous les points de P un à un et retenir celui qui est le plus proche de x mais on peut faire beaucoup mieux. Par exemple, si les points de P sont dans le plan euclidien, on peut construire le diagramme de Voronoï de P. La recherche du plus proche voisin de x se ramène alors à localiser x dans le diagramme, ce qu’on peut faire en temps logarithmique et non pas linéaire.

31En dimensions supérieures à 2, le problème est beaucoup plus difficile et, pour être efficaces, les algorithmes de recherche de plus proches voisins doivent se contenter de fournir des solutions approchées. Par ailleurs, on peut se contenter de n’avoir la solution qu’avec une bonne probabilité. Les algorithmes probabilistes s’avèrent alors une nouvelle fois très efficaces. Le cours présente différentes partitions de l’espace ambiant et montre comment tirer parti de la dimension intrinsèque de l’ensemble P. On présente également la technique LSH (local sensitive hashing) qui est actuellement la meilleure technique de recherche de voisins en grandes dimensions.

Séminaire – Learning streaming and distributed big data using core-sets

Danny Feldman (University of Haifa), le 24 mai 2017

32A coreset (or, core-set) for a given problem is a “compressed” representation of its input, in the sense that a solution for the problem with the (small) coreset as input would yield a provable (1+epsilon) approximation to the problem with the original (large) input.

33Using traditional techniques, a coreset usually implies provable linear time algorithms for the corresponding optimization problem, which can be computed in parallel, via one pass over the data on the cloud, and using only logarithmic space (i.e., in the streaming model). During the recent years, coresets were designed for many problems in deep/machine learning, statistics, facility location, real-time systems, computer vision and robotics.

34In this talk I will forge links between coresets for machine learning of streaming “Big Data” on the cloud, computational geometry, and robotic. In particular, coresets for matrix approximation, epsilon-nets, and autonomous toy-quadcopters.

Cours 8 – Géométrie des données

35Si 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é tout entière. Développer une approche géométrique et topologique de l’analyse des données (on parle de topological data analysis en anglais), 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 qu’aborde ce dernier cours.

36Les données sont considérées comme des points dans un espace qu’on suppose muni d’une notion de distance (pas nécessairement la distance euclidienne usuelle). La plupart du temps, les points de données vivent dans des espaces de grandes dimensions mais ne sont en général pas distribués de manière uniforme dans cet espace gigantesque. La complexité apparente des données ne reflète en général pas la complexité intrinsèque de celles-ci. Il est donc important de rechercher des modèles synthétiques qui représentent convenablement les données et permettent de les analyser. C’est un problème majeur qu’on appelle « la réduction de dimension ». Quelle est la dimension des données ? Peut-on plonger les données dans un espace de petite dimension sans trop modifier les distances entre points ? Peut-on concevoir des algorithmes dont la complexité dépende de la dimension des données plutôt que de celle de l’espace des observations ? Ces questions sont à l’origine de résultats remarquables et au développement d’algorithmes très utiles comme on l’a vu pour la recherche de voisins en grandes dimensions dans le cours précédent.

37Le cours introduit deux modèles géométriques pour les données. Le premier est celui des amas de points (ou clusters) et du partitionnement des données. Le deuxième cherche à approximer les données par des variétés triangulées de petites dimensions même si elles sont plongées dans des espaces de grandes dimensions. Cette hypothèse est justifiée par des résultats spectaculaires comme le théorème de Takens pour les séries temporelles ou le lemme de Johnson Lindenstrauss et ses variantes. Les résultats d’approximation des variétés décrits dans les cours précédents sont utilisables mais, pour être utilisables en pratique, il faut les analyser d’un point de vue statistique et les rendre robustes au bruit toujours présent dans les données. Ceci conduit à étudier la distance à une mesure de probabilités et à des théorèmes de stabilité qui permettent d’étendre les résultats de reconstruction vus dans les cours précédents.

Séminaire – Analyse topologique des données

Frédéric Chazal (Inria, Saclay), le 31 mai 2017

38L’analyse topologique des données (TDA) est un domaine récent qui connaît un succès croissant depuis quelques années. Il vise à comprendre, analyser et exploiter la structure topologique et géométrique de données souvent représentées par des nuages de points dans des espaces euclidiens ou des espaces métriques plus généraux. Avec l’émergence de la théorie de la persistance topologique, la géométrie et la topologie algorithmiques ont fourni des outils mathématiques et algorithmiques nouveaux et efficaces pour aborder ce sujet. Combinés à des méthodes statistiques, ces outils ont récemment donné lieux à des applications et des résultats originaux dans le domaine de l’analyse des données et de l’apprentissage statistique.

Séminaire – Object-centric machine learning

Leonidas Guibas (Computer Science Department, Stanford University), le 28 avril 2017

39Deep knowledge of the world is necessary if we are to have autonomous and intelligent agents and artifacts that can assist us in everyday activities, or even carry out tasks entirely independently. One way to factorize the complexity of the world is to associate information and knowledge with stable entities, animate or inanimate, such as a person or a vehicle, etc. In this talk I’ll survey a number of recent efforts whose aim is to create and annotate reference representations for objects based on 3D models with the aim of delivering such information to new observations, as needed. In this object-centric view, the goal is to use these reference representations for aggregating information and knowledge about object geometry, appearance, articulation, materials, physical properties, affordances, and functionality.

40We acquire such information in a multitude of ways, both from crowd-sourcing and from establishing direct links between models and signals, such as images, videos, and 3D scans – and through these to language and text. The purity of the 3D representation allows us to establish robust maps and correspondences for transferring information among the 3D models themselves – making our current 3D repository, ShapeNet, a true network. Furthermore, the network can act as a regularizer, allowing us to benefit from the “wisdom of the collection” in performing operations on individual data sets or in map inference between them. This effectively enables us to add missing information to signals through computational imagination, giving us for example the ability to infer what an occluded part of an object in an image may look like, or what other object arrangements may be possible, based on the world-knowledge encoded in ShapeNet and other repositories.

41The talk will also briefly discuss current approaches in designing deep neural network architectures appropriate for operating directly on irregular 3D data representations, such as meshes or pointclouds, as well as ways to learn object function from observing multiple action sequences involving objects.

Colloque – Computational geometry and topology in the sciences

42As Franco Preparata will recall, computational geometry emerged in the late seventies. Since then, the field has developed a lot and its roots and impact extend now far beyond the traditional areas of computer science. The goal of this first colloque is to present in an accessible way some of the most promissing trends in computational geometry research, both from a theory and an applied perspective. We will see new, and sometimes spectacular, theoretical developments, and a number of new applications and connections with dynamical systems, robotics, statistics and data analysis.

43The speakers of this colloque are all outstanding researchers whose seminal contributions have shaped the field.

44It is intended that this colloque helps establishing new and mutually beneficial interactions with the other sciences.

45The colloque ends with a concert by Agnès Sulem and her quartet. Agnès is a colleague at Inria who is both a leading researcher in applied mathematics and a professional musician whose quartet created several contemporary works and made several recordings.

46• Franco Preparata (Brown University) : « Computational geometry: the early days »

• Bernard Chazelle (Princeton University) : « Geometry, dynamics, and natural algorithms »

• Dan Feldman (University of Haifa) : « Computational geometry for robotics and big data systems »

• Sandoy Dasgupta (UCSD) : « Geometric algorithms for classification and retrieval in high dimension »

• Micha Sharir (Tel Aviv University) : « Incidences, distinct and repeated distances, other hard Erdös problems in geometry, and their applications: the new algebraic era »

• Konstantin Mischaikow (Rutgers University) : « Towards a computational, discrete geometric foundation for nonlinear dynamics »

• Uli Wagner (Institute for Sciences and Technology, Vienna) : « Embeddings, combinatorics, and algorithms »

Colloque – Geometry understanding in higher dimensions

47• Sanjoy Dasgupta (University California San Diego) : « Cluster trees, near neighbor graphs, and continuum percolation »

• Bertrand Michel (École centrale de Nantes) : « A statistical approach to topological data analysis »

• Steve Oudot (Inria) : « Topological graphs for data analysis: structure, stability and statistics »

• Quentin Mérigot (Université Paris Sud) : « Computational geometry, optimal transport and applications »

• Berend Smit (EPFL) : « The materials genome in action »

• Ramsay Dyer (MSP and Inria) : « Triangulating manifolds »

• Clément Maria (University of Queensland) : « Algorithmic aspects of topological data analysis »

• Arijit Ghosh (Indian Statistical Institute) : « Combinatorial Macbeath regions for semi-algebraic set systems »

• Valerio Pascucci (University of Utah) : « Interactive visualization of high dimensional data: can we deal with curse of dimentionality and failure of intuition? »

Publications

48Boissonnat J.-D., Chazal F., Yvinec M., Geometric and Topological Inference, Cambridge, Cambridge University Press, coll. « Cambridge Texts in Applied Mathematics », n° 17, 2018.

Boissonnat J.-D., Karthik C.S. et Tavenas S., « Building efficient and compact data structures for simplicial complexes », Algorithmica, vol. 79, n° 2, 2017, p. 530-567, DOI : 10.1007/s00453-016-0207-y [arXiv: 1503.07444].

Boissonnat J.-D., Dyer R. et Ghosh A., « Delaunay triangulation of manifolds », Foundations of Computational Mathematics, vol. 18, n° 2, 2018, p. 399-431, DOI : 10.1007/s10208-017-9344-1.

Boissonnat J.-D., Dyer R., Ghosh A. et Martynchuk N., « An obstruction to Delaunay triangulations in Riemannian manifolds », Discrete & Computational Geometry, vol. 59, n° 1, 2018, p. 226-237, DOI : 10.1007/s00454-017-9908-5.

Boissonnat J.-D., Dyer R., Ghosh A. et Oudot S.Y., « Only distances are required to reconstruct submanifolds », Computational Geometry, vol. 66, 2017, p. 32-67, DOI : 10.1016/j.comgeo.2017.08.001.

Haut de page

Pour citer cet article

Référence papier

Jean-Daniel Boissonnat, « Informatique et sciences numériques »L’annuaire du Collège de France, 117 | 2019, 555-565.

Référence électronique

Jean-Daniel Boissonnat, « Informatique et sciences numériques »L’annuaire du Collège de France [En ligne], 117 | 2019, mis en ligne le 04 juin 2020, consulté le 11 mai 2025. URL : http://journals.openedition.org/annuaire-cdf/14474 ; DOI : https://doi.org/10.4000/annuaire-cdf.14474

Haut de page

Auteur

Jean-Daniel Boissonnat

Directeur de recherche à l’Inria, professeur invité au Collège de France

Haut de page

Droits d’auteur

Le texte et les autres éléments (illustrations, fichiers annexes importés), sont « Tous droits réservés », sauf mention contraire.

Haut de page
Rechercher dans OpenEdition Search

Vous allez être redirigé vers OpenEdition Search