Name
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 &Ogr;(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 &Ogr;(n2W) algorithm for finding lexicographically shortest paths in weighted regions (with W different weights); (2) an &Ogr;(k2n2) algorithm for planning least-risk paths in a simple polygon that contains k line-of-sight threats (this becomes &Ogr;(k4n4) in polygons with holes); and (3) an &Ogr;(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). |
Year | DOI | Venue |
|---|---|---|
1990 | 10.1145/73393.73421 | SCG '88 Proceedings of the fourth annual symposium on Computational geometry |
Keywords | Field | DocType |
lexicographically shortest path,least-risk path,convex free region,path planning,present algorithm,weighted region problem,terrain navigation problem,exact algorithm,least-risk watchman route,faster algorithm,simple polygon | Discrete mathematics,Polygon,Combinatorics,Shortest path problem,Floyd–Warshall algorithm,Yen's algorithm,Shortest Path Faster Algorithm,Simple polygon,Mathematics,K shortest path routing,Euclidean shortest path | Journal |
Volume | Issue | ISBN |
2 | 3 | 0-89791-270-5 |
Citations | PageRank | References |
16 | 1.48 | 14 |
Authors | ||
4 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| L. Gewali | 1 | 20 | 2.25 |
| Alex C. Meng | 2 | 16 | 1.48 |
| Joseph S. B. Mitchell | 3 | 16 | 1.48 |
| Simeon C. Ntafos | 4 | 599 | 98.18 |