article

Determining approximate shortest paths on weighted polyhedral surfaces

Authors:

L. Aleksandrov,

J.-R. SackAuthors Info & Claims

Journal of the ACM (JACM), Volume 52, Issue 1

Pages 25 - 53

https://doi.org/10.1145/1044731.1044733

Published: 01 January 2005 Publication History

Abstract

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 <ε < 1, the cost of the computed paths is at most 1 + ε times the cost of corresponding shortest paths. Our algorithm is based on a novel way of discretizing polyhedral surfaces and utilizes a generic greedy approach for computing shortest paths in geometric graphs obtained by such discretization. Its running time is O(C(P)n/√ε log n/ε log 1/ε) time, where C(P) captures geometric parameters and the weights of the faces of P.

References

[1]

Agarwal, P., Har-Peled, S., and Karia, M. 2002. Computing approximate shortest paths on convex polytopes. Algorithmica 33, 227--242.]]

Digital Library

[2]

Agarwal, P., Har-Peled, S., Sharir, M., and Varadarajan, K. 1997. Approximating shortest paths on a convex polytope in three dimensions. J. ACM 44, 567--584.]]

Digital Library

[3]

Aleksandrov, L., Lanthier, M., Maheshwari, A., and Sack, J.-R. 1998. An ϵ-approximation algorithm for weighted shortest paths on polyhedral surfaces. In Proceedings of SWAT. Lecture Notes in Computer Science, vol. 1432, Springer-Verlag, Berlin, Germany, 11--22.]]

Digital Library

[4]

Aleksandrov, L., Maheshwari, A., and Sack, J.-R. 2000. Approximation algorithms for geometric shortest path problems. In Proceedings of 32nd ACM Symposium on Theory of Computing. ACM, New York, 286--295.]]

Digital Library

[5]

Aleksandrov, L., Maheshwari, A., and Sack, J.-R. 2003. An improved approximation algorithm for computing geometric shortest paths. In Proceedings of Foundations of Computation Theory. Lecture Notes in Computer Science, vol. 2751, Springer-Verlag, Berlin, Germany, 246--257.]]

[6]

Aleksandrov, L., Maheshwari, A., and Sack, J.-R. 2004. Determining approximate shortest paths in polyhedral domains. In manuscript. Carleton University, Ottawa, Canada.]]

[7]

Bajaj, C. 1998. The algebraic degree of geometric optimization problems. Disc. Computat. Geom. 3, 177--191.]]

Digital Library

[8]

Canny, J., and Reif, J. H. 1987. New lower bound techniques for robot motion planning problems. In Proceedings of 28th IEEE Foundation of Computer Science. (Washington, D.C.) IEEE Computer Society Press, Los Alamitos, Calif., 49--60.]]

[9]

Chazelle, B., Liu, D., and Magen, A. 2003. Sublinear geometric algorithms. In Proceedings of 35nd ACM Symposium on Theory of Computing. ACM, New York.]]

Digital Library

[10]

Chen, J., and Han, Y. 1996. Shortest paths on a polyhedron. Int. J. Computat. Geom. Appl. 6, 127--144.]]

[11]

Har-Peled, S. 1999a. Approximate shortest paths and geodesic diameters on convex polytopes in three dimensions. Disc. Computat. Geom. 21, 217--231.]]

[12]

Har-Peled, S. 1999b. Constructing approximate shortest paths maps in three dimensions. SIAM J. Comput. 28, 1182--1197.]]

Digital Library

[13]

Hershberger, J., and Suri, S. 1995. Practical methods for approximating shortest paths on a convex polytope. In Proceedings of 6th ACM-SIAM Symposium on Discrete Algorithms. ACM, New York, 447--456.]]

Digital Library

[14]

Johansson, P. 1997. On a weighted distance model for injection molding. Ph.D. dissertation. Linköping Studies in Science and Technology, Linköping University, Linköping, Sweden.]]

[15]

Kanai, T., and Suzuki, H. 2001. Approximate shortest path on polyhedral surface and its applications. Comput. Aid. Des. 33, 11, 801--811.]]

[16]

Kapoor, S. 1999. Efficient computation of geodesic shortest paths. In Proceedings of 31st ACM Symposium on Theory of Computing. ACM, New York, 770--779.]]

Digital Library

[17]

Kindl, M., Shing, M., and Rowe, N. 1991. A stochastic approach to the weighted-region problem: Design and testing of a path annealing algorithm. In Technical Report, Computer Science. Naval Postgraduate School, Monterey, Calif.]]

[18]

Lanthier, M., Maheshwari, A., and Sack, J.-R. 2001. Approximating weighted shortest paths on polyhedral surfaces. Algorithmica 30, 4, 527--562.]]

[19]

Lee, A., Dobkin, D., Sweldens, W., and Schroder, P. 1999. Multiresolution mesh morphing. In Computer Graphics Proceedings (SIGGRAPH 99). ACM, New York, 343--350.]]

Digital Library

[20]

Lyusternik, L. 1964. Shortest Paths: Variational Problems (Translated and adapted from Kratchaischie linii). Mir Publishers, Moscow.]]

[21]

Minoi, J.-L. 2001. Navigation and orientation with mobile telephone. Ph.D. dissertation. Department of Computation, UMIST, UK.]]

[22]

Mitchell, J., Mount, D., and Papadimitriou, C. 1987. The discrete geodesic problem. SIAM J. Comput. 16, 647--668.]]

Digital Library

[23]

Mitchell, J., and Papadimitriou, C. 1991. The weighted region problem: Finding shortest paths through a weighted planar subdivision. J. ACM 38, 18--73.]]

Digital Library

[24]

Mourgues, F., Devernay, F., Malandain, G., and Coste-Maniere, E. 2001. 3d+t modeling of coronary artery tree from standard non simultaneous angiographic sequences. In Proceedings of the 4th International Conference on on Medical Image Computing and Computer-Assisted Intervention. Lecture Notes in Computer Science, vol. 2208, Springer-Verlag, Berlin, Germany, 1320--1322.]]

Digital Library

[25]

Papadimitriou, C. 1985. An algorithm for shortest path motion in three dimensions. Inf. Proc. Lett. 20, 259--263.]]

[26]

Polthier, K., and Schmies, M. 1998. Straightest geodesics on polyhedral surfaces. In Math. Visual. Springer, Verlag, Berlin, Germany, 391.]]

[27]

Reif, J., and Sun, Z. 2000. An efficient approximation algorithm for weighted region shortest path problem. In Proceedings of the 4th Workshop on Algorithmic Foundations of Robotics (WAFR2000). A. K. Peters Lt, Hanover, N.H., 191--203.]]

[28]

Reif, J., and Sun, Z. 2001. Bushwack: An approximation algorithm for minimal paths through pseudo-Euclidean spaces. In Proceedings of 12th ISAAC. Lecture Notes in Computer Science, vol. 2223. Springer-Verlag, Berlin, Germany, 160--171.]]

Digital Library

[29]

Reif, J., and Sun, Z. 2003. Adaptive and compact discretization for weighted region optimal path finding. In Proceedings of Foundations of Computation Theory. Lecture Notes in Computer Science, vol. 2751. Springer-Verlag, Berlin, Germany, 258--270.]]

[30]

Sharir, M., and Schorr, A. 1986. On shortest paths in polyhedral spaces. SIAM J. Comput. 15, 193--215.]]

Digital Library

[31]

Varadarajan, K., and Agarwal, P. 2000. Approximating shortest paths on nonconvex polyhedron. SIAM J. Comput. 30, 4, 1321--1340.]]

Digital Library

[32]

Warntz, W. 1957. Transportation, social physics, and the law of refraction. Prof. Geog. 9, 4, 2--7.]]

[33]

Ziegelmann, M. 2001. Constrained shortest paths and related problems. Ph.D. dissertation. Max-Planck Institut fur Informatik (submitted at Universität des Saarlandes), Saarbrücken, Germany.]]

Cited By

Meng WYu HGeng YBo P(2025)An Efficient Algorithm for Approximate Polyline-Sourced Offset Computation on Triangulated SurfacesTsinghua Science and Technology10.26599/TST.2024.901023930:4(1744-1761)Online publication date: Aug-2025
https://doi.org/10.26599/TST.2024.9010239
Wei VWong RLong CMount DSamet H(2024)On Efficient Shortest Path Computation on Terrain Surface: A Direction-Oriented ApproachIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2024.336314736:8(4129-4143)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1109/TKDE.2024.3363147
Bose PEsteban GMaheshwari A(2024)A Steiner-point-based algorithm for approximate shortest paths in weighted equilateral-triangle meshesTheoretical Computer Science10.1016/j.tcs.2024.1145831001:COnline publication date: 27-Jun-2024
https://dl.acm.org/doi/10.1016/j.tcs.2024.114583
Show More Cited By

Index Terms

Determining approximate shortest paths on weighted polyhedral surfaces
1. Theory of computation
  1. Randomness, geometry and discrete structures
    1. Computational geometry

Recommendations

An Approximation Algorithm for Computing Shortest Paths in Weighted 3-d Domains

We present an approximation algorithm for computing shortest paths in weighted three-dimensional domains. Given a polyhedral domain $$\mathcal D $$D, consisting of $$n$$n tetrahedra with positive weights, and a real number $$\varepsilon \in (0,1)$$źź(0,...
On finding approximate optimal paths in weighted regions

The main result of this paper is an approximation algorithm for the weighted region optimal path problem. In this problem, a point robot moves in a planar space composed of n triangular regions, each of which is associated with a positive unit weight. ...
Approximating Shortest Paths on Weighted Polyhedral Surfaces
Abstract.
One common problem in computational geometry is that of computing shortest paths between two points in a constrained domain. In the context of Geographical Information Systems (GIS), terrains are often modeled as Triangular Irregular Networks (...

Comments

Information & Contributors

Information

Published In

cover image Journal of the ACM

Journal of the ACM Volume 52, Issue 1

January 2005

146 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/1044731

Issue’s Table of Contents

Copyright © 2005 ACM.

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 January 2005

Published in JACM Volume 52, Issue 1

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

83
Total Citations
View Citations
1,862
Total Downloads

Downloads (Last 12 months)44
Downloads (Last 6 weeks)0

Reflects downloads up to 03 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Meng WYu HGeng YBo P(2025)An Efficient Algorithm for Approximate Polyline-Sourced Offset Computation on Triangulated SurfacesTsinghua Science and Technology10.26599/TST.2024.901023930:4(1744-1761)Online publication date: Aug-2025
https://doi.org/10.26599/TST.2024.9010239
Wei VWong RLong CMount DSamet H(2024)On Efficient Shortest Path Computation on Terrain Surface: A Direction-Oriented ApproachIEEE Transactions on Knowledge and Data Engineering10.1109/TKDE.2024.336314736:8(4129-4143)Online publication date: 1-Aug-2024
https://dl.acm.org/doi/10.1109/TKDE.2024.3363147
Bose PEsteban GMaheshwari A(2024)A Steiner-point-based algorithm for approximate shortest paths in weighted equilateral-triangle meshesTheoretical Computer Science10.1016/j.tcs.2024.1145831001:COnline publication date: 27-Jun-2024
https://dl.acm.org/doi/10.1016/j.tcs.2024.114583
Davoodi MSafari A(2024)Path Planning in a Weighted Planar Subdivision Under the Manhattan MetricGraphs and Combinatorics10.1007/s00373-023-02744-740:1Online publication date: 19-Jan-2024
https://dl.acm.org/doi/10.1007/s00373-023-02744-7
Babakano FFahmin AShen BCheema M(2024)Time-Efficient Path Planning Algorithm for Mobile Robots on Uneven TerrainDatabases Theory and Applications10.1007/978-981-96-1242-0_21(279-292)Online publication date: 17-Dec-2024
https://dl.acm.org/doi/10.1007/978-981-96-1242-0_21
Huang BWei VWong RTang B(2023)EAR-Oracle: On Efficient Indexing for Distance Queries between Arbitrary Points on Terrain SurfaceProceedings of the ACM on Management of Data10.1145/35886941:1(1-26)Online publication date: 30-May-2023
https://dl.acm.org/doi/10.1145/3588694
Yuan NWang PMeng WChen SXu JXin SHe YWang W(2023)A Variational Framework for Curve Shortening in Various Geometric DomainsIEEE Transactions on Visualization and Computer Graphics10.1109/TVCG.2021.313502129:4(1951-1963)Online publication date: 1-Apr-2023
https://dl.acm.org/doi/10.1109/TVCG.2021.3135021
Agathos AAzariadis P(2023)Optimal Point-to-Point geodesic path generation on point cloudsComputer-Aided Design10.1016/j.cad.2023.103552162:COnline publication date: 13-Jul-2023
https://dl.acm.org/doi/10.1016/j.cad.2023.103552
Bose PEsteban GOrden DSilveira R(2023)On approximating shortest paths in weighted triangular tessellationsArtificial Intelligence10.1016/j.artint.2023.103898318:COnline publication date: 1-May-2023
https://dl.acm.org/doi/10.1016/j.artint.2023.103898
Meng WBo PZhang XHong JXin STu C(2023)An efficient algorithm for approximate Voronoi diagram construction on triangulated surfacesComputational Visual Media10.1007/s41095-022-0326-09:3(443-459)Online publication date: 5-Mar-2023
https://doi.org/10.1007/s41095-022-0326-0
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Article

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Figures

Tables

Media

View Issue’s Table of Contents