Sites Inria

English version

Equipe de recherche GAMBLE

Geometric Algorithms and Models Beyond the Linear and Euclidean realm

Présentation de l'équipe

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.

Axes de recherche

    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.

Mots-clés : Géométrie algorithmique Calcul formel Probabilité Géométrie hyperbolique.

Suivez Inria tout au long de son 50e anniversaire et au-delà !