{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,10]],"date-time":"2026-07-10T08:07:37Z","timestamp":1783670857136,"version":"3.55.0"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2013,11,1]],"date-time":"2013-11-01T00:00:00Z","timestamp":1383264000000},"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":["ACM Trans. Graph."],"published-print":{"date-parts":[[2013,11]]},"abstract":"<jats:p>\n            This paper presents the Saddle Vertex Graph (SVG), a novel solution to the discrete geodesic problem. The SVG is a sparse undirected graph that encodes complete geodesic distance information: a geodesic path on the mesh is equivalent to a shortest path on the SVG, which can be solved efficiently using the shortest path algorithm (e.g., Dijkstra algorithm). The SVG method solves the discrete geodesic problem from a local perspective. We have observed that the polyhedral surface has some interesting and unique properties, such as the fact that the discrete geodesic exhibits a strong local structure, which is not available on the smooth surfaces. The richer the details and complicated geometry of the mesh, the stronger such local structure will be. Taking advantage of the local nature, the SVG algorithm breaks down the discrete geodesic problem into significantly smaller sub-problems, and elegantly enables information reuse. It does not require any numerical solver, and is numerically stable and insensitive to the mesh resolution and tessellation. Users can intuitively specify a model-independent parameter\n            <jats:italic>K<\/jats:italic>\n            , which effectively balances the SVG complexity and the accuracy of the computed geodesic distance. More importantly, the computed distance is guaranteed to be a metric. The experimental results on real-world models demonstrate significant improvement to the existing approximate geodesic methods in terms of both performance and accuracy.\n          <\/jats:p>","DOI":"10.1145\/2508363.2508379","type":"journal-article","created":{"date-parts":[[2013,11,6]],"date-time":"2013-11-06T14:09:19Z","timestamp":1383746959000},"page":"1-12","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":66,"title":["Saddle vertex graph (SVG)"],"prefix":"10.1145","volume":"32","author":[{"given":"Xiang","family":"Ying","sequence":"first","affiliation":[{"name":"Nanyang Technological University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Xiaoning","family":"Wang","sequence":"additional","affiliation":[{"name":"Nanyang Technological University"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ying","family":"He","sequence":"additional","affiliation":[{"name":"Nanyang Technological University"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2013,11]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2011.01896.x"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/98524.98601"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2516971.2516977"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1462173.1462176"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"e_1_2_2_6_1","volume-title":"Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA '05)","author":"Goldberg A. V.","unstructured":"Goldberg , A. V. , and Harrelson , C . 2005. Computing the shortest path: A search meets graph theory . In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA '05) , 156--165. Goldberg, A. V., and Harrelson, C. 2005. Computing the shortest path: A search meets graph theory. In Proceedings of the ACM-SIAM Symposium on Discrete Algorithms (SODA '05), 156--165."},{"key":"e_1_2_2_7_1","doi-asserted-by":"crossref","unstructured":"Kimmel R. and Sethian J. A. 1998. Computing geodesic paths on manifolds. In Proc. Natl. Acad. Sci. 8431--8435.  Kimmel R. and Sethian J. A. 1998. Computing geodesic paths on manifolds. In Proc. Natl. Acad. Sci. 8431--8435.","DOI":"10.1073\/pnas.95.15.8431"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00371-007-0136-5"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPAMI.2010.221"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/511920.511936"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/S003613990342877X"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/0216045"},{"key":"e_1_2_2_13_1","volume-title":"Proc. WSCG '02","author":"Novotni M.","unstructured":"Novotni , M. , and Klein , R . 2002. Computing geodesic distances on triangular meshes . In Proc. WSCG '02 . Novotni, M., and Klein, R. 2002. Computing geodesic distances on triangular meshes. In Proc. WSCG '02."},{"key":"e_1_2_2_14_1","first-page":"124","article-title":"Bi-directional search","volume":"6","author":"Pohl I.","year":"1971","unstructured":"Pohl , I. 1971 . Bi-directional search . Machine Intelligence 6 , 124 -- 140 . Pohl, I. 1971. Bi-directional search. Machine Intelligence 6, 124--140.","journal-title":"Machine Intelligence"},{"key":"e_1_2_2_15_1","doi-asserted-by":"crossref","unstructured":"Polthier K. and Schmies M. 1998. Mathematical Visualization ch. Straightest Geodesics on Polyhedral Surfaces 391.  Polthier K. and Schmies M. 1998. Mathematical Visualization ch. Straightest Geodesics on Polyhedral Surfaces 391.","DOI":"10.1007\/978-3-662-03567-2_11"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1137856.1137862"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247069.1247081"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.93.4.1591"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/0215014"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073204.1073228"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1409625.1409626"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559755.1559761"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2407746.2407769"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2159616.2159622"},{"key":"e_1_2_2_25_1","unstructured":"Ying X. Xin S.-Q. and He Y. 2013. Parallel Chen-Han (PCH) algorithm for discrete geodesics. arXiv:1305.1293.  Ying X. Xin S.-Q. and He Y. 2013. Parallel Chen-Han (PCH) algorithm for discrete geodesics. arXiv:1305.1293 ."}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2508363.2508379","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2508363.2508379","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:28:38Z","timestamp":1750231718000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2508363.2508379"}},"subtitle":["a novel solution to the discrete geodesic problem"],"short-title":[],"issued":{"date-parts":[[2013,11]]},"references-count":25,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2013,11]]}},"alternative-id":["10.1145\/2508363.2508379"],"URL":"https:\/\/doi.org\/10.1145\/2508363.2508379","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,11]]},"assertion":[{"value":"2013-11-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}