path planning in 0/1/ weighted regions with applications
We consider the terrain navigation problem in a two-dimensional polygonal subdivision consisting of obstacles, free regions (in which one can travel at no cost), and regions in which cost is proportional to distance traveled. This problem is a special case of the weighted region problem and is a generalization of the well-known planar shortest path problem in the presence of obstacles. We present an &Ogr;(n 2 ) exact algorithm for this problem and faster algorithms for the cases of convex free regions and/or obstacles. We generalize our algorithm to allow arbitrary weights on the edges of the subdivision. In addition, we present algorithms to solve a variety of important applications: (1) an &Ogr;(n 2 W) algorithm for finding lexicographically shortest paths in weighted regions (with W different weights); (2) an &Ogr;(k 2 n 2 ) algorithm for planning least-risk paths in a simple polygon that contains k line-of-sight threats (this becomes &Ogr;(k 4 n 4 ) in polygons with holes); and (3) an &Ogr;(k 2 n 3 ) algorithm for finding least-risk watchman routes in simple rectilinear polygons (a watchman route is such that each point in the polygon is visible from at least one point along the route).
path planning plan region applications navigation polygon subdivision cost distance case general shortest path presence algorithm routing point risk