Path Planning in 0/1/∞ Weighted Regions with Applications

We consider the terrain navigation problem in a two-dimensional polygonal subdivision with three types of regions: obstacles, “free” regions (in which one can travel at no cost), and regions in which cost is proportional to distance traveled. We present an algorithm whose running time is O(E + nlog n), where n is the number of vertices representing the subdivision, and E is bounded above by the size of the visibility graph induced by the set of obstacles and free regions, which is no worse than quadratic (O(n²)). In addition, we present algorithms to solve a variety of important generalizations and applications: (1) an O(n²) algorithm for constructing a critical graph of size O(n²) (which can be searched in time O(n²log n) for shortest paths) for the case in which linear features (roads) are added, thereby allowing arbitrary weights on the edges of the subdivision; (2) similar time bounds for the case in which the linear features include a possible “cost of crossing”; (3) an O(n²W) algorithm for finding lexicographically shortest paths in weighted regions (with W different weights); (4) an O(k²n²) algorithm for planning least-risk paths in a simple polygon that contains k line-of-sight threats (this becomes O(k⁴n⁴) in polygons with holes); and (5) an O(k²n³) 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).

INFORMS Journal on Computing, ISSN 1091-9856, was published as ORSA Journal on Computing from 1989 to 1995 under ISSN 0899-1499.