Algorithms to construct optimal-path maps for single isolated homogeneous-cost convex-polygonal regions are discussed. Assuming the ability to construct optimal paths for a certain set of key points, a complete analysis is given of one of the four possible single-region situations, showing how to partition the map into regions of similar path behavior. An algorithm is then proposed for constructing optimal-path maps for multiple such regions, in the case that they meet certain decomposability constraints. This algorithm is of O(n/sup 4/) time complexity and O(n) space complexity, where n is the number of vertices in a polygonal model of the terrain as homogeneous-cost regions. The algorithm greatly simplifies planning of paths through areas of terrain with near-uniform characteristics, allowing a robot to exploit optimal paths but still have significant time for other matters.>