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