In this article, we present an approximation algorithm for solving the single source shortest paths problem on weighted polyhedral surfaces. We consider a polyhedral surface P as consisting of n triangular faces, where each face has an associated positive weight. The cost of travel through a face is the Euclidean distance traveled, multiplied by the face's weight. For a given parameter ε, 0 < ε < 1, the cost of the computed paths is at most 1 + ε times the cost of corresponding shortest paths. Our algorithm is based on a novel way of discretizing polyhedral surfaces and utilizes a generic greedy approach for computing shortest paths in geometric graphs obtained by such discretization. Its running time is O(C(P)n/√ε log n/ε log 1/ε) time, where C(P) captures geometric parameters and the weights of the faces of P.

Additional Metadata
Keywords Approximation algorithms, Computational geometry, Design and analysis of algorithms, Polyhedral surfaces, Shortest path problems, Weighted paths
Persistent URL
Journal Journal of the ACM
Aleksandrov, L., Maheshwari, A, & Sack, J.-R. (2005). Determining approximate shortest paths on weighted polyhedral surfaces. Journal of the ACM, 52(1), 25–53. doi:10.1145/1044731.1044733