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.

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.

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.

The standard problem is the special case where the obstacles have infinite weight.