Approximation algorithms for shortest path motion planning .
Given a set of polyhedral obstacles and points s and t , find a shortest path from s to t that avoids the obstacles. The paths found by the algorithms are piecewise linear, and the length of a path is the sum of the lengths of the line segments making up the path. Approximation algorithms will be given for versions of this problem in the plane and in three-dimensional space. Let n be the total number of faces of the polyhedral obstacles, and epsilon a given value satisfying 0 . The data structure is associated with a new variety of Voronoi diagram.