Détail d'une fiche   Version PDF

GAMBLE (SR0791BR)

Géométrie, Algorithmes et Modèles Bien au-delà du Linéaire et de l’Euclidien

GAMBLE (SR0769MR) →  GAMBLE


Statut: Décision signée

Responsable : Olivier Devillers

Mots-clés de "A - Thèmes de recherche en Sciences du numérique - 2024" : A5.5.1. Modélisation géométrique , A5.10.1. Conception , A7.1. Algorithmique , A8.1. Mathématiques discrètes, combinatoire , A8.3. Géométrie, Topologie , A8.4. Calcul formel, calcul algébrique

Mots-clés de "B - Autres sciences et domaines d'application - 2024" : B1.1.1. Biologie structurale , B1.2.3. Neurosciences computationnelles , B2.6. Imagerie biologique et médicale , B3.3. Géosciences , B5.5. Matériaux , B5.6. Systèmes robotiques , B5.7. Fabrication 3D , B6.2.2. Radio

Domaine : Algorithmique, programmation, logiciels et architectures
Thème : Algorithmique, calcul formel et cryptologie

Période : 01/07/2017 -> 30/06/2025
Dates d'évaluation : 19/03/2019 ,

Etablissement(s) de rattachement : U. DE LORRAINE
Laboratoire(s) partenaire(s) : LORIA (UMR7503)

CRI : Centre Inria de l'Université de Lorraine
Localisation : Centre Inria de l'Université de Lorraine
Code structure Inria : 051034-2

Numéro RNSR : 201722240E
N° de structure Inria: SR0791BR

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.

    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.


Axes de recherche

   Géométrie algorithmique non linéaire.
    Géométrie algorithmique non euclidienne.
    Probabilité et géométrie algorithmique.
    Structures géométriques discrètes.


Relations industrielles et internationales