Plus court chemin euclidien

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.

Au-delà de trois dimensions, le problème est en général NP-difficile^[1]. 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 3 dimensions.

Il existe une variante de ce problème, où les obstacles sont « pondérés ». Dans ce problème, un obstacle peut être traversé, mais cela entraîne un surcoût. C'est ce qu'on appelle le « problème de la région pondérée », ou weighted region problem dans la littérature. Le problème standard est alors le cas particulier où tous les obstacles ont un poids infini.