Analyse et Simulation Probabilistes des Algorithmes Géométriques – ASPAG

L'analyse et le traitement des données géométriques est maintenant indispensable à un bon nombre d'activités allant de la conception et de l'usinage assistés par ordinateur au suivi de trajectoires animales en écologie ou à l'analyse de traces GPS issues des systèmes de navigation automobile. La géométrie algorithmique et les modèles probabilistes géométriques sont cruciaux pour le traitement de toutes ces données géométriques, cependant les connaissances actuelles se heurtent à plusieurs limitations: les modèles sont encore loin de coller à la réalité, et les analyses de complexité s'avèrent peu pertinentes dans nombre de situations pratiques. Une des raisons de cette situation est que l'expertise nécessaire est dispersée dans plusieurs communautés scientifiques (géométrie algorithmique, analyse d'algorithmes, géométrie stochastique) qui n'ont historiquement eu que très peu d'interactions. Le projet ASPAG réunit des experts de ces trois communautés pour s'attaquer efficacement à ce problème via les trois directions de recherches interdépendantes suivantes.

(1) Ensembles de points dépendants. Un aspect crucial de beaucoup de modèles est l'hypothèse que les points sont générés indépendamment suivant la même distribution. Même s'il peut s'avérer intéressant dans certains contextes, l'indépendance est une contrainte trop forte pour de nombreuses applications.

(2) Simulation efficace de structures géométriques aléatoires. Au vu de la difficulté des problèmes abordés en (1), il apparaît primordial de développer
des outils appropriés pour nous aider dans la compréhension des phénomènes. Une première étape naturelle consiste à développer notre intuition et à identifier de potentielles conjectures via les simulations. De manière surprenante, les outils nécessaires à la simulation efficace de telles systèmes géométriques complexes doivent encore être développés.

(3) Analyse réaliste des algorithmes géométriques. L'analyse des algorithmes est une étape essentielle dans l'évaluation des forces et des
faiblesses des principes algorithmiques, et est cruciale pour guider les choix lors de la conception d'une chaine complexe de traitement de données. Toute analyse se doit d'obtenir un équilibre entre réalisme et difficulté; les analyses actuellement disponibles se démarquent par leur manque de réalisme.

Mis à part les objectifs purement scientifiques, ASPAG visera à la restructuration des communautés de manière à les rapprocher durablement. C'est pourquoi le financement du projet est crucial pour assurer la collaboration régulière des membres du consortium, une condition nécessaire à des progrès significatifs sur les défis énoncés plus haut.