Back to Search
Start Over
Determining Approximate Shortest Paths on Weighted Polyhedral Surfaces.
- Source :
- Journal of the ACM; Jan2005, Vol. 52 Issue 1, p25-53, 29p, 10 Diagrams, 2 Charts
- Publication Year :
- 2005
-
Abstract
- 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) ...) time, where C ( P) captures geometric parameters and the weights of the faces of P. [ABSTRACT FROM AUTHOR]
- Subjects :
- ALGORITHMS
APPROXIMATION theory
POLYHEDRAL functions
GEOMETRY
POLYHEDRA
Subjects
Details
- Language :
- English
- ISSN :
- 00045411
- Volume :
- 52
- Issue :
- 1
- Database :
- Complementary Index
- Journal :
- Journal of the ACM
- Publication Type :
- Academic Journal
- Accession number :
- 16004703
- Full Text :
- https://doi.org/10.1145/1044731.1044733