Séminaire MACS (Modélisation, Analyse et Calcul Scientifique). Commun ICJ & UMPA.

Calcul de plus courts chemins sur des variétés: méthodes numériques efficaces et applications.

par Jean-Marie Mirebeau (CNRS)

Europe/Paris
4e étage, salle 435 (UMPA, ENS Lyon - Site Monod)

4e étage, salle 435

UMPA, ENS Lyon - Site Monod

ENS de Lyon, 46 Allée d'Italie
Description
Le fast marching est un algorithme efficace pour la résolution de l'équation eikonale, qui permet de calculer le plus court chemin entre deux points d'un domaine de R^d. Ses applications sont nombreuses, et vont de la planification de mouvement à la segmentation d'images médicales. L'unité de longueur, pour la mesure du chemin, peut varier dans le domaine. Motivés par certaines applications, nous généralisons l'algorithme au cas où l'unité de longueur dépend également de la direction, voire de l'orientation du chemin. Un conflit apparait entre cette géométrie anisotrope et la grille cartésienne utilisée pour la discrétisation. Son étude fait intervenir des outils élégants et peu communs en analyse des EDP, allant de la classification des réseaux euclidiens à l'arbre de Stern-Brocot (qui répartit les nombres rationnels aux noeuds d'un arbre binaire complet infini).