The Euclidean shortest path problem is a problem in computational geometry: given a set of polyhedral obstacles in a Euclidean space, and two points, find the shortest path between the points that does not intersect any of the obstacles.
Example of a shortest path in a three-dimensional Euclidean space
In two dimensions, the problem can be solved in polynomial time in a model of computation allowing addition and comparisons of real numbers, despite theoretical difficulties involving the numerical precision needed to perform such calculations. These algorithms are based on two different principles, either performing a shortest path algorithm such as Dijkstra's algorithm on a visibility graph derived from the obstacles or (in an approach called the continuous Dijkstra method) propagating a wavefront from one of the points until it meets the other.
Higher dimensionsedit
In three (and higher) dimensions the problem is NP-hard in the general case,[1] but there exist efficient approximation algorithms that run in polynomial time based on the idea of finding a suitable sample of points on the obstacle edges and performing a visibility graph calculation using these sample points.
There are many results on computing shortest paths which stays on a polyhedral surface. Given two points s and t, say on the surface of a convex polyhedron, the problem is to compute a shortest path that never leaves the surface and connects s with t. This is a generalization of the problem from 2-dimension but it is much easier than the 3-dimensional problem.
Variantsedit
There are variations of this problem, where the obstacles are weighted, i.e., one can go through an obstacle, but it incurs an extra cost to go through an obstacle. The standard problem is the special case where the obstacles have infinite weight. This is termed as the weighted region problem in the literature.
^ J. Canny and J. H. Reif, "New lower bound techniques for robot motion planning problems", Proc. 28th Annu. IEEE Sympos. Found. Comput. Sci., 1987, pp. 49-60.
Referencesedit
Aleksandrov, Lyudmil; Maheshwari, Anil; Sack, Joerg (2005), "Determining approximate shortest paths in weighted polyhedral surfaces", Journal of the ACM, 52: 25–53, doi:10.1145/1044731.1044733, S2CID 697658.
Chiang, Yi-Jen; Mitchell, Joseph S. B. (1999), "Two-point Euclidean shortest path queries in the plane", Proc. 10th ACM-SIAM Symposium on Discrete Algorithms (SODA 1999), pp. 215–224, ISBN9780898714340.
Hershberger, John; Suri, Subhash (1999), "An optimal algorithm for Euclidean shortest paths in the plane", SIAM Journal on Computing, 28 (6): 2215–2256, CiteSeerX10.1.1.47.2037, doi:10.1137/S0097539795289604.
Kapoor, S.; Maheshwari, S. N.; Mitchell, Joseph S. B. (1997), "An efficient algorithm for Euclidean shortest paths among polygonal obstacles in the plane", Discrete & Computational Geometry, 18 (4): 377–383, doi:10.1007/PL00009323.
Lanthier, Mark; Maheshwari, Anil; Sack, Jörg-Rüdiger (2001), "Approximating shortest paths on weighted polyhedral surfaces", Algorithmica, pp. 527–562.
Lee, D. T.; Preparata, F. P. (1984), "Euclidean shortest paths in the presence of rectilinear barriers", Networks, 14 (3): 393–410, doi:10.1002/net.3230140304.
euclidean, shortest, path, problem, problem, computational, geometry, given, polyhedral, obstacles, euclidean, space, points, find, shortest, path, between, points, that, does, intersect, obstacles, example, shortest, path, three, dimensional, euclidean, space. The Euclidean shortest path problem is a problem in computational geometry given a set of polyhedral obstacles in a Euclidean space and two points find the shortest path between the points that does not intersect any of the obstacles Example of a shortest path in a three dimensional Euclidean space Contents 1 Two dimensions 2 Higher dimensions 3 Variants 4 See also 5 Notes 6 References 7 External linksTwo dimensions editIn two dimensions the problem can be solved in polynomial time in a model of computation allowing addition and comparisons of real numbers despite theoretical difficulties involving the numerical precision needed to perform such calculations These algorithms are based on two different principles either performing a shortest path algorithm such as Dijkstra s algorithm on a visibility graph derived from the obstacles or in an approach called the continuous Dijkstra method propagating a wavefront from one of the points until it meets the other Higher dimensions editIn three and higher dimensions the problem is NP hard in the general case 1 but there exist efficient approximation algorithms that run in polynomial time based on the idea of finding a suitable sample of points on the obstacle edges and performing a visibility graph calculation using these sample points There are many results on computing shortest paths which stays on a polyhedral surface Given two points s and t say on the surface of a convex polyhedron the problem is to compute a shortest path that never leaves the surface and connects s with t This is a generalization of the problem from 2 dimension but it is much easier than the 3 dimensional problem Variants editThere are variations of this problem where the obstacles are weighted i e one can go through an obstacle but it incurs an extra cost to go through an obstacle The standard problem is the special case where the obstacles have infinite weight This is termed as the weighted region problem in the literature See also editShortest path problem in a graph of edges and vertices Any angle path planning in a grid spaceNotes edit J Canny and J H Reif New lower bound techniques for robot motion planning problems Proc 28th Annu IEEE Sympos Found Comput Sci 1987 pp 49 60 References editAleksandrov Lyudmil Maheshwari Anil Sack Joerg 2005 Determining approximate shortest paths in weighted polyhedral surfaces Journal of the ACM 52 25 53 doi 10 1145 1044731 1044733 S2CID 697658 Chiang Yi Jen Mitchell Joseph S B 1999 Two point Euclidean shortest path queries in the plane Proc 10th ACM SIAM Symposium on Discrete Algorithms SODA 1999 pp 215 224 ISBN 9780898714340 Choi Joonsoo Sellen Jurgen Yap Chee Keng 1994 Approximate Euclidean shortest path in 3 space Proc 10th ACM Symposium on Computational Geometry pp 41 48 doi 10 1145 177424 177501 ISBN 0 89791 648 4 S2CID 69747 Hershberger John Suri Subhash 1999 An optimal algorithm for Euclidean shortest paths in the plane SIAM Journal on Computing 28 6 2215 2256 CiteSeerX 10 1 1 47 2037 doi 10 1137 S0097539795289604 Kapoor S Maheshwari S N 1988 Efficient algorithms for Euclidean shortest path and visibility problems with polygonal obstacles Proc 4th ACM Symposium on Computational Geometry pp 172 182 doi 10 1145 73393 73411 ISBN 0 89791 270 5 S2CID 9599057 Kapoor S Maheshwari S N Mitchell Joseph S B 1997 An efficient algorithm for Euclidean shortest paths among polygonal obstacles in the plane Discrete amp Computational Geometry 18 4 377 383 doi 10 1007 PL00009323 Lanthier Mark Maheshwari Anil Sack Jorg Rudiger 2001 Approximating shortest paths on weighted polyhedral surfaces Algorithmica pp 527 562 Lee D T Preparata F P 1984 Euclidean shortest paths in the presence of rectilinear barriers Networks 14 3 393 410 doi 10 1002 net 3230140304 Li Fajie Klette Reinhard 2011 Euclidean Shortest Paths Exact or Approximate Algorithms Springer Verlag doi 10 1007 978 1 4471 2256 2 ISBN 978 1 4471 2255 5 Samuel David Toussaint Godfried T 1990 Computing the external geodesic diameter of a simple polygon Computing 44 1 1 19 doi 10 1007 BF02247961 S2CID 31450333 Toussaint Godfried T 1989 Computing geodesic properties inside a simple polygon PDF Revue d Intelligence Artificielle 3 2 9 42 External links editImplementation of Euclidean Shortest Path algorithm in Digital Geometric Kernel software nbsp This combinatorics related article is a stub You can help Wikipedia by expanding it vte nbsp This geometry related article is a stub You can help Wikipedia by expanding it vte Retrieved from https en wikipedia org w index php title Euclidean shortest path amp oldid 1154732502, wikipedia, wiki, book, books, library,
