Euclidean shortest path
Encyclopedia
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.
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.
In three (and higher) dimensions the problem is NP-hard
in the general case
, 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.
Also, 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.
Computational geometry
Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems are also considered to be part of computational...
: given a set of polyhedral
Polyhedron
In elementary geometry a polyhedron is a geometric solid in three dimensions with flat faces and straight edges...
obstacles in a Euclidean space
Euclidean space
In mathematics, Euclidean space is the Euclidean plane and three-dimensional space of Euclidean geometry, as well as the generalizations of these notions to higher dimensions...
, and two points, find the shortest path between the points that does not intersect any of the obstacles.
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
Dijkstra's algorithm
Dijkstra's algorithm, conceived by Dutch computer scientist Edsger Dijkstra in 1956 and published in 1959, is a graph search algorithm that solves the single-source shortest path problem for a graph with nonnegative edge path costs, producing a shortest path tree...
on a visibility graph
Visibility graph
In computational geometry and robot motion planning, a visibility graph is a graph of intervisible locations, typically for a set of points and obstacles in the Euclidean plane. Each node in the graph represents a point location, and each edge represents a visible connection between them...
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.
In three (and higher) dimensions the problem is NP-hard
NP-hard
NP-hard , in computational complexity theory, is a class of problems that are, informally, "at least as hard as the hardest problems in NP". A problem H is NP-hard if and only if there is an NP-complete problem L that is polynomial time Turing-reducible to H...
in the general case
, 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.
Also, 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.