Abstract
This paper presents an approximation algorithm for finding minimum cost path between two points on the surface of a weighted polyhedron in 3D. It terminates in finite time. For a restricted class of polyhedron better approximation bound can be obtained.
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
Agarwal, P.K., Har-Peled, S., Karia, M.: Computing approximate shortest paths on convex polytopes. Algorithmica 33, 227–242 (2002)
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. Symp. on Theory of Comput., pp. 286–295 (2000)
Aleksandrov, L., Maheshwari, A., Sack, J.-R.: An improved approximation algorithms for computing geometric shortest paths problems. In: Proc. Symp. on Foundations of Computing Theory, pp. 246–257 (2003)
Chen, J., Han, Y.: Shortest paths on a polyhedron. Int. J. on Computational Geometry and Applications 6, 127–144 (1996)
Dijkstra, E.W.: A note on two problems in connection with graphs. Numerical Mathematics 1, 267–271 (1959)
Kapoor, S.: Efficient computation of geodesic shortest paths. In: Symp. on Theory of Computing, pp. 770–779 (1999)
Lanthier, M., Maheswari, A., Sack, J.-R.: Approximating weighted shortest paths on polyhedral surfaces. Algorithmica 30, 527–562 (2001)
Mata, C., Mitchell, J.S.B.: A new algorithm for computing shortest paths in weighted planar subdivisions. In: Proc. 13th ACM Symp. Comput. Geom., pp. 264–273 (1997)
Mitchell, J.S.B., Mount, D.M., Papadimitrou, C.H.: Discrete geodesic problem. SIAM J. on Computing 16, 647–668 (1987)
Mitchell, J.S.B., Papadimitrou, C.H.: The weighted region problem: finding shortest paths through a weighted planar subdivision. J. of the Association for Computing Machinary 38, 18–73 (1991)
Papdimitriou, C.H.: An algorithm for shortest path motion in three dimension. Inform. Process. Lett. 20, 259–263 (1985)
Sack, J.R., Urrutia, J.: Handbook of computational geometry. North-Holland, Elsevier Science B. V., Netherlands (2000)
Sharir, M., Schorr, A.: On shortest paths in polyhedral space. SIAM J. Computing 15, 93–215 (1986)
Varadarajan, K.R., Agarwal, P.K.: Approximating shortest path on a non-convex polyhedron. SIAM J. Computing 30, 1321–1340 (2000)
Ziegelmann, M.: Constrained shortest paths and related problems, Ph.D. Thesis, Universitat des Saarlandes (Max-Plank Institut fur Informatik) (2001)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2004 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Roy, S., Das, S., Nandy, S.C. (2004). A Practical Algorithm for Approximating Shortest Weighted Path between a Pair of Points on Polyhedral Surface. In: Laganá, A., Gavrilova, M.L., Kumar, V., Mun, Y., Tan, C.J.K., Gervasi, O. (eds) Computational Science and Its Applications – ICCSA 2004. ICCSA 2004. Lecture Notes in Computer Science, vol 3045. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-24767-8_5
Download citation
DOI: https://doi.org/10.1007/978-3-540-24767-8_5
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-22057-2
Online ISBN: 978-3-540-24767-8
eBook Packages: Springer Book Archive