{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,10]],"date-time":"2026-03-10T01:45:14Z","timestamp":1773107114294,"version":"3.50.1"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2009,8,1]],"date-time":"2009-08-01T00:00:00Z","timestamp":1249084800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["60873111"],"award-info":[{"award-number":["60873111"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100002855","name":"Ministry of Science and Technology of the People's Republic of China","doi-asserted-by":"publisher","award":["2004CB719400"],"award-info":[{"award-number":["2004CB719400"]}],"id":[{"id":"10.13039\/501100002855","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2009,8]]},"abstract":"<jats:p>The computation of geodesic distances or paths between two points on triangulated meshes is a common operation in many computer graphics applications. In this article, we present an exact algorithm for the single-source all-vertices shortest path problem.<\/jats:p>\n          <jats:p>\n            Mitchell et al. [1987] proposed an\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            log\n            <jats:italic>n<\/jats:italic>\n            ) method (MMP), based on Dijkstra's algorithm, where\n            <jats:italic>n<\/jats:italic>\n            is the complexity of the polyhedral surface. Then, Chen and Han [1990] (CH) improved the running time to\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            ). Interestingly Surazhsky et al. [2005] provided experimental evidence demonstrating that the MMP algorithm runs many times faster, in practice, than the CH algorithm.\n          <\/jats:p>\n          <jats:p>\n            The CH algorithm encodes the structure of the set of shortest paths using a set of windows on the edges of the polyhedron. Our experiments showed that in many examples over 99% of the windows created by the CH algorithm are of no use to define a shortest path. So this article proposes to improve the CH algorithm by two separate techniques. One is to filter out useless windows using the current estimates of the distances to the vertices, the other is to maintain a priority queue like that achieved in Dijkstra's algorithm. Our experimental results suggest that the improved CH algorithm, in spite of an\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            <jats:sup>2<\/jats:sup>\n            log\n            <jats:italic>n<\/jats:italic>\n            ) asymptotic time complexity, greatly outperforms the original CH algorithm in both time and space. Furthermore, it generally runs faster than the MMP algorithm and uses considerably less space.\n          <\/jats:p>","DOI":"10.1145\/1559755.1559761","type":"journal-article","created":{"date-parts":[[2009,9,8]],"date-time":"2009-09-08T12:53:03Z","timestamp":1252414383000},"page":"1-8","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":125,"title":["Improving Chen and Han's algorithm on the discrete geodesic problem"],"prefix":"10.1145","volume":"28","author":[{"given":"Shi-Qing","family":"Xin","sequence":"first","affiliation":[{"name":"Zhejiang University, Hangzhou, PR China"}]},{"given":"Guo-Jin","family":"Wang","sequence":"additional","affiliation":[{"name":"Zhejiang University, Hangzhou, PR China"}]}],"member":"320","published-online":{"date-parts":[[2009,9,8]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793253371"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/336154.336213"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/263867.263869"},{"key":"e_1_2_1_4_1","volume-title":"Proceedings of Foundations of Computation Theory (FCT). 246--257","author":"Aleksandrov L."},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/98524.98601"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009417"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797325223"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the 6th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). Society for Industrial and Applied Mathematics","author":"Hershberger J."},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the Geometric Modeling and Processing (GMP). IEEE Computer Society","author":"Kanai T."},{"key":"e_1_2_1_11_1","volume-title":"Proceedings of the 12th Canadian Conference on Computational Geometry (CCCG).","author":"Kaneva B.","year":"2000"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/301250.301449"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.95.15.8431"},{"key":"e_1_2_1_14_1","first-page":"633","article-title":"Geometric shortest paths and network optimization. In Handbook of Computational Geometry, J.-R. Sack and J. Urrutia, Eds. Elsevier","volume":"15","author":"Mitchell J. S. B.","year":"2000","journal-title":"Chapter"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1137\/0216045"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/997817.997839"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cag.2005.08.003"},{"key":"e_1_2_1_18_1","doi-asserted-by":"crossref","unstructured":"Mount D. M. 1984. On finding shortest paths on convex polyhedra. Tech. rep. 1495. Computer Science Department University of Maryland College Park MD.  Mount D. M. 1984. On finding shortest paths on convex polyhedra. Tech. rep. 1495. Computer Science Department University of Maryland College Park MD.","DOI":"10.21236\/ADA166246"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the 10th International Conference in Central Europe on Computer Graphics, Visualization and Computer Vision (WSCG).","author":"Novotni M."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-7643-7384-9_18"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1016617010088"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1185657.1185664"},{"key":"e_1_2_1_23_1","volume-title":"Proceedings of the Eurographics\/ACM SIGGRAPH Symposium on Geometry Processing (SGP). Eurographics Association, 146--155","author":"Sander P. V."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144598347059"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215014"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073204.1073228"},{"key":"e_1_2_1_27_1","volume-title":"Proceedings of the IEEE Symposium on Foundations of Computer Science. 182--191","author":"Varadarajan K. R."},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2007.08.001"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1057432.1057439"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/2945.998671"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1559755.1559761","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1559755.1559761","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:29:57Z","timestamp":1750253397000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1559755.1559761"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,8]]},"references-count":30,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2009,8]]}},"alternative-id":["10.1145\/1559755.1559761"],"URL":"https:\/\/doi.org\/10.1145\/1559755.1559761","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2009,8]]},"assertion":[{"value":"2006-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-09-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}