{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,4]],"date-time":"2025-11-04T16:09:14Z","timestamp":1762272554702,"version":"3.41.0"},"reference-count":43,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2020,3,18]],"date-time":"2020-03-18T00:00:00Z","timestamp":1584489600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Singapore MOE","award":["MOE2013-T2-2-011 and RG26\/17"],"award-info":[{"award-number":["MOE2013-T2-2-011 and RG26\/17"]}]},{"name":"NTU URECA Programme"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2020,4,30]]},"abstract":"<jats:p>\n            This paper develops a new method for constructing Discrete Geodesic Graph (DGG)\u2014an undirected, sparse graph for computing discrete geodesic distances and paths on triangle meshes. Based on a novel accuracy aware window propagation scheme, our method is able to compute the graph edges in a direct and efficient manner. Given a triangle mesh with\n            <jats:italic>n<\/jats:italic>\n            vertices and a user-specified accuracy parameter \u025b, our method produces a DGG with\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            \\\u221a\u025b) edges in empirical\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            \\\u025b\n            <jats:sup>0.75<\/jats:sup>\n            log 1\\\u025b) time, which greatly improves the time complexity\n            <jats:italic>O<\/jats:italic>\n            (\n            <jats:italic>n<\/jats:italic>\n            \\\u025b log 1\\\u025b) of the existing method. Extensive evaluation on a large-scale 3D shape repository shows that our method is efficient and can produce high-quality geodesic distances with predictable accuracy and guaranteed true distance metric. In particular, our method has a great advantage over the existing approximate methods on meshes with high degree of anisotropy. The source code is available at https:\/\/github.com\/GeodesicGraph.\n          <\/jats:p>","DOI":"10.1145\/3144567","type":"journal-article","created":{"date-parts":[[2020,3,18]],"date-time":"2020-03-18T12:25:06Z","timestamp":1584534306000},"page":"1-14","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":19,"title":["Fast Construction of Discrete Geodesic Graphs"],"prefix":"10.1145","volume":"39","author":[{"given":"Yohanes Yudhi","family":"Adikusuma","sequence":"first","affiliation":[{"name":"Nanyang Technological University, Singapore"}]},{"given":"Zheng","family":"Fang","sequence":"additional","affiliation":[{"name":"Nanyang Technological University, Singapore"}]},{"given":"Ying","family":"He","sequence":"additional","affiliation":[{"name":"Nanyang Technological University, Singapore"}]}],"member":"320","published-online":{"date-parts":[[2020,3,18]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.5555\/645899.672441"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.12611"},{"key":"e_1_2_2_3_1","volume-title":"Network Optimization: Continuous and Discrete Models","author":"Bertsekas Dimitri P.","year":"1998","unstructured":"Dimitri P. Bertsekas . 1998 . Network Optimization: Continuous and Discrete Models , Athena Scientific . Dimitri P. Bertsekas. 1998. Network Optimization: Continuous and Discrete Models, Athena Scientific."},{"key":"e_1_2_2_4_1","volume-title":"Proceedings of the Vision, Modeling, and Visualization Conference","author":"Bommes David","year":"2007","unstructured":"David Bommes and Leif Kobbelt . 2007 . Accurate computation of geodesic distance fields for polygonal curves on triangle meshes . In Proceedings of the Vision, Modeling, and Visualization Conference 2007. 151--160. David Bommes and Leif Kobbelt. 2007. Accurate computation of geodesic distance fields for polygonal curves on triangle meshes. In Proceedings of the Vision, Modeling, and Visualization Conference 2007. 151--160."},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comgeo.2011.05.006"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.12173"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2011.01896.x"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/98524.98601"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2516971.2516977"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897824.2925880"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01386390"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.95.15.8431"},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2816795.2818076"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2980179.2982424"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2012.11.005"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2816795.2818076"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00371-007-0136-5"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2012.03187.x"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/511920.511936"},{"volume-title":"Handbook of Discrete and Computational Geometry","author":"Mitchell Joseph S. B.","key":"e_1_2_2_20_1","unstructured":"Joseph S. B. Mitchell . 2004. Shortest paths and networks . In Handbook of Discrete and Computational Geometry , Second Edition. 607--641. Joseph S. B. Mitchell. 2004. Shortest paths and networks. In Handbook of Discrete and Computational Geometry, Second Edition. 607--641."},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/0216045"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.amc.2015.06.103"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1561\/0600000029"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897824.2925930"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.93.4.1591"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.090060097"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2017.386"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.4171\/IFB\/102"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073204.1073228"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/9.412624"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cagd.2017.03.010"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1409625.1409626"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2011.08.027"},{"key":"e_1_2_2_34_1","unstructured":"Shi-Qing Xin Dao T. P. Quynh Xiang Ying and Ying He. 2012a. A global algorithm to compute defect-tolerant geodesic distance. In SIGGRAPH Asia 2012 Technical Briefs. 23:1--23:4.  Shi-Qing Xin Dao T. P. Quynh Xiang Ying and Ying He. 2012a. A global algorithm to compute defect-tolerant geodesic distance. In SIGGRAPH Asia 2012 Technical Briefs. 23:1--23:4."},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559755.1559761"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2010.05.009"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2159616.2159622"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.12484"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2015.2407404"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/2366145.2366200"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2508363.2508379"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2534161"},{"key":"e_1_2_2_43_1","volume-title":"Thingi10K: A dataset of 10,000 3D-printing models. arXiv:1605.04797","author":"Zhou Qingnan","year":"2016","unstructured":"Qingnan Zhou and Alec Jacobson . 2016. Thingi10K: A dataset of 10,000 3D-printing models. arXiv:1605.04797 ( 2016 ). Qingnan Zhou and Alec Jacobson. 2016. Thingi10K: A dataset of 10,000 3D-printing models. arXiv:1605.04797 (2016)."}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3144567","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3144567","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T02:11:22Z","timestamp":1750212682000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3144567"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,3,18]]},"references-count":43,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2020,4,30]]}},"alternative-id":["10.1145\/3144567"],"URL":"https:\/\/doi.org\/10.1145\/3144567","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"type":"print","value":"0730-0301"},{"type":"electronic","value":"1557-7368"}],"subject":[],"published":{"date-parts":[[2020,3,18]]},"assertion":[{"value":"2017-07-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-01-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-03-18","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}