Département 1 : Algorithme, calcul, image et géométrie

Responsable de l’équipe : Olivier Devillers
Tél. : 03 54 95 85 25
Mail : olivier.devillers@loria.fr

Site de l’équipe

Présentation

La géométrie algorithmique classique traite habituellement d’objets linéaires dans un cadre euclidien. Quand d’autres situations surviennent, les objets courbes sont généralement linéarisés, les espace non euclidiens approximés localement par des espaces euclidiens. Les objectifs de l’équipe GAMBLE sont de dépasser ces limitations de la géométrie algorithmique classique.

Géométrie algorithmique non linéaire. Les objets courbes peuplent le monde qui nous entoure. Cependant, malgré des dizaines d’années de recherche, les objets courbes ne sont pas appréhendés de manière robuste ni efficace par les algorithmes géométriques. Notre travail, par exemple sur les intersections de quadriques ou sur le tracé certifié de courbes planes, a démontré que des améliorations substantielles pouvaient être obtenues quand les bonnes notion de mathématique et d’informatique étaient utilisées. Dans cette direction, nombre de problèmes sont fondamentaux et leurs solutions ont un potentiel impact industriel, par exemple en CAO ou en robotique. L’intersection de NURBS et le maillage certifié de surfaces singulières sont des exemples de tels problèmes.

Géométrie algorithmique non euclidienne. Les triangulations sont une structure de données de première importance dans de nombreux domaines de la science et de l’ingénierie. Le besoin de triangulation dans un cadre non euclidien a émergé dans plusieurs domaines traitant d’objets dont la taille varie de l’atome à l’amas de galaxies, tant dans le monde académique qu’industriel. Il est temps d’étendre la géométrie algorithmique hors du cadre usuel Rd et de prendre en compte des espaces non euclidiens.

Probabilité et géométrie algorithmique. La conception d’algorithmes efficaces est dirigée par l’analyse de leur complexité. Traditionnellement, le cas le pire, et parfois le cas de distributions uniformes, sont utilisés et les résultats obtenus dans ce contexte ont eu une grande influence sur le domaine. Il est maintenant nécessaire d’être plus subtil et de trouver de nouveaux résultats entre  ces deux modèles de complexité extrêmes. Par exemple, l’analyse lissée introduite pour l’algorithme du simplex a été utilisée pour l’analyse de l’enveloppe convexe et démontre que des alternatives prometteuses existent.

Axes thématiques

• Géométrie algorithmique non linéaire.
• Géométrie algorithmique non euclidienne.
• Probabilité et géométrie algorithmique.

Logiciels

• QI
• Isotop
• Cgal

Collaborations

• De nombreux coauteurs à l’échelle internationale
• University of Victoria, University Carleton
• IRCCyN (Nantes), LIGM (Marne la Vallée)
• Équipes INRIA DataShape (Saclay) et Ouragan (Paris)

Mots-clés

Géométrie algorithmique, triangulation de Delaunay, diagrammes de Voronoi, visualisation de courbes et surfaces.