GAMBLE

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.

    Structures géométriques discrètes. De nombreux algorithmes géométriques fonctionnent, explicitement ou implicitement, sur des structures discrètes telles que des graphes, des hypergraphes, des treillis qui sont définies à partir de données géométriques. Par exemple, les enveloppes convexes ou les dessins graphes sont essentiellement basés sur des prédicats d'orientation, et fonctionnent donc sur le type d'ordre de l'ensemble des points d'entrée. Les types d'ordre sont une sous-classe de matroïdes orientés qui reste mal comprise : par exemple, nous ne savons même pas comment échantillonner cet espace avec un biais raisonnable. L'un de nos objectifs est de contribuer au développement de ces bases en comprenant mieux ces structures géométriques discrètes.