Determining approximate shortest paths on weighted polyhedral surfaces

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...

Full description

Saved in:
Bibliographic Details
Published in:Journal of the ACM 2005, Vol.52 (1), p.25-53
Main Authors: ALEKSANDROV, L, MAHESHWARI, A, SACK, J.-R
Format: Article
Language:English
Subjects:
Algorithmics. Computability. Computer arithmetics
Algorithms
Applied sciences
Approximation
Artificial intelligence
Computation
Computer science
control theory
systems
Design
Discretization
Exact sciences and technology
Geometry
Graphs
Mathematical analysis
Mathematical problems
Pattern recognition. Digital image processing. Computational geometry
Run time (computers)
Shortest-path problems
Studies
Theoretical computing
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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
ISSN:0004-5411
1557-735X
DOI:10.1145/1044731.1044733