Plus court chemin euclidien
La mise en forme de cet article est à améliorer ().
La mise en forme du texte ne suit pas les recommandations de Wikipédia : il faut le « wikifier ».
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[modifier | modifier le code]
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[modifier | modifier le code]
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.
Variantes[modifier | modifier le code]
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.
Bibliographie[modifier | modifier le code]
- (en) Aleksandrov, Lyudmil ; Maheshwari, Anil ; Sack, Joerg, Determining Approximate Shortest Paths in Weighted Polyhedral Surfaces, (DOI 10.1145/1044731.1044733), chap. 52, p. 25–53.
- (en) Chiang, Yi-Jen; Mitchell, Joseph S. B., Two-point Euclidean Shortest Path Queries in the Plane, (lire en ligne), p. 215–224.
- (en) Choi, Joonsoo ; Sellen, Jürgen ; Yap, Chee-Keng, Approximate Euclidean Shortest Path in 3-Space, (ISBN 0-89791-648-4, DOI 10.1145/177424.177501), p. 41–48.
- (en) Hershberger, John ; Suri, Subhash, « An Optimal Algorithm for Euclidean Shortest Paths in the Plane », SIAM Journal on Computing, CiteSeerX, no 28 (6), , p. 2215–2256 (DOI 10.1137/S0097539795289604, lire en ligne).
- (en) Kapoor, S. ; Maheshwari, S. N., « Efficient Algorithms for Euclidean Shortest Path and Visibility Problems with Polygonal Obstacles », Proc. 4th ACM Symposium on Computational Geometry, pp. 172–182, (ISBN 0-89791-270-5, DOI 10.1145/73393.73411).
- (en) Kapoor, S. ; Maheshwari, S. N.; Mitchell, Joseph S. B., « An Efficient Algorithm for Euclidean Shortest Paths Among Polygonal Obstacles in the Plane », Discrete and Computational Geometry, no 18 (4), , p. 377–383 (DOI 10.1007/PL00009323).
- (en) Lanthier, Mark ; Maheshwari, Anil ; Sack, Jörg-Rüdiger, Approximating shortest paths on weighted polyhedral surfaces, (lire en ligne), p. 527-562.
- (en) Lee, D. T. ; Preparata, F. P., « Euclidean Shortest Paths in the Presence of Rectilinear Barriers », Networks, no 14 (3), , p. 393–410 (DOI 10.1002/net.3230140304).
- (en) Li, Fajie ; Klette, Reinhard, Euclidean Shortest Paths: Exact or Approximate Algorithms, Springer-Verlag, (ISBN 978-1-4471-2255-5, DOI 10.1007/978-1-4471-2256-2).
- (en) Samuel, David, Toussaint, Godfried T., « Computing the external geodesic diameter of a simple polygon », Computing, no 44 (1), , p. 1–19 (DOI 10.1007/BF02247961, lire en ligne).
- (en) Toussaint, Godfried T., « Computing geodesic properties inside a simple polygon », Revue d'intelligence artificielle, 3(2), , p. 9-42 (lire en ligne).
Articles connexes[modifier | modifier le code]
- Problème du plus court chemin, dans un graphe
Notes et références[modifier | modifier le code]
- (en) J. Canny and J. H. Reif, New lower bound techniques for robot motion planning problems, (lire en ligne [PDF]), p. 49-60, Proc. 28th Annu. IEEE Sympos. Found. Comput. Sci.
Liens externes[modifier | modifier le code]
- (en) Implémentation de l'algorithme Euclidean Shortest Path dans le logiciel Digital Geometric Kernel
