Approximating weighted shortest paths on polyhedral surfaces
Several algorithms are presented to compute the shortest cost path between two points, s and t, on a polyhedral surface P. Shortest path problems are among the fundamental problems studied in computational geometry. This problem arises in numerous applications in areas such as robotics, traffic control, search and rescue, water flow analysis, road design, navigation, routing, and geographical information systems. The algorithms are simple, practical, less prone to numerical problems, adaptable to a wide spectrum of weight functions, and use only elementary data structures.
|Conference||Proceedings of the 1997 13th Annual Symposium on Computational Geometry|
Lanthier, M, Maheshwari, A, & Sack, J.-R. (1997). Approximating weighted shortest paths on polyhedral surfaces. In Proceedings of the Annual Symposium on Computational Geometry (pp. 274–283).