méthodes PRobabilistes pour l'Éfficacité des Structures et Algorithmes GEométriques – PRESAGE

Notre modus operandi consiste à organiser des journées d'exposés (2 jours, 2 à 3 fois par an), des groupes de travail réunissant la majorité des participants pour une semaine (1 fois en 1ere et 2eme année) et des encadrements croisés (une thèse et un post-doc).

- Nouvelles analyses, plus simples ou plus précises, de complexité de structures géométriques (polytopes, triangulation de Delaunay, silhouette) induits par des processus ponctuels aléatoires.
- Nouvel algorithme de marche dans les triangulations. Il s'agit du premier algorithme ``non markovien'' dont on sait analyser la complexité sur des processus ponctuels Poissoniens.
- Analyse de séries aléatoires construites à base de diagrammes de Voronoi.
- Analyse de récurrence/transience de marches aléatoires dans des graphes géométriques.
- Développement d'un logiciel d'analyse efficace de propriétés statistiques d'ensembles de points aléatoires

Ce projet conduira à des avancées sur la théorie des structures géométriques aléatoires et à une meilleure compréhension du fonctionnement des algorithmes géométriques.

Les résultats de ce projet prennent la forme de publications (en conférences internationales et journaux avec comité de lecture), de formation de jeunes chercheurs (doctorants et post-doctorants) aux techniques des deux domaines, ou encore de production de package pour la bibliothèque logicielle CGAL.

CONTEXTE.
Les méthodes probabilistes sont omniprésentes en informatique et la géométrie algorithmique, la discipline qui s'intéresse à la conception et l'analyse d'algorithmes pour résoudre des problèmes géométriques, ne fait pas exception : des algorithmes aléatoirisés aux analyses en moyenne (ou leurs variantes récentes, les analyses lissées) en passant par la "loupe aléatoire" d'Erdös, les méthodes aléatoires ont eu un impact majeur.

Le plus souvent, les méthodes probabilistes sont mises en oeuvre en géométrie algorithmique par les géomètres algorithmiciens eux-mêmes. Cette mise en oeuvre requiert une compréhension fine des propriétés d'objets géométriques aléatoires, par ailleurs l'objet d'étude de la discipline de géométrie probabiliste en mathématiques. Étonnament, il y a jusqu'à présent eu très peu d'interaction entre géométrie algorithmique et géométrie probabiliste.


PRESENTATION.
L'objectif principal de ce projet est de réunir géomètres algorithmiques et probabilistes pour aborder ensemble de nouvelles questions de géométrie probabilistes issues de la conception et de l'analyse d'algorithmes et de structures de données géométriques. Cela conduira naturellement à de nouvelles pistes de recherche en géométrie probabiliste et à une meilleure compréhension des algorithmes et structures de données géométriques.

Le projet s'organise autour de l'étude de certaines structures discrètes induites par, ou sous-jacentes à, des objets géométriques continus aléatoires. Nous considérons trois types de questions :


* À quoi ressemble une structure géométrique (enveloppe convexe, mosaique, régions de visibilité...) aléatoire ?

* Comment mesurer et améliorer les performances d'algorithmes géométriques classiques sur les données "courantes" ?

* Comment générer aléatoirement des structures géométriques intéressantes ?


ORGANISATION.
Le projet implique trois partenaires, deux équipes de géomètres algorithmiciens (Sophia-Antipolis et Nancy) et une équipe de géomètres probabilistes (Rouen-Poitiers-Orléans).

L'interdisciplinarité est un aspect important de ce projet. En outre des visites mutuelles et journées de rencontres, nous nous assurerons qu'une réelle collaboration ait lieu en:
* organisant des seminaires de recherche les deux premières années; chaque séminaire réunira de 10 à 20 participants, étudiants ou chercheurs établis, afin de travailler une semaine sur des problèmes de recherche.
* financant une thèse co-encadrée par un informaticien (O. Devillers) et un mathematicien (P. Calka).