Euclidean shortest path
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. == Two dimensions == 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.