« Plus court chemin euclidien » : différence entre les versions

Navigation interactive dans l’historique

← Modification précédente Modification suivante →

Contenu supprimé Contenu ajouté

Intégrés

Version du 11 mars 2023 à 12:29

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^[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

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

(en) Aleksandrov, Lyudmil ; Maheshwari, Anil ; Sack, Joerg, Determining Approximate Shortest Paths in Weighted Polyhedral Surfaces, 2005 (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, 1999 (lire en ligne), p. 215–224.
(en) Choi, Joonsoo ; Sellen, Jürgen ; Yap, Chee-Keng, Approximate Euclidean Shortest Path in 3-Space, 1994 (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, n^o 28 (6),‎ 1999, 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,‎ 1988 (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, n^o 18 (4),‎ 1997, p. 377–383 (DOI 10.1007/PL00009323).
(en) Lanthier, Mark ; Maheshwari, Anil ; Sack, Jörg-Rüdiger, Approximating shortest paths on weighted polyhedral surfaces, 2001 (lire en ligne), p. 527-562.
(en) Lee, D. T. ; Preparata, F. P., « Euclidean Shortest Paths in the Presence of Rectilinear Barriers », Networks, n^o 14 (3),‎ 1984, p. 393–410 (DOI 10.1002/net.3230140304).
(en) Li, Fajie ; Klette, Reinhard, Euclidean Shortest Paths: Exact or Approximate Algorithms, Springer-Verlag, 2011 (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, n^o 44 (1),‎ 1990, 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),‎ 1989, p. 9-42 (lire en ligne).

Articles connexes

Problème du plus court chemin, dans un graphe

Notes et références

↑ (en) J. Canny and J. H. Reif, New lower bound techniques for robot motion planning problems, 1987 (lire en ligne [PDF]), p. 49-60, Proc. 28th Annu. IEEE Sympos. Found. Comput. Sci.

Liens externes

(en) Implémentation de l'algorithme Euclidean Shortest Path dans le logiciel Digital Geometric Kernel

Portail de la géométrie

[1] (en) J. Canny and J. H. Reif, New lower bound techniques for robot motion planning problems, 1987 (lire en ligne [PDF]), p. 49-60, Proc. 28th Annu. IEEE Sympos. Found. Comput. Sci.

[1]

@@ Ligne 1 : / Ligne 1 : @@
-{{À wikifier|date=février 2023}}
 Le problème '''du plus court chemin euclidien''' est un problème de [[géométrie algorithmique]] : étant donné un ensemble d'obstacles [[Polyèdre|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 [[Complexité en temps|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 arithmétique|précision numérique]] nécessaire pour effectuer de tels calculs. Il existe deux approches. Une des approches repose sur la notion de  [[Graphique de visibilité|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 [[Algorithme de Dijkstra|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 deux dimensions, il existe des algorithmes qui résolvent le problème du plus court chemin euclidien en [[Complexité en temps|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 arithmétique|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 [[Algorithme de Dijkstra|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]]<ref>{{ouvrage|lang=en|auteurs=J. Canny and J. H. Reif|url=https://www.researchgate.net/profile/John_Canny2/publication/4355151_New_lower_bound_techniques_for_robot_motion_planning_problems/links/5581e03708ae6cf036c16ff3/New-lower-bound-techniques-for-robot-motion-planning-problems.pdf|titre=New lower bound techniques for robot motion planning problems|format=pdf|page=49-60|année=1987}}, Proc. 28th Annu. IEEE Sympos. Found. Comput. Sci.</ref>. 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.
-Au delà de trois dimensions, le problème est en général [[NP-difficile]]<ref>
-J. Canny and J. H. Reif, "[https://www.researchgate.net/profile/John_Canny2/publication/4355151_New_lower_bound_techniques_for_robot_motion_planning_problems/links/5581e03708ae6cf036c16ff3/New-lower-bound-techniques-for-robot-motion-planning-problems.pdf New lower bound techniques for robot motion planning problems]", Proc. 28th Annu. IEEE Sympos. Found. Comput. Sci., 1987, pp.
--60.
-</ref>. 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 [[Ensemble convexe|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 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 [[Ensemble convexe|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 {{nobr|3 dimensions}}.
 == Variantes ==
-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 ''[[Weighted region problem|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.
+Il existe une variante de ce problème, où les obstacles sont {{citation|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 {{citation|problème de la région pondérée}}, ou ''{{lang|en|weighted region problem}}'' dans la littérature. Le problème standard est alors le cas particulier où tous les obstacles ont un poids infini.
-== Voir aussi ==
+== Bibliographie ==
+* {{ouvrage|lang=en|auteurs=Aleksandrov, Lyudmil ; Maheshwari, Anil ; Sack, Joerg|année=2005|titre=Determining Approximate Shortest Paths in Weighted Polyhedral Surfaces|périodique=Journal of the ACM|numéro=52|page=25–53|doi=10.1145/1044731.1044733}}.
+* {{ouvrage|lang=en|auteurs=Chiang, Yi-Jen; Mitchell, Joseph S. B.|année=1999|titre=Two-point Euclidean Shortest Path Queries in the Plane|url=http://portal.acm.org/citation.cfm?id=314500.314560|périodique=Proc. 10th ACM-SIAM Symposium on Discrete Algorithms (SODA 1999)|page=215–224}}.
+* {{ouvrage|lang=en|auteurs=Choi, Joonsoo ; Sellen, Jürgen ; Yap, Chee-Keng|année=1994|titre=Approximate Euclidean Shortest Path in 3-Space|périodique=Proc. 10th ACM Symposium on Computational Geometry]]|page=41–48|doi=10.1145/177424.177501|10.1145/177424.177501|isbn=0-89791-648-4}}.
+* {{article|lang=en|auteurs=Hershberger, John ; Suri, Subhash|année=1999|titre=An Optimal Algorithm for Euclidean Shortest Paths in the Plane|périodique=SIAM Journal on Computing|numéro=28 (6)|page=2215–2256|éditeur=CiteSeerX|url=https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.47.2037 10.1.1.47.2037|doi=10.1137/S0097539795289604}}.
+* {{article|lang=en|auteurs=Kapoor, S. ; Maheshwari, S. N.|année=1988|titre=Efficient Algorithms for Euclidean Shortest Path and Visibility Problems with Polygonal Obstacles|périodique=Proc. 4th ACM Symposium on Computational Geometry]]'', pp. 172–182|doi=10.1145/73393.73411|isbn=0-89791-270-5}}.
+* {{article|lang=en|auteurs=Kapoor, S. ; Maheshwari, S. N.; Mitchell, Joseph S. B.|année=1997|titre=An Efficient Algorithm for Euclidean Shortest Paths Among Polygonal Obstacles in the Plane|périodique=Discrete and Computational Geometry|numéro=18 (4)|page=377–383|doi=10.1007/PL00009323}}.
+* {{ouvrage|lang=en|auteurs=Lanthier, Mark ; Maheshwari, Anil ; Sack, Jörg-Rüdiger|année=2001|url=http://link.springer.de/link/service/journals/00453/contents/01/0027/|titre=Approximating shortest paths on weighted polyhedral surfaces|périodique=Algorithmica|page=527-562}}.
+* {{article|lang=en|auteurs=Lee, D. T. ; Preparata, F. P.|année=1984|titre=Euclidean Shortest Paths in the Presence of Rectilinear Barriers|périodique=Networks|numéro=14 (3)|page=393–410|doi=10.1002/net.3230140304}}.
+* {{ouvrage|lang=en|auteurs=Li, Fajie ; Klette, Reinhard|année=2011|titre=Euclidean Shortest Paths: Exact or Approximate Algorithms|éditeur=Springer-Verlag|doi=10.1007/978-1-4471-2256-2|isbn=978-1-4471-2255-5}}.
+* {{article|lang=en|auteurs=Samuel, David, Toussaint, Godfried T.|année=1990|url=http://digitool.library.mcgill.ca/R/?func=dbin-jump-full&object_id=61805|titre=Computing the external geodesic diameter of a simple polygon|périodique=Computing|numéro=44 (1)|page=1–19|doi=10.1007/BF02247961}}.
+* {{article|lang=en|auteurs=Toussaint, Godfried T.|année=1989|url=http://cgm.cs.mcgill.ca/~godfried/publications/geodesic.pdf|titre=Computing geodesic properties inside a simple polygon|périodique=Revue d'intelligence artificielle, 3(2)|page=9-42}}.
+== Articles connexes ==
 * [[Problème de plus court chemin|Problème du plus court chemin]], dans un graphe
-* Planification de chemin sous n'importe quel angle, dans un espace de grille
-== Bibliographie ==
+== Notes et références ==
+{{Références}}
-* Aleksandrov, Lyudmil; Maheshwari, Anil; Sack, Joerg (2005), "Determining approximate shortest paths in weighted polyhedral surfaces", ''[[:en:Journal_of_the_ACM|Journal of the ACM]]'', '''52''': 25–53, doi:[[doi:10.1145/1044731.1044733|10.1145/1044731.1044733]]
-* Chiang, Yi-Jen; Mitchell, Joseph S. B. (1999), "Two-point Euclidean shortest path queries in the plane", ''[http://portal.acm.org/citation.cfm?id=314500.314560 Proc. 10th ACM-SIAM Symposium on Discrete Algorithms (SODA 1999)], pp. 215–224.''
-* Choi, Joonsoo; Sellen, Jürgen; Yap, Chee-Keng (1994), "Approximate Euclidean shortest path in 3-space", ''[[:en:Symposium_on_Computational_Geometry|Proc. 10th ACM Symposium on Computational Geometry]]'', pp. 41–48, doi:[[doi:10.1145/177424.177501|10.1145/177424.177501]], ISBN 0-89791-648-4.
-* Hershberger, John; [[:en:Subhash_Suri|Suri, Subhash]] (1999), "An optimal algorithm for Euclidean shortest paths in the plane", ''[[:en:SIAM_Journal_on_Computing|SIAM Journal on Computing]]'', '''28''' (6): 2215–2256, [[:en:CiteSeerX_(identifier)|CiteSeerX]] [https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.47.2037 10.1.1.47.2037], doi:[[doi:10.1137/S0097539795289604|10.1137/S0097539795289604]].
-* Kapoor, S.; Maheshwari, S. N. (1988), "Efficient algorithms for Euclidean shortest path and visibility problems with polygonal obstacles", ''[[:en:Symposium_on_Computational_Geometry|Proc. 4th ACM Symposium on Computational Geometry]]'', pp. 172–182, doi:[[doi:10.1145/73393.73411|10.1145/73393.73411]], ISBN 0-89791-270-5
-* Kapoor, S.; Maheshwari, S. N.; Mitchell, Joseph S. B. (1997), "An efficient algorithm for Euclidean shortest paths among polygonal obstacles in the plane", ''[[:en:Discrete_&_Computational_Geometry|Discrete & Computational Geometry]]'', '''18''' (4): 377–383, doi:[[doi:10.1007/PL00009323|10.1007/PL00009323]]
-* Lanthier, Mark; Maheshwari, Anil; [[:en:Jörg-Rüdiger_Sack|Sack, Jörg-Rüdiger]] (2001), "[http://link.springer.de/link/service/journals/00453/contents/01/0027/ Approximating shortest paths on weighted polyhedral surfaces]", [[:en:Algorithmica|Algorithmica]], pp. 527-562.
-* [[:en:Der-Tsai_Lee|Lee, D. T.]]; [[:en:Franco_P._Preparata|Preparata, F. P.]] (1984), "Euclidean shortest paths in the presence of rectilinear barriers", ''Networks'', '''14''' (3): 393–410, doi:[[doi:10.1002/net.3230140304|10.1002/net.3230140304]].
-* Li, Fajie; Klette, Reinhard (2011), ''Euclidean Shortest Paths: Exact or Approximate Algorithms'', [[:en:Springer-Verlag|Springer-Verlag]], doi:[[doi:10.1007/978-1-4471-2256-2|10.1007/978-1-4471-2256-2]], ISMB [[:en:Special:BookSources/978-1-4471-2255-5|978-1-4471-2255-5]]
-* Samuel, David; [[:en:Godfried_Toussaint|Toussaint, Godfried T.]] (1990), [http://digitool.library.mcgill.ca/R/?func=dbin-jump-full&object_id=61805 "Computing the external geodesic diameter of a simple polygon"], ''Computing'', '''44''' (1): 1–19, doi:[[doi:10.1007/BF02247961|10.1007/BF02247961]]
-* [[:en:Godfried_Toussaint|Toussaint, Godfried T.]] (1989), [http://cgm.cs.mcgill.ca/~godfried/publications/geodesic.pdf "Computing geodesic properties inside a simple polygon"], Revue d'intelligence artificielle, 3(2): 9-42.
 == Liens externes ==
+* {{en}} [http://www.dynoinsight.com/ESP.htm Implémentation] de l'algorithme Euclidean Shortest Path dans le logiciel Digital Geometric Kernel
-* [http://www.dynoinsight.com/ESP.htm Implémentation] de l'algorithme Euclidean Shortest Path dans le logiciel [[:en:Digital_Geometric_Kernel|Digital Geometric Kernel]]
-== Notes et références ==
-{{Références}}
 {{Portail|géométrie}}