Sites Inria

English version

Equipe de recherche GEOMETRICA

Calcul géométrique

  • Responsable : Jean-daniel Boissonnat
  • Centre(s) de recherche : CRI Sophia Antipolis - Méditerranée
  • Domaine : Algorithmique, programmation, logiciels et architectures
  • Thème : Algorithmique, calcul formel et cryptologie

Présentation de l'équipe

GEOMETRICA a pour objectif de développer un cadre théorique et expérimental pour le calcul géométrique effectif.

Le calcul géométrique est resté longtemps limité à l'ingénierie, et principalement à la conception et la fabrication assistées par ordinateur. Les progrès technologiques récents bouleversent cette situation.

  • Les nouveaux systèmes de mesure, scanners, télémètres, imageurs 3D, permettent de mesurer des formes tridimensionnelles très variées et complexes, anatomiques, géologiques ou architecturales par exemple.
  • Les performances graphiques des ordinateurs progressent de manière spectaculaire aussi bien sur les PC, les consoles de jeux que sur les systèmes de réalité virtuelle haut de gamme.
  • Le développement des réseaux et de l'Internet et l'essor de nouvelles activités dans le domaine commerce électronique, du télétravail ou des jeux entrainent la transmission et l'échange d'objets géométriques complexes.
  • De nouveaux procédés de fabrication d'objets tridimensionnels comme la stéréolithographie conduisent à de véritables imprimantes 3D.
Ces changements technologiques rendent possible ce qui ne l'avait jamais été auparavant : la création de modèles tridimensionnels facilement observables, transmissibles, reproductibles, modifiables. Ils apportent aux ingénieurs de nouveaux modes de conception et fabrication comme les maquettes numériques, le prototypage rapide, l'ingénierie inverse. Ils ouvrent aussi de nouveaux champs d'application au calcul géométrique comme la modélisation géométrique d'objets non manufacturés, la simulation et la planification d'interventions chirurgicales, le docking et le repliement de molécules en biologie moléculaire.

Les objets géométriques tridimensionnels envahissent également notre vie quotidienne à travers les jeux vidéo et le multimédia. Leur arrivée sur les réseaux va avoir un impact sur le commerce électronique, sur l'éducation et la culture, via le télé-enseignement et les visites virtuelles, et sur le travail à distance : en médecine notamment, la réunion d'experts en réseaux disposant de moyens de visualisation 3D sera demain une réalité.

Les objets géométriques sont amenés à jouer un rôle comparable à celui des images. Parallèlement, le calcul géométrique se voit prendre une importance sans précédent en même temps qu'il doit faire face à des problèmes d'une complexité et d'une variété beaucoup plus grandes que par le passé. Les questions combinatoires et algorithmiques deviennent critiques et de nouveaux sujets apparaissent comme l'échantillonnage et l'approximation de formes complexes, leur codage, leur transmission.

Axes de recherche

Le programme de recherche s'articule autour de trois axes :
  • conception et analyse de structures de données et d'algorithmes géométriques,
  • calcul fiable et programmation avancée,
  • approximation de formes, maillages, codage et transmission.

Structures de données et algorithmes géométriques. La géométrie algorithmique a jusque là essentiellement considéré la géométrie linéaire et très peu les objets plus complexes. Un des objectifs de GEOMETRICA est de contribuer au développement de la géométrie algorithmique des objets courbes. GEOMETRICA s'intéresse en particulier aux diagrammes de Voronoï non affines qui interviennent en recherche opérationnelle, en biologie, et dans les maillages.

Calcul et programmation. Les questions d'architecture logicielle, de fiabilité et de performances pratiques sont devenues un champ essentiel de la recherche en géométrie algorithmique. GEOMETRICA s'intéresse au problème de la robustesse des algorithmes géométriques vis-à-vis des erreurs d'arrondis et mène notamment des recherches sur le calcul exact efficace, les arithmétiques dédiées, et les constructions à précision fixée. GEOMETRICA est également un des principaux acteurs du développement de la bibliothèque d'algorithmes géométriques CGAL. CGAL est à la fois une plate-forme de recherches et un excellent vecteur de diffusion des techniques développées.

Approximation. Les formes complexes ne peuvent qu'être approchées. Pour des besoins très différents et avec des contraintes qui leur sont propres, l'analyse numérique, l'informatique graphique, la robotique doivent discrétiser leurs objets d'étude. Inversement, la reconstruction de surfaces exige d'interpoler des formes à partir d'échantillons. GEOMETRICA veut développer une théorie de l'approximation géométrique, et s'intéresse à des questions comme l'échantillonnage, la géométrie différentielle des objets discrets, le contrôle topologique et géométrique des approximations, et la représentation des objets à différentes échelles. Dans le contexte des réseaux, l'approximation des objets géométriques revêt de nouveaux aspects. GEOMETRICA s'intéresse à la compression et à la transmission progressive.

Applications

Les domaines d'application de la géométrie algorithmique sont très variés. GEOMETRICA s'intéresse principalement à quatre secteurs pour lesquels la géométrie algorithmique a apporté récemment des contributions décisives : la modélisation géométrique, le calcul scientifique, les télécommunications et la biologie structurale. Les apports attendus des techniques de la géométrie algorithmique sont de plusieurs types : l'introduction de nouvelles structures de données, des analyses rigoureuses de la complexité et de la qualité des solutions proposées, des implémentations robustes et efficaces.

Logiciels

Relations industrielles et internationales

Nos collaborations les plus étroites se font au niveau européen. L'équipe-projet GEOMETRICA (ou le projet PRISME avant lui) ont participé à de nombreux projets européens traitant de géométrie algorithmique qui lui ont permis de nouer des collaborations avec les meilleures équipes européennes du domaine.

La bibliothèque CGAL a conduit à la création d'une start-up, Geometry factory qui commercialise CGAL.

Mots-clés : Algorithmes et structures de données Calcul fiable Approximation et maillages

Suivez Inria