@inproceedings{e87f2e6f9322428bbde8822d1fafc4c9,
title = "Path planning in 0/1/∞ weighted regions with applications",
abstract = "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 O(n2) 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 O(n2W) algorithm for finding lexicographically shortest paths in weighted regions (with W different weights); (2) an O(k2n2) algorithm for planning least-risk paths in a simple polygon that contains k line-of-sight threats (this becomes O(k4n4) in polygons with holes); and (3) an O(k2n3) 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).",
author = "Laxmi Gewali and Alex Meng and Mitchell, \{Joseph S.B.\} and Simeon Ntafos",
year = "1988",
month = jan,
day = "6",
doi = "10.1145/73393.73421",
language = "English",
series = "Proceedings of the 4th Annual Symposium on Computational Geometry, SCG 1988",
publisher = "Association for Computing Machinery, Inc",
pages = "266--278",
booktitle = "Proceedings of the 4th Annual Symposium on Computational Geometry, SCG 1988",
note = "4th Annual Symposium on Computational Geometry, SCG 1988 ; Conference date: 06-06-1988 Through 08-06-1988",
}