The Euclidean shortest path problem is a problem in
computational geometry: given a set of
polyhedral obstacles in a
Euclidean space
Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, that is, in Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics there are Euclidean sp ...
, and two points, find the shortest path between the points that does not intersect any of the obstacles.
Two dimensions
In two dimensions, the problem can be solved in
polynomial time
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
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
Dijkstra's algorithm ( ) is an algorithm for finding the shortest paths between nodes in a graph, which may represent, for example, road networks. It was conceived by computer scientist Edsger W. Dijkstra in 1956 and published three years ...
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
In three (and higher) dimensions the problem is
NP-hard
In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard pr ...
in the general case,
[
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.
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
A convex polytope is a special case of a polytope, having the additional property that it is also a convex set contained in the n-dimensional Euclidean space \mathbb^n. Most texts. use the term "polytope" for a bounded convex polytope, and the w ...
, 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
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.
See also
*
Shortest path problem
In graph theory, the shortest path problem is the problem of finding a path between two vertices (or nodes) in a graph such that the sum of the weights of its constituent edges is minimized.
The problem of finding the shortest path between t ...
, in a graph of edges and vertices
*
Any-angle path planning, in a grid space
Notes
References
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
*.
External links
Implementationof Euclidean Shortest Path algorithm in
Digital Geometric Kernel software
Geometric algorithms
Computational geometry
{{geometry-stub