{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T17:58:44Z","timestamp":1775325524804,"version":"3.50.1"},"reference-count":58,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2014,7,27]],"date-time":"2014-07-27T00:00:00Z","timestamp":1406419200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000006","name":"Office of Naval Research","doi-asserted-by":"publisher","award":["N00014-13-1-0341"],"award-info":[{"award-number":["N00014-13-1-0341"]}],"id":[{"id":"10.13039\/100000006","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Max Planck Center for Visual Computing and Communications"},{"DOI":"10.13039\/100006785","name":"Google","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100006785","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["1161480"],"award-info":[{"award-number":["1161480"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100005883","name":"Hertz Foundation","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100005883","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":[[2014,7,27]]},"abstract":"<jats:p>We introduce a novel method for computing the earth mover's distance (EMD) between probability distributions on a discrete surface. Rather than using a large linear program with a quadratic number of variables, we apply the theory of optimal transportation and pass to a dual differential formulation with linear scaling. After discretization using finite elements (FEM) and development of an accompanying optimization method, we apply our new EMD to problems in graphics and geometry processing. In particular, we uncover a class of smooth distances on a surface transitioning from a purely spectral distance to the geodesic distance between points; these distances also can be extended to the volume inside and outside the surface. A number of additional applications of our machinery to geometry problems in graphics are presented.<\/jats:p>","DOI":"10.1145\/2601097.2601175","type":"journal-article","created":{"date-parts":[[2014,7,22]],"date-time":"2014-07-22T15:08:20Z","timestamp":1406041700000},"page":"1-12","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":87,"title":["Earth mover's distances on discrete surfaces"],"prefix":"10.1145","volume":"33","author":[{"given":"Justin","family":"Solomon","sequence":"first","affiliation":[{"name":"Stanford University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Raif","family":"Rustamov","sequence":"additional","affiliation":[{"name":"Stanford University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Leonidas","family":"Guibas","sequence":"additional","affiliation":[{"name":"Stanford University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Adrian","family":"Butscher","sequence":"additional","affiliation":[{"name":"Max Planck Institute for Informatics"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2014,7,27]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/100805741"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/38.536276"},{"key":"e_1_2_2_3_1","doi-asserted-by":"crossref","unstructured":"Beckmann M. 1952. A continuous model of transportation. Econometrica 643--660.  Beckmann M. 1952. A continuous model of transportation. Econometrica 643--660.","DOI":"10.2307\/1907646"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s002110050002"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2070781.2024192"},{"key":"e_1_2_2_6_1","doi-asserted-by":"crossref","unstructured":"Bonneel N. Rabin J. Peyr\u00e9 G. and Pfister H. 2013. Sliced and Radon Wasserstein barycenters of measures. Tech. rep. Preprint Hal-00881872.  Bonneel N. Rabin J. Peyr\u00e9 G. and Pfister H. 2013. Sliced and Radon Wasserstein barycenters of measures. Tech. rep. Preprint Hal-00881872.","DOI":"10.1007\/s10851-014-0506-3"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1561\/2200000016"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.12173"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1987.42"},{"key":"e_1_2_2_10_1","volume-title":"Tech. Rep. 6930, INRIA, June.","author":"Chazal F.","year":"2010","unstructured":"Chazal , F. , Cohen-Steiner , D. , and M\u00e9rigot , Q . 2010 . Geometric inference for measures based on distance functions. Tech. Rep. 6930, INRIA, June. Chazal, F., Cohen-Steiner, D., and M\u00e9rigot, Q. 2010. Geometric inference for measures based on distance functions. Tech. Rep. 6930, INRIA, June."},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-011-9098-0"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.0500334102"},{"key":"e_1_2_2_13_1","volume-title":"Proc. Conf. on Robotics and Automation","volume":"3","author":"Connolly C.","unstructured":"Connolly , C. , Burns , J. B. , and Weiss , R . 1990. Path planning using Laplace's equation . In Proc. Conf. on Robotics and Automation , vol. 3 , 2102--2106. Connolly, C., Burns, J. B., and Weiss, R. 1990. Path planning using Laplace's equation. In Proc. Conf. on Robotics and Automation, vol. 3, 2102--2106."},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2516971.2516977"},{"key":"e_1_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2014.01.004"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2366145.2366190"},{"key":"e_1_2_2_17_1","unstructured":"Deza M. M. and Laurent M. 2009. Geometry of Cuts and Metrics. Springer.   Deza M. M. and Laurent M. 2009. Geometry of Cuts and Metrics . Springer."},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2009.64"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-01-02930-0"},{"key":"e_1_2_2_20_1","volume-title":"Real analysis: modern techniques and their applications","author":"Folland G. B.","unstructured":"Folland , G. B. 1999. Real analysis: modern techniques and their applications , vol. 361 . Wiley New York . Folland, G. B. 1999. Real analysis: modern techniques and their applications, vol. 361. Wiley New York."},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2007.46"},{"key":"e_1_2_2_22_1","volume-title":"-T","author":"Gu X.","year":"2013","unstructured":"Gu , X. , Luo , F. , Sun , J. , and Yau , S . -T ., 2013 . Variational principles for Minkowski type problems, discrete optimal transport, and discrete Monge-Amp\u00e8re equations. Gu, X., Luo, F., Sun, J., and Yau, S.-T., 2013. Variational principles for Minkowski type problems, discrete optimal transport, and discrete Monge-Amp\u00e8re equations."},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1004603514434"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-010-0419-x"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073204.1073229"},{"key":"e_1_2_2_26_1","doi-asserted-by":"crossref","unstructured":"Kimmel R. and Sethian J. A. 1998. Computing geodesic paths on manifolds. In PNAS 8431--8435.  Kimmel R. and Sethian J. A. 1998. Computing geodesic paths on manifolds. In PNAS 8431--8435.","DOI":"10.1073\/pnas.95.15.8431"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.3934\/ipi.2013.7.737"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1018333422414"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.media.2010.01.005"},{"key":"e_1_2_2_30_1","first-page":"A1461","article-title":"Solving partial differential equations on point clouds","volume":"35","author":"Liang J.","year":"2013","unstructured":"Liang , J. , and Zhao , H. 2013 . Solving partial differential equations on point clouds . J. Sci. Comp. 35 , 3, A1461 -- A1486 . Liang, J., and Zhao, H. 2013. Solving partial differential equations on point clouds. J. Sci. Comp. 35, 3, A1461--A1486.","journal-title":"J. Sci. Comp."},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2011.01.020"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/1805964.1805971"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-2012-02569-5"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-011-9093-5"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2011.02032.x"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1137\/0216045"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2010324.1964998"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10957-008-9364-8"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/2461912.2461935"},{"key":"e_1_2_2_40_1","volume-title":"Proc. ICCV, 460--467","author":"Pele O.","unstructured":"Pele , O. , and Werman , M . 2009. Fast and robust earth mover's distances . In Proc. ICCV, 460--467 . Pele, O., and Werman, M. 2009. Fast and robust earth mover's distances. In Proc. ICCV, 460--467."},{"key":"e_1_2_2_41_1","series-title":"Operations Research & Management Science","volume-title":"Found. of Location Anal.","author":"Plastria F.","unstructured":"Plastria , F. 2011. The Weiszfeld algorithm: Proof, amendments, and extensions . In Found. of Location Anal. , H. A. Eiselt and V. Marianov, Eds., vol. 155 of Operations Research & Management Science . 357--389. Plastria, F. 2011. The Weiszfeld algorithm: Proof, amendments, and extensions. In Found. of Location Anal., H. A. Eiselt and V. Marianov, Eds., vol. 155 of Operations Research & Management Science. 357--389."},{"key":"e_1_2_2_42_1","doi-asserted-by":"crossref","unstructured":"Polthier K. and Preuss E. 2003. Identifying vector field singularities using a discrete Hodge decomposition. In Vis. and Math. III H.-C. Hege and K. Polthier Eds. Springer 113--134.  Polthier K. and Preuss E. 2003. Identifying vector field singularities using a discrete Hodge decomposition. In Vis. and Math. III H.-C. Hege and K. Polthier Eds. Springer 113--134.","DOI":"10.1007\/978-3-662-05105-4_6"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0377-0427(01)00357-0"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1026543900054"},{"key":"e_1_2_2_45_1","volume-title":"Proc. SGP, 1279--1288","author":"Rustamov R. M.","unstructured":"Rustamov , R. M. , Lipman , Y. , and Funkhouser , T . 2009. Interior distance using barycentric coordinates . In Proc. SGP, 1279--1288 . Rustamov, R. M., Lipman, Y., and Funkhouser, T. 2009. Interior distance using barycentric coordinates. In Proc. SGP, 1279--1288."},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00526-009-0231-8"},{"key":"e_1_2_2_47_1","volume-title":"October","author":"Santambrogio F.","year":"2013","unstructured":"Santambrogio , F. 2013. Prescribed-divergence problems in optimal transportation. MSRI lecture notes , October 2013 . Santambrogio, F. 2013. Prescribed-divergence problems in optimal transportation. MSRI lecture notes, October 2013."},{"key":"e_1_2_2_48_1","unstructured":"Sayas F.-J. 2008. A gentle introduction to the finite element method.  Sayas F.-J. 2008. A gentle introduction to the finite element method."},{"key":"e_1_2_2_49_1","volume-title":"Hodge decomposition: a method for solving boundary value problems. Lecture notes in mathematics","author":"Schwarz G.","unstructured":"Schwarz , G. 1995. Hodge decomposition: a method for solving boundary value problems. Lecture notes in mathematics . Springer . Schwarz, G. 1995. Hodge decomposition: a method for solving boundary value problems. Lecture notes in mathematics. Springer."},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2012.03167.x"},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.12186"},{"key":"e_1_2_2_52_1","first-page":"1535","article-title":"Fuzzy geodesics and consistent sparse correspondences for deformable shapes","volume":"29","author":"Sun J.","year":"2010","unstructured":"Sun , J. , Chen , X. , and Funkhouser , T. A. 2010 . Fuzzy geodesics and consistent sparse correspondences for deformable shapes . Proc. SGP 29 , 5, 1535 -- 1544 . Sun, J., Chen, X., and Funkhouser, T. A. 2010. Fuzzy geodesics and consistent sparse correspondences for deformable shapes. Proc. SGP 29, 5, 1535--1544.","journal-title":"Proc. SGP"},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/1073204.1073228"},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0217595910002545"},{"key":"e_1_2_2_55_1","volume-title":"Proc. SGP, 201--210","author":"Tong Y.","unstructured":"Tong , Y. , Alliez , P. , Cohen-Steiner , D. , and Desbrun , M . 2006. Designing quadrangulations with discrete harmonic forms . In Proc. SGP, 201--210 . Tong, Y., Alliez, P., Cohen-Steiner, D., and Desbrun, M. 2006. Designing quadrangulations with discrete harmonic forms. In Proc. SGP, 201--210."},{"key":"e_1_2_2_56_1","doi-asserted-by":"crossref","unstructured":"Villani C. 2003. Topics in Optimal Transportation. AMS.  Villani C. 2003. Topics in Optimal Transportation . AMS.","DOI":"10.1090\/gsm\/058"},{"key":"e_1_2_2_57_1","first-page":"355","article-title":"Sur le point pour lequel la somme des distances de n points donn\u00e9s est minimum","volume":"43","author":"Weiszfeld E.","year":"1937","unstructured":"Weiszfeld , E. 1937 . Sur le point pour lequel la somme des distances de n points donn\u00e9s est minimum . T\u00f4hoku Math. J. 43 , 355 -- 386 . Weiszfeld, E. 1937. Sur le point pour lequel la somme des distances de n points donn\u00e9s est minimum. T\u00f4hoku Math. J. 43, 355--386.","journal-title":"T\u00f4hoku Math. J."},{"key":"e_1_2_2_58_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:JOTA.0000005450.58251.6d"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2601097.2601175","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2601097.2601175","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T07:19:11Z","timestamp":1750231151000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2601097.2601175"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,7,27]]},"references-count":58,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2014,7,27]]}},"alternative-id":["10.1145\/2601097.2601175"],"URL":"https:\/\/doi.org\/10.1145\/2601097.2601175","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2014,7,27]]},"assertion":[{"value":"2014-07-27","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}