Abstract
Let P be a simple polyhedron, possibly non-convex, whose boundary is composed of n triangular faces, and in which each face has an associated positive weight. The cost of travel through each face is the distance traveled multiplied by the face's weight. We present an ε-approximation algorithm for computing a weighted shortest path on P, i.e. the ratio of the length of the computed path with respect to the length of an optimal path is bounded by (1 + ε), for a given ε > 0.We give a detailed analysis to determine the exact constants for the approximation factor. The running time of the algorithm is O(mn log mn + nm 2). The total number of Steiner points, m, added to obtain the approximation depends on various parameters of the given polyhedron such as the length of the longest edge, the minimum angle between any two adjacent edges of P and the minimum distance from any vertex to the boundary of the union of its incident faces and the ratio of the largest (finite) to the smallest face weights of P. Lastly, we present an approximation algorithm with an improved running time of O(mn log mn), at the cost of trading off the constants in the path accuracy. Our results present an improvement in the dependency on the number of faces, n, to the recent results of Mata and Mitchell [10] by a multiplicative factor of n 2/log n, and to that of Mitchell and Papadimitriou [11] by a factor of n 7.
Research supported in part by ALMERCO Inc. & NSERC
Preview
Unable to display preview. Download preview PDF.
References
L. Aleksandrov, M. Lanthier, A. Maheshwari and J.-R. Sack, “An ε-Approximation Algorithm for Weighted Shortest Path Queries on Polyhedral Surfaces”, to appear 14th European Workshop on Computational Geometry, Barcelona, Spain, 1998.
J. Choi, J. Sellen and C.K. Yap, “Approximate Euclidean Shortest Path in 3-Space”, Proc. 10th Annual Symp. on Computational Geometry, 1994, pp. 41–48.
G. Das and G. Narasimhan, “Short Cuts in Higher Dimensional Space”, Proceedings of the 7th Annual Canadian Conference on Computational Geometry, Québec City, Québec, 1995, pp. 103–108.
M.L. Fredman and R.E. Tarjan, “Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms”, J. ACM, 34(3), 1987, pp.596–615.
J. Goodman and J. O'Rourke, Eds., Handbook of Discrete and Computational Geometry, CRC Press LLC, Chapter 24, 1997, pp. 445–466.
P. Johansson, “On a Weighted Distance Model for Injection Molding”, Linköping Studies in Science and Technology, Thesis no. 604 LiU-TEK-LIC-1997:05, Division of Applied Mathematics, Linköping University, Linköping, Sweden, 1997.
C. Kenyon and R. Kenyon, “How To Take Short Cuts”, Discrete and Computational Geometry, Vol. 8, No. 3, 1992, pp. 251–264.
M. Lanthier, A. Maheshwari and J.-R. Sack, “Approximating Weighted Shortest Paths on Polyhedral Surfaces”, Proceedings of the 13th Annual ACM Symposium on Computational Geometry, 1997, pp. 274–283.
M. Lanthier, “Shortest Path Problems on Polyhedral Surfaces”, Ph.D. Thesis in progress, School of Computer Science, Carleton University, Ottawa, Canada, 1998.
C. Mata and J. Mitchell, “A New Algorithm for Computing Shortest Paths in Weighted Planar Subdivisions”, Proceedings of the 13th Annual ACM Symposium on Computational Geometry, 1997, pp. 264–273.
J.S.B. Mitchell and C.H. Papadimitriou, “The Weighted Region Problem: Finding Shortest Paths Through a Weighted Planar Subdivision”, Journal of the ACM, 38, January 1991, pp. 18–73.
C.H. Papadimitriou, “An Algorithm for Shortest Path Motion in Three Dimensions”, Information Processing Letters, 20, 1985, pp. 259–263.
J.-R. Sack and J. Urrutia Eds., Handbook on Computational Geometry, Elsevier Science B.V., to appear.
M. Sharir and A. Schorr, “On Shortest Paths in Polyhedral Spaces”, SIAM Journal of Computing, 15, 1986, pp. 193–215.
Paradigm Group Webpage, School of Computer Science, Carleton University, http://www.scs.carleton.ca/~gis.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1998 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Aleksandrov, L., Lanthier, M., Maheshwari, A., Sack, J.R. (1998). An ε — Approximation algorithm for weighted shortest paths on polyhedral surfaces. In: Arnborg, S., Ivansson, L. (eds) Algorithm Theory — SWAT'98. SWAT 1998. Lecture Notes in Computer Science, vol 1432. Springer, Berlin, Heidelberg. https://doi.org/10.1007/BFb0054351
Download citation
DOI: https://doi.org/10.1007/BFb0054351
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-64682-2
Online ISBN: 978-3-540-69106-8
eBook Packages: Springer Book Archive