{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,29]],"date-time":"2026-04-29T02:35:29Z","timestamp":1777430129261,"version":"3.51.4"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2005,1,1]],"date-time":"2005-01-01T00:00:00Z","timestamp":1104537600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2005,1]]},"abstract":"<jats:p>\n            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\n            <jats:italic>P<\/jats:italic>\n            as consisting of\n            <jats:italic>n<\/jats:italic>\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 \u03b5, 0 &lt;\u03b5 &lt; 1, the cost of the computed paths is at most 1 + \u03b5 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\n            <jats:italic>O(C(P)<\/jats:italic>\n            <jats:italic>n<\/jats:italic>\n            \/\u221a\u03b5 log\n            <jats:italic>n<\/jats:italic>\n            \/\u03b5 log 1\/\u03b5) time, where\n            <jats:italic>C(P)<\/jats:italic>\n            captures geometric parameters and the weights of the faces of\n            <jats:italic>P<\/jats:italic>\n            .\n          <\/jats:p>","DOI":"10.1145\/1044731.1044733","type":"journal-article","created":{"date-parts":[[2005,8,3]],"date-time":"2005-08-03T08:30:55Z","timestamp":1123057855000},"page":"25-53","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":74,"title":["Determining approximate shortest paths on weighted polyhedral surfaces"],"prefix":"10.1145","volume":"52","author":[{"given":"L.","family":"Aleksandrov","sequence":"first","affiliation":[{"name":"Bulgarian Academy of Sciences, Sofia, Bulgaria"}]},{"given":"A.","family":"Maheshwari","sequence":"additional","affiliation":[{"name":"Carleton University, Ottawa, Ontario, Canada"}]},{"given":"J.-R.","family":"Sack","sequence":"additional","affiliation":[{"name":"Carleton University, Ottawa, Ontario, Canada"}]}],"member":"320","published-online":{"date-parts":[[2005,1]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0111-x"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/263867.263869"},{"key":"e_1_2_1_3_1","volume-title":"-R","author":"Aleksandrov L.","year":"1998","unstructured":"Aleksandrov , L. , Lanthier , M. , Maheshwari , A. , and Sack , J . -R . 1998 . An &epsiv;-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.]] Aleksandrov, L., Lanthier, M., Maheshwari, A., and Sack, J.-R. 1998. An &epsiv;-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.]]"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335339"},{"key":"e_1_2_1_5_1","volume-title":"-R","author":"Aleksandrov L.","year":"2003","unstructured":"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.]] 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.]]"},{"key":"e_1_2_1_6_1","volume-title":"-R","author":"Aleksandrov L.","year":"2004","unstructured":"Aleksandrov , L. , Maheshwari , A. , and Sack , J . -R . 2004 . Determining approximate shortest paths in polyhedral domains. In manuscript. Carleton University , Ottawa, Canada.]] Aleksandrov, L., Maheshwari, A., and Sack, J.-R. 2004. Determining approximate shortest paths in polyhedral domains. In manuscript. Carleton University, Ottawa, Canada.]]"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02187906"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of 28th IEEE Foundation of Computer Science. (Washington, D.C.) IEEE Computer Society Press, Los Alamitos, Calif., 49--60","author":"Canny J.","unstructured":"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 .]] 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.]]"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780620"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218195996000095"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009417"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797325223"},{"key":"e_1_2_1_13_1","volume-title":"Proceedings of 6th ACM-SIAM Symposium on Discrete Algorithms. ACM","author":"Hershberger J.","unstructured":"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.]] 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.]]"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0010-4485(01)00097-5"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/301250.301449"},{"key":"e_1_2_1_17_1","unstructured":"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.]]  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.]]"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-001-0027-5"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/311535.311586"},{"key":"e_1_2_1_20_1","volume-title":"Shortest Paths: Variational Problems (Translated and adapted from Kratchaischie linii)","author":"Lyusternik L.","year":"1964","unstructured":"Lyusternik , L. 1964 . Shortest Paths: Variational Problems (Translated and adapted from Kratchaischie linii) . Mir Publishers , Moscow .]] Lyusternik, L. 1964. Shortest Paths: Variational Problems (Translated and adapted from Kratchaischie linii). Mir Publishers, Moscow.]]"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/0216045"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/102782.102784"},{"key":"e_1_2_1_24_1","series-title":"Lecture Notes in Computer Science","volume-title":"Proceedings of the 4th International Conference on on Medical Image Computing and Computer-Assisted Intervention","author":"Mourgues F.","unstructured":"Mourgues , F. , Devernay , F. , Malandain , G. , and Coste-Maniere , E. 2001. 3d&plus;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.]] Mourgues, F., Devernay, F., Malandain, G., and Coste-Maniere, E. 2001. 3d&plus;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.]]"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(85)90029-8"},{"key":"e_1_2_1_26_1","doi-asserted-by":"crossref","unstructured":"Polthier K. and Schmies M. 1998. Straightest geodesics on polyhedral surfaces. In Math. Visual. Springer Verlag Berlin Germany 391.]]  Polthier K. and Schmies M. 1998. Straightest geodesics on polyhedral surfaces. In Math. Visual. Springer Verlag Berlin Germany 391.]]","DOI":"10.1007\/978-3-662-03567-2_11"},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the 4th Workshop on Algorithmic Foundations of Robotics (WAFR2000)","author":"Reif J.","unstructured":"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.]] 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.]]"},{"key":"e_1_2_1_28_1","series-title":"Lecture Notes in Computer Science","volume-title":"Bushwack: An approximation algorithm for minimal paths through pseudo-Euclidean spaces. In Proceedings of 12th ISAAC","author":"Reif J.","year":"2001","unstructured":"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.]] 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.]]"},{"key":"e_1_2_1_29_1","volume-title":"Proceedings of Foundations of Computation Theory. Lecture Notes in Computer Science","volume":"2751","author":"Reif J.","unstructured":"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.]] 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.]]"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215014"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799352759"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.0033-0124.1957.094_2.x"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1044731.1044733","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1044731.1044733","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T21:36:47Z","timestamp":1750282607000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1044731.1044733"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,1]]},"references-count":30,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2005,1]]}},"alternative-id":["10.1145\/1044731.1044733"],"URL":"https:\/\/doi.org\/10.1145\/1044731.1044733","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,1]]},"assertion":[{"value":"2005-01-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}