Le problème du plus court chemin euclidien est un problème de géométrie algorithmique : étant donné un ensemble d'obstacles polyédriques dans un espace euclidien, et deux points, trouver un plus court chemin les reliant en évitant les obstacles.
En deux dimensions En deux dimensions, il existe des algorithmes qui résolvent le problème du plus court chemin euclidien en temps polynomial. Dans ces algorithmes, on suppose que le modèle de calcul sous-jacent permet l'addition et les comparaisons de nombres réels, malgré les difficultés théoriques liées à la précision numérique nécessaire pour effectuer de tels calculs. Il existe deux approches : Une des approches repose sur la notion de graphe de visibilité dérivé des obstacles. On calcule d'abord un graphe de visibilité, puis on effectue un algorithme du plus court chemin dans un graphe tel que l'algorithme de Dijkstra ou l'algorithme A*. L'autre approche s'appelle la méthode continue de Dijkstra : elle consiste à propager un front d'onde depuis l'un des points jusqu'à ce qu'il en rencontre d'autres.
En dimensions supérieures Au-delà de trois dimensions, le problème est en général NP-difficile, Proc. 28th Annu. IEEE Sympos. Found. Comput. Sci.. Cependant, il existe des algorithmes d'approximation efficaces qui s'exécutent en temps polynomial basés sur l'idée de trouver un échantillon approprié de points sur les bords de l'obstacle et d'effectuer un calcul du graphe de visibilité à l'aide de ces points d'échantillonnage.
Il existe de nombreux résultats sur le calcul des plus courts chemins qui restent sur une surface d'un polyèdre. Étant donné deux points s et t, supposés sur la même surface d'un polyèdre convexe, le problème est de calculer un plus court chemin qui ne quitte jamais cette surface et qui relie s à t. Il s'agit d'une généralisation du problème en 2 dimensions, mais reste beaucoup plus facile que le problème en .
Variantes Il existe une variante de ce problème, où les obstacles sont . Dans ce problème, un obstacle peut être traversé, mais cela entraîne un surcoût. C'est ce qu'on appelle le , ou dans la littérature. Le problème standard est alors le cas particulier où tous les obstacles ont un poids infini.
Bibliographie . . . . . . . . . . .
Notes et références
Voir aussi Articles connexes Problème du plus court chemin, dans un graphe
Liens externes Implémentation de l'algorithme Euclidean Shortest Path dans le logiciel Digital Geometric Kernel
Catégorie:Géométrie algorithmique