ABSTRACT
In this paper we present an approximation algorithm for solving the following optimal motion planning prob lem: Given a planar space composed of triangular re gions, each of which is associated with a positive unit weight, and two points s and t, find a path from s to t with the minimum weight, where the weight of a path is defined to be the weighted sum of the lengths of the sub-paths within each region.
