Abstract
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.
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Aleksandrov, L., Lanthier, M., Maheshwari, A., Sack, J.-R.: An ε-approximation algorithm for weighted shortest paths on polyhedral surfaces. In: Arnborg, S. (ed.) SWAT 1998. LNCS, vol. 1432, pp. 11–22. Springer, Heidelberg (1998)
Aleksandrov, L., Maheshwari, A., Sack, J.-R.: Approximation algorithms for geometric shortest path problems. In: Proc. 32nd ACM Sympos. Theory Computing, pp. 286–295 (2000)
Aleksandrov, L., Maheshwari, A., Sack, J.-R.: Determining approximate shortest paths on weighted polyhedral surfaces. Journal of the ACM 52(1), 25–53 (2005)
Arkin, E.M., Mitchell, J.S.B., Piatko, C.D.: Bicriteria shortest path problems in the plane. In: Proc. 3rd Canadian Conf. Computational Geometry, pp. 153–156 (1991)
Chen, D.Z., Daescu, O., Hu, X., Wu, X., Xu, J.: Determining an optimal penetration among weighted regions in two and three dimensions. Journal of Combinatorial Optimization 5(1), 59–79 (2001)
Chen, D.Z., Hu, X., Xu, J.: Optimal beam penetration in two and three dimensions. Journal of Combinatorial Optimization 7(2), 111–136 (2003)
Daescu, O.: Improved optimal weighted links algorithms. In: Proc. ICCS 2nd International Workshop on Computational Geometry and Applications, pp. 65–74 (2002)
Daescu, O., Luo, J.: Proximity problems on line segments spanned by points. In: Proc. 17th Canadian Conf. Computational Geometry, pp. 224–228 (2005)
Daescu, O., Mitchell, J.S.B., Ntafos, S., Palmer, J.D., Yap, C.K.: k-link shortest paths in weighted subdivisions. In: Proc. 9th Workshop on Algorithms and Data Structures, pp. 325–337 (2005)
Krozel, J., Lee, C., Mitchell, J.S.B.: Estimating time of arrival in heavy weather conditions. In: Proc. AIAA Guidance, Navigation, and Control, pp. 1481–1495 (1999)
Lanthier, M., Maheshwari, A., Sack, J.-R.: Approximating weighted shortest paths on polyhedral surfaces. In: Proc. 13th ACM Sympos. Computational Geometry, pp. 274–283 (1997)
Lanthier, M., Maheshwari, A., Sack, J.-R.: Approximating shortest paths on weighted polyhedral surfaces. Algorithmica 30(4), 527–562 (2001)
Mata, C., Mitchell, J.S.B.: A new algorithm for computing shortest paths in weighted planar subdivisions. In: Proc. 13th ACM Sympos. Computational Geometry, pp. 264–273 (1997)
Mitchell, J.S.B.: Geometric shortest paths and network optimization. In: Sack, J.-R., Urrutia, J. (eds.) Handbook of Computational Geometry, Elsevier Science, Amsterdam (2000)
Mitchell, J.S.B.: Shortest paths and networks. In: Goodman, J.E., O’Rourke, J. (eds.) Handbook of Discrete and Computational Geometry, ch. 27, 2nd edn., pp. 607–641. Chapman & Hall/CRC, Boca Raton (2004)
Mitchell, J.S.B., Papadimitriou, C.H.: The weighted region problem: Finding shortest paths through a weighted planar subdivision. Journal of the ACM 38(1), 18–73 (1991)
Mitchell, J.S.B., Piatko, C.D., Arkin, E.M.: Computing a shortest k-link path in a polygon. In: Proc. 33rd IEEE Sympos. Foundations Computer Science, pp. 573–582 (1992)
National Library of Medicine. The visible human project, http://www.nlm.nih.gov/research/visible
Piatko, C.D.: Geometric Bicriteria Optimal Path Problems. Ph.D. thesis, Computer Science, Cornell University (1993)
Shewchuk, J.R.: Triangle: Engineering a 2D Quality Mesh Generator and Delaunay Triangulator. In: Lin, M.C., Manocha, D. (eds.) FCRC-WS 1996 and WACG 1996. LNCS, vol. 1148, pp. 203–222. Springer, Heidelberg (1996)
Sun, Z., Reif, J.H.: Adaptive and compact discretization for weighted region optimal path finding. In: Lingas, A., Nilsson, B.J. (eds.) FCT 2003. LNCS, vol. 2751, pp. 258–270. Springer, Heidelberg (2003)
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 2008 Springer-Verlag Berlin Heidelberg
About this chapter
Cite this chapter
Daescu, O., Mitchell, J.S.B., Ntafos, S., Palmer, J.D., Yap, C.K. (2008). An Experimental Study of Weighted k-Link Shortest Path Algorithms. In: Akella, S., Amato, N.M., Huang, W.H., Mishra, B. (eds) Algorithmic Foundation of Robotics VII. Springer Tracts in Advanced Robotics, vol 47. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-68405-3_12
Download citation
DOI: https://doi.org/10.1007/978-3-540-68405-3_12
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-68404-6
Online ISBN: 978-3-540-68405-3
eBook Packages: EngineeringEngineering (R0)