Shortest Paths in Euclidean spaces

Sanjiv Kapoor (IIT Delhi)
The Shortest Path problem in Euclidean domains is an important problem for terrain navigation and path planning which arise in Motion Planning. Both 2-dimensional and 3-dimensional Path Planning problems have been well studied. This talk will first describe solutions to the shortest path problem in 2-dimensional Euclidean space, populated with polygonal obstacles. The technique of wavefront propogation will be discussed. and we will describe solutions to the geodesic path problem on the surface of a 3-dimensional polyhedron. The problem, of obvious interest in terrain navigation, had previously been shown to have complexity O(n²). We will outline a solution of complexity O(nlog²n). Extensions of the methodology to the Weighted regions shortest path problem will also be discussed.