{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,1]],"date-time":"2026-04-01T21:57:25Z","timestamp":1775080645737,"version":"3.50.1"},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2013,9,1]],"date-time":"2013-09-01T00:00:00Z","timestamp":1377993600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100006785","name":"Google","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100006785","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":[[2013,9]]},"abstract":"<jats:p>\n            We introduce the\n            <jats:italic>heat method<\/jats:italic>\n            for computing the geodesic distance to a specified subset (e.g., point or curve) of a given domain. The heat method is robust, efficient, and simple to implement since it is based on solving a pair of standard linear elliptic problems. The resulting systems can be prefactored once and subsequently solved in near-linear time. In practice, distance is updated an order of magnitude faster than with state-of-the-art methods, while maintaining a comparable level of accuracy. The method requires only standard differential operators and can hence be applied on a wide variety of domains (grids, triangle meshes, point clouds, etc.). We provide numerical evidence that the method converges to the exact distance in the limit of refinement; we also explore smoothed approximations of distance suitable for applications where greater regularity is required.\n          <\/jats:p>","DOI":"10.1145\/2516971.2516977","type":"journal-article","created":{"date-parts":[[2013,10,17]],"date-time":"2013-10-17T12:23:34Z","timestamp":1382012614000},"page":"1-11","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":383,"title":["Geodesics in heat"],"prefix":"10.1145","volume":"32","author":[{"given":"Keenan","family":"Crane","sequence":"first","affiliation":[{"name":"Caltech, Pasadena, CA"}]},{"given":"Clarisse","family":"Weischedel","sequence":"additional","affiliation":[{"name":"University of G\u00f6ttingen, Gottingen, Germany"}]},{"given":"Max","family":"Wardetzky","sequence":"additional","affiliation":[{"name":"University of G\u00f6ttingen, Gottingen, Germany"}]}],"member":"320","published-online":{"date-parts":[[2013,10,8]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2010324.1964997"},{"key":"e_1_2_2_2_1","volume-title":"Proceedings of the ACM\/SIAM Symposium on Discrete Algorithms (SODA'09)","author":"Belkin M.","unstructured":"Belkin , M. , Sun , J. , and Wang , Y . 2009a. Constructing laplace operator from point clouds in Rd . In Proceedings of the ACM\/SIAM Symposium on Discrete Algorithms (SODA'09) . Belkin, M., Sun, J., and Wang, Y. 2009a. Constructing laplace operator from point clouds in Rd. In Proceedings of the ACM\/SIAM Symposium on Discrete Algorithms (SODA'09)."},{"key":"e_1_2_2_3_1","volume-title":"Proceedings of the ACM\/SIAM Symposium on Discrete Algorithms (SODA'09)","author":"Belkin M.","unstructured":"Belkin , M. , Sun , J. , and Wang , Y . 2009b. Discrete laplace operator for meshed surfaces . In Proceedings of the ACM\/SIAM Symposium on Discrete Algorithms (SODA'09) . 1031--1040. Belkin, M., Sun, J., and Wang, Y. 2009b. Discrete laplace operator for meshed surfaces. In Proceedings of the ACM\/SIAM Symposium on Discrete Algorithms (SODA'09). 1031--1040."},{"key":"e_1_2_2_4_1","volume-title":"Proceedings of the Workshop on Vision, Modeling, and Visualization (VMV'07)","author":"Bommes D.","unstructured":"Bommes , D. and Kobbelt , L . 2007. Accurate computation of geodesic distance fields for polygonal curves on triangle meshes . In Proceedings of the Workshop on Vision, Modeling, and Visualization (VMV'07) . 151--160. Bommes, D. and Kobbelt, L. 2007. Accurate computation of geodesic distance fields for polygonal curves on triangle meshes. In Proceedings of the Workshop on Vision, Modeling, and Visualization (VMV'07). 151--160."},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1007\/11537908_5"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2011.01896.x"},{"key":"e_1_2_2_7_1","unstructured":"Chebotarev P. 2011. The walk distances in graphs. ArXiv e-prints.  Chebotarev P. 2011. The walk distances in graphs. ArXiv e-prints."},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1391989.1391995"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.acha.2006.04.006"},{"key":"e_1_2_2_10_1","volume-title":"Discrete Differential Geometry. Oberwolfach Seminars","volume":"38","author":"Desbrun M.","unstructured":"Desbrun , M. , Kanso , E. , and Tong , Y . 2008. Discrete differential forms for computational modeling . In Discrete Differential Geometry. Oberwolfach Seminars , vol. 38 . Birkhauser, 287--324. Desbrun, M., Kanso, E., and Tong, Y. 2008. Discrete differential forms for computational modeling. In Discrete Differential Geometry. Oberwolfach Seminars, vol. 38. Birkhauser, 287--324."},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2007.46"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2011.02025.x"},{"key":"e_1_2_2_13_1","volume-title":"Proceedings of the Algoritmy Conference. 22--31","author":"Hysing S.","unstructured":"Hysing , S. and Turek , S . 2005. The eikonal equation: Numerical efficiency vs. algorithmic complexity . In Proceedings of the Algoritmy Conference. 22--31 . Hysing, S. and Turek, S. 2005. The eikonal equation: Numerical efficiency vs. algorithmic complexity. In Proceedings of the Algoritmy Conference. 22--31."},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/S106482759732455X"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.95.15.8431"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1805964.1805971"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2011.152"},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/1735603.1735635"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.5555\/511920.511936"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/S003613990342877X"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/0216045"},{"key":"e_1_2_2_23_1","unstructured":"Nealen A. 2004. An as-short-as-possible introduction to the mls method for scattered data approximation and interpolation. Tech. rep. http:\/\/www.nealen.net\/projects\/mls\/asapmls.pdf.  Nealen A. 2004. An as-short-as-possible introduction to the mls method for scattered data approximation and interpolation. Tech. rep. http:\/\/www.nealen.net\/projects\/mls\/asapmls.pdf."},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.4310\/SDG.2004.v9.n1.a9"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02392720"},{"key":"e_1_2_2_26_1","doi-asserted-by":"crossref","unstructured":"Peyre G. and Cohen L. D. 2005. Geodesic computations for fast and accurate surface remeshing and parameterization. In Programs in Nonlinear Differential Equations and Their Applications. Vol. 63. Springer 157--171.  Peyre G. and Cohen L. D. 2005. Geodesic computations for fast and accurate surface remeshing and parameterization. In Programs in Nonlinear Differential Equations and Their Applications. Vol. 63. Springer 157--171.","DOI":"10.1007\/3-7643-7384-9_18"},{"key":"e_1_2_2_27_1","unstructured":"Rangarajan A. and Gurumoorthy K. 2011. A fast eikonal equation solver using the schrodinger wave equation. Tech. rep. REP-2011-512 CISE University of Florida.  Rangarajan A. and Gurumoorthy K. 2011. A fast eikonal equation solver using the schrodinger wave equation. Tech. rep. REP-2011-512 CISE University of Florida."},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/1735603.1735607"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcp.2011.10.013"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0095978"},{"key":"e_1_2_2_31_1","volume-title":"Fluid Mechanics, Computer Vision and Materials Science","author":"Sethian J. A.","unstructured":"Sethian , J. A. 1996. Level Set Methods and Fast Marching Methods: Evolving Interfaces in Computational Geometry , Fluid Mechanics, Computer Vision and Materials Science . Cambridge University Press . Sethian, J. A. 1996. Level Set Methods and Fast Marching Methods: Evolving Interfaces in Computational Geometry, Fluid Mechanics, Computer Vision and Materials Science. Cambridge University Press."},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007372"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073204.1073228"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.3160200210"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:POTA.0000025376.45065.80"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1409625.1409626"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2516971.2516977","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2516971.2516977","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:28:40Z","timestamp":1750231720000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2516971.2516977"}},"subtitle":["A new approach to computing distance based on heat flow"],"short-title":[],"issued":{"date-parts":[[2013,9]]},"references-count":35,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2013,9]]}},"alternative-id":["10.1145\/2516971.2516977"],"URL":"https:\/\/doi.org\/10.1145\/2516971.2516977","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,9]]},"assertion":[{"value":"2012-09-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-03-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-10-08","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}