TY - GEN
T1 - An experimental study of weighted k-link shortest path algorithms
AU - Daescu, Ovidiu
AU - Mitchell, Joseph S.B.
AU - Ntafos, Simeon
AU - Palmer, James D.
AU - Yap, Chee K.
PY - 2008
Y1 - 2008
N2 - We consider the problem of computing a minimum-weight polygonal path between two points in a weighted polygonal subdivision, subject to the constraint that the path have few segments (links). We give an algorithm that generates paths of weighted length at most (1 + ε) times the weight of a minimum-cost k-link path, for any fixed ε > 0, while using at most 2k - 1 links. This is an improvement over the previous (1 + ε)-approximation algorithm, which used at most 5k - 2 links. Further, we have implemented our new algorithm and we have conducted a performance study of these algorithms (old and new) on a variety of real-world and synthetic data, comparing not only the efficiency but also the quality of paths generated using these algorithms. We also consider the implications of these results on the practical usage of these algorithms.
AB - We consider the problem of computing a minimum-weight polygonal path between two points in a weighted polygonal subdivision, subject to the constraint that the path have few segments (links). We give an algorithm that generates paths of weighted length at most (1 + ε) times the weight of a minimum-cost k-link path, for any fixed ε > 0, while using at most 2k - 1 links. This is an improvement over the previous (1 + ε)-approximation algorithm, which used at most 5k - 2 links. Further, we have implemented our new algorithm and we have conducted a performance study of these algorithms (old and new) on a variety of real-world and synthetic data, comparing not only the efficiency but also the quality of paths generated using these algorithms. We also consider the implications of these results on the practical usage of these algorithms.
UR - http://www.scopus.com/inward/record.url?scp=53849124364&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=53849124364&partnerID=8YFLogxK
U2 - 10.1007/978-3-540-68405-3_12
DO - 10.1007/978-3-540-68405-3_12
M3 - Conference contribution
AN - SCOPUS:53849124364
SN - 9783540684046
T3 - Springer Tracts in Advanced Robotics
SP - 187
EP - 202
BT - Algorithmic Foundation of Robotics VII - Selected Contributions of the Seventh International Workshop on the Algorithmic Foundations of Robotics
T2 - 7th International Workshop on the Algorithmic Foundations of Robotics, WAFR 2006
Y2 - 16 July 2006 through 18 July 2006
ER -