{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,19]],"date-time":"2026-03-19T18:48:00Z","timestamp":1773946080596,"version":"3.50.1"},"reference-count":65,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2018,12,4]],"date-time":"2018-12-04T00:00:00Z","timestamp":1543881600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"MIT-IBM Watson AI Laboratory"},{"DOI":"10.13039\/100000183","name":"Army Research Office","doi-asserted-by":"publisher","award":["W911NF-12-R-0011"],"award-info":[{"award-number":["W911NF-12-R-0011"]}],"id":[{"id":"10.13039\/100000183","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Amazon Research Award"},{"name":"Skoltech-MIT Next Generation Program"},{"name":"MIT Research Support Committee"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2018,12,31]]},"abstract":"<jats:p>We propose a technique for interpolating between probability distributions on discrete surfaces, based on the theory of optimal transport. Unlike previous attempts that use linear programming, our method is based on a dynamical formulation of quadratic optimal transport proposed for flat domains by Benamou and Brenier [2000], adapted to discrete surfaces. Our structure-preserving construction yields a Riemannian metric on the (finite-dimensional) space of probability distributions on a discrete surface, which translates the so-called Otto calculus to discrete language. From a practical perspective, our technique provides a smooth interpolation between distributions on discrete surfaces with less diffusion than state-of-the-art algorithms involving entropic regularization. Beyond interpolation, we show how our discrete notion of optimal transport extends to other tasks, such as distribution-valued Dirichlet problems and time integration of gradient flows.<\/jats:p>","DOI":"10.1145\/3272127.3275064","type":"journal-article","created":{"date-parts":[[2018,11,28]],"date-time":"2018-11-28T19:16:10Z","timestamp":1543432570000},"page":"1-16","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":30,"title":["Dynamical optimal transport on discrete surfaces"],"prefix":"10.1145","volume":"37","author":[{"given":"Hugo","family":"Lavenant","sequence":"first","affiliation":[{"name":"Universit\u00e9 Paris-Sud"}]},{"given":"Sebastian","family":"Claici","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology"}]},{"given":"Edward","family":"Chien","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology"}]},{"given":"Justin","family":"Solomon","sequence":"additional","affiliation":[{"name":"Massachusetts Institute of Technology"}]}],"member":"320","published-online":{"date-parts":[[2018,12,4]]},"reference":[{"key":"e_1_2_2_1_1","volume-title":"Gradient Flows: In Metric Spaces and in the Space of Probability Measures","author":"Ambrosio Luigi","year":"2008","unstructured":"Luigi Ambrosio , Nicola Gigli , and Giuseppe Savar\u00e9 . 2008 . Gradient Flows: In Metric Spaces and in the Space of Probability Measures . Springer Science & Business Media . Luigi Ambrosio, Nicola Gigli, and Giuseppe Savar\u00e9. 2008. Gradient Flows: In Metric Spaces and in the Space of Probability Measures. Springer Science & Business Media."},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009187"},{"key":"e_1_2_2_3_1","volume-title":"Computer Graphics Forum","author":"Azencot Omri","unstructured":"Omri Azencot , Orestis Vantzos , and Mirela Ben-Chen . 2016. Advection-based function matching on surfaces . In Computer Graphics Forum , Vol. 35 . Wiley Online Library , 55--64. Omri Azencot, Orestis Vantzos, and Mirela Ben-Chen. 2016. Advection-based function matching on surfaces. In Computer Graphics Forum, Vol. 35. Wiley Online Library, 55--64."},{"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.1007\/s10957-015-0725-9"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1137\/141000439"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1051\/proc\/201654001"},{"key":"e_1_2_2_8_1","volume-title":"Active Particles","author":"Benamou Jean-David","unstructured":"Jean-David Benamou , Guillaume Carlier , and Filippo Santambrogio . 2017. Variational mean field games . In Active Particles , Volume 1 . Springer , 141--171. Jean-David Benamou, Guillaume Carlier, and Filippo Santambrogio. 2017. Variational mean field games. In Active Particles, Volume 1. Springer, 141--171."},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2070781.2024192"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1561\/2200000016"},{"key":"e_1_2_2_11_1","volume-title":"Convex Optimization","author":"Boyd Stephen","unstructured":"Stephen Boyd and Lieven Vandenberghe . 2004. Convex Optimization . Cambridge University Press . Stephen Boyd and Lieven Vandenberghe. 2004. Convex Optimization. Cambridge University Press."},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1002\/cpa.3160440402"},{"key":"e_1_2_2_13_1","volume-title":"The Mathematical Theory of Finite Element Methods","author":"Brenner Susanne","unstructured":"Susanne Brenner and Ridgway Scott . 2007. The Mathematical Theory of Finite Element Methods . Vol. 15 . Springer Science & Business Media . Susanne Brenner and Ridgway Scott. 2007. The Mathematical Theory of Finite Element Methods. Vol. 15. Springer Science & Business Media."},{"key":"e_1_2_2_14_1","volume-title":"Entropy dissipation semi-discretization schemes for Fokker-Planck equations. arXiv:1608.02628","author":"Chow Shui-Nee","year":"2016","unstructured":"Shui-Nee Chow , Luca Dieci , Wuchen Li , and Haomin Zhou . 2016. Entropy dissipation semi-discretization schemes for Fokker-Planck equations. arXiv:1608.02628 ( 2016 ). Shui-Nee Chow, Luca Dieci, Wuchen Li, and Haomin Zhou. 2016. Entropy dissipation semi-discretization schemes for Fokker-Planck equations. arXiv:1608.02628 (2016)."},{"key":"e_1_2_2_15_1","volume-title":"Proceedings of the 35th International Conference on Machine Learning, ICML 2018 (to appear).","author":"Claici Sebastian","year":"2018","unstructured":"Sebastian Claici , Edward Chien , and Justin Solomon . 2018 . Stochastic Wasserstein barycenters . In Proceedings of the 35th International Conference on Machine Learning, ICML 2018 (to appear). Sebastian Claici, Edward Chien, and Justin Solomon. 2018. Stochastic Wasserstein barycenters. In Proceedings of the 35th International Conference on Machine Learning, ICML 2018 (to appear)."},{"key":"e_1_2_2_16_1","volume-title":"NIPS","author":"Cuturi Marco","year":"2013","unstructured":"Marco Cuturi . 2013 . Sinkhorn distances: Lightspeed computation of optimal transport. In Advances in Neural Information Processing Systems , NIPS 2013. 2292--2300. Marco Cuturi. 2013. Sinkhorn distances: Lightspeed computation of optimal transport. In Advances in Neural Information Processing Systems, NIPS 2013. 2292--2300."},{"key":"e_1_2_2_17_1","volume-title":"International Conference on Machine Learning. 685--693","author":"Cuturi Marco","year":"2014","unstructured":"Marco Cuturi and Arnaud Doucet . 2014 . Fast computation of Wasserstein barycenters . In International Conference on Machine Learning. 685--693 . Marco Cuturi and Arnaud Doucet. 2014. Fast computation of Wasserstein barycenters. In International Conference on Machine Learning. 685--693."},{"key":"e_1_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2366145.2366190"},{"key":"e_1_2_2_19_1","volume-title":"Computer Graphics Forum","author":"de Goes Fernando","unstructured":"Fernando de Goes , David Cohen-Steiner , Pierre Alliez , and Mathieu Desbrun . 2011. An optimal transport approach to robust reconstruction and simplification of 2d shapes . In Computer Graphics Forum , Vol. 30 . Wiley Online Library , 1593--1602. Fernando de Goes, David Cohen-Steiner, Pierre Alliez, and Mathieu Desbrun. 2011. An optimal transport approach to robust reconstruction and simplification of 2d shapes. In Computer Graphics Forum, Vol. 30. Wiley Online Library, 1593--1602."},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2897826.2927303"},{"key":"e_1_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2602143"},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/2766901"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10851-013-0414-y"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/321694.321699"},{"key":"e_1_2_2_25_1","volume-title":"Computation of Optimal Transport on Discrete Metric Measure Spaces. arXiv:1707.06859","author":"Erbar Matthias","year":"2017","unstructured":"Matthias Erbar , Martin Rumpf , Bernhard Schmitzer , and Stefan Simon . 2017. Computation of Optimal Transport on Discrete Metric Measure Spaces. arXiv:1707.06859 ( 2017 ). Matthias Erbar, Martin Rumpf, Bernhard Schmitzer, and Stefan Simon. 2017. Computation of Optimal Transport on Discrete Metric Measure Spaces. arXiv:1707.06859 (2017)."},{"key":"e_1_2_2_26_1","volume-title":"A Lagrangian scheme \u00e0 la Brenier for the incompressible Euler equations. Foundations of Computational Mathematics","author":"Gallou\u00ebt Thomas O","year":"2017","unstructured":"Thomas O Gallou\u00ebt and Quentin M\u00e9rigot . 2017. A Lagrangian scheme \u00e0 la Brenier for the incompressible Euler equations. Foundations of Computational Mathematics ( 2017 ), 1--31. Thomas O Gallou\u00ebt and Quentin M\u00e9rigot. 2017. A Lagrangian scheme \u00e0 la Brenier for the incompressible Euler equations. Foundations of Computational Mathematics (2017), 1--31."},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02392620"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/120886315"},{"key":"e_1_2_2_29_1","volume-title":"Scaling limits of discrete optimal transport. arXiv:1809.01092","author":"Gladbach Peter","year":"2018","unstructured":"Peter Gladbach , Eva Kopfer , and Jan Maas . 2018. Scaling limits of discrete optimal transport. arXiv:1809.01092 ( 2018 ). Peter Gladbach, Eva Kopfer, and Jan Maas. 2018. Scaling limits of discrete optimal transport. arXiv:1809.01092 (2018)."},{"key":"e_1_2_2_30_1","volume-title":"Recent Advances in Learning and Control","author":"Grant Michael","unstructured":"Michael Grant and Stephen Boyd . 2008. Graph implementations for nonsmooth convex programs . In Recent Advances in Learning and Control , V. Blondel, S. Boyd, and H. Kimura (Eds.). Springer-Verlag Limited , 95--110. Michael Grant and Stephen Boyd. 2008. Graph implementations for nonsmooth convex programs. In Recent Advances in Learning and Control, V. Blondel, S. Boyd, and H. Kimura (Eds.). Springer-Verlag Limited, 95--110."},{"key":"e_1_2_2_31_1","volume-title":"CVX: Matlab Software for Disciplined Convex Programming, version 2.1","author":"Grant Michael","year":"2014","unstructured":"Michael Grant and Stephen Boyd . 2014 . CVX: Matlab Software for Disciplined Convex Programming, version 2.1 . http:\/\/cvxr.com\/cvx. Michael Grant and Stephen Boyd. 2014. CVX: Matlab Software for Disciplined Convex Programming, version 2.1. http:\/\/cvxr.com\/cvx."},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0036142901386069"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2012.03180.x"},{"key":"e_1_2_2_34_1","unstructured":"Romain Hug Nicolas Papadakis and Emmanuel Maitre. 2015. On the convergence of augmented Lagrangian method for optimal transport between nonnegative densities. (2015).  Romain Hug Nicolas Papadakis and Emmanuel Maitre. 2015. On the convergence of augmented Lagrangian method for optimal transport between nonnegative densities. (2015)."},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0036141096303359"},{"key":"e_1_2_2_36_1","volume-title":"Riemannian geometry and geometric analysis","author":"Jost J\u00fcrgen","unstructured":"J\u00fcrgen Jost . 2008. Riemannian geometry and geometric analysis . Vol. 42005 . Springer . J\u00fcrgen Jost. 2008. Riemannian geometry and geometric analysis. Vol. 42005. Springer."},{"key":"e_1_2_2_37_1","first-page":"199","article-title":"On the translocation of masses","volume":"37","author":"Kantorovich Leonid V","year":"1942","unstructured":"Leonid V Kantorovich . 1942 . On the translocation of masses . In Dokl. Akad. Nauk. USSR (NS) , Vol. 37. 199 -- 201 . Leonid V Kantorovich. 1942. On the translocation of masses. In Dokl. Akad. Nauk. USSR (NS), Vol. 37. 199--201.","journal-title":"Dokl. Akad. Nauk. USSR (NS)"},{"key":"e_1_2_2_38_1","volume-title":"Convergence of a Newton algorithm for semi-discrete optimal transport. arXiv preprint arXiv:1603.05579","author":"Kitagawa Jun","year":"2016","unstructured":"Jun Kitagawa , Quentin M\u00e9rigot , and Boris Thibert . 2016. Convergence of a Newton algorithm for semi-discrete optimal transport. arXiv preprint arXiv:1603.05579 ( 2016 ). Jun Kitagawa, Quentin M\u00e9rigot, and Boris Thibert. 2016. Convergence of a Newton algorithm for semi-discrete optimal transport. arXiv preprint arXiv:1603.05579 (2016)."},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.14.3.205"},{"key":"e_1_2_2_40_1","volume-title":"Harmonic mappings valued in the Wasserstein space. arXiv:1712.07528","author":"Lavenant Hugo","year":"2017","unstructured":"Hugo Lavenant . 2017. Harmonic mappings valued in the Wasserstein space. arXiv:1712.07528 ( 2017 ). Hugo Lavenant. 2017. Harmonic mappings valued in the Wasserstein space. arXiv:1712.07528 (2017)."},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1051\/m2an\/2015055"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10915-017-0529-1"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jfa.2011.06.009"},{"key":"e_1_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1142\/S0218202510004799"},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1006\/aima.1997.1634"},{"key":"e_1_2_2_47_1","volume-title":"Computer Graphics Forum","author":"M\u00e9rigot Quentin","unstructured":"Quentin M\u00e9rigot . 2011. A multiscale approach to optimal transport . In Computer Graphics Forum , Vol. 30 . Wiley Online Library , 1583--1592. Quentin M\u00e9rigot. 2011. A multiscale approach to optimal transport. In Computer Graphics Forum, Vol. 30. Wiley Online Library, 1583--1592."},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1137486"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1137\/15M1017235"},{"key":"e_1_2_2_50_1","unstructured":"MOSEK ApS. 2017. The MOSEK optimization toolbox for MATLAB manual.  MOSEK ApS. 2017. The MOSEK optimization toolbox for MATLAB manual."},{"key":"e_1_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02614365"},{"key":"e_1_2_2_52_1","unstructured":"Felix Otto. 2001. The geometry of dissipative evolution equations: the porous medium equation. (2001).  Felix Otto. 2001. The geometry of dissipative evolution equations: the porous medium equation. (2001)."},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/2461912.2461935"},{"key":"e_1_2_2_54_1","doi-asserted-by":"publisher","DOI":"10.1137\/130920058"},{"key":"e_1_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1080\/10586458.1993.10504266"},{"key":"e_1_2_2_56_1","doi-asserted-by":"crossref","unstructured":"Konrad Polthier and Markus Schmies. 2006. Straightest geodesics on polyhedral surfaces. ACM.  Konrad Polthier and Markus Schmies. 2006. Straightest geodesics on polyhedral surfaces. ACM.","DOI":"10.1145\/1185657.1185664"},{"key":"e_1_2_2_57_1","volume-title":"NY","author":"Santambrogio Filippo","year":"2015","unstructured":"Filippo Santambrogio . 2015. Optimal transport for applied mathematicians. Birk\u00e4user , NY ( 2015 ), 99--102. Filippo Santambrogio. 2015. Optimal transport for applied mathematicians. Birk\u00e4user, NY (2015), 99--102."},{"key":"e_1_2_2_58_1","doi-asserted-by":"crossref","unstructured":"Filippo Santambrogio. 2018. Crowd motion and evolution PDEs under density constraints.  Filippo Santambrogio. 2018. Crowd motion and evolution PDEs under density constraints.","DOI":"10.1051\/proc\/201864137"},{"key":"e_1_2_2_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/2766963"},{"key":"e_1_2_2_60_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.12186"},{"key":"e_1_2_2_61_1","doi-asserted-by":"publisher","DOI":"10.1111\/j.1467-8659.2012.03167.x"},{"key":"e_1_2_2_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/2601097.2601175"},{"key":"e_1_2_2_63_1","volume-title":"Gromov-Hausdorff limit of Wasserstein spaces on point clouds. arXiv:1702.03464","author":"Trillos Nicolas Garcia","year":"2017","unstructured":"Nicolas Garcia Trillos . 2017. Gromov-Hausdorff limit of Wasserstein spaces on point clouds. arXiv:1702.03464 ( 2017 ). Nicolas Garcia Trillos. 2017. Gromov-Hausdorff limit of Wasserstein spaces on point clouds. arXiv:1702.03464 (2017)."},{"key":"e_1_2_2_64_1","volume-title":"The Porous Medium Equation: Mathematical Theory","author":"V\u00e1zquez Juan Luis","unstructured":"Juan Luis V\u00e1zquez . 2007. The Porous Medium Equation: Mathematical Theory . Oxford University Press . Juan Luis V\u00e1zquez. 2007. The Porous Medium Equation: Mathematical Theory. Oxford University Press."},{"key":"e_1_2_2_65_1","doi-asserted-by":"crossref","unstructured":"C\u00e9dric Villani. 2003. Topics in Optimal Transportation. Number 58. American Mathematical Soc.  C\u00e9dric Villani. 2003. Topics in Optimal Transportation. Number 58. American Mathematical Soc.","DOI":"10.1090\/gsm\/058"},{"key":"e_1_2_2_66_1","volume-title":"Optimal Transport: Old and New.","author":"Villani C\u00e9dric","year":"2008","unstructured":"C\u00e9dric Villani . 2008 . Optimal Transport: Old and New. Vol. 338 . Springer Science & Business Media . C\u00e9dric Villani. 2008. Optimal Transport: Old and New. Vol. 338. Springer Science & Business Media."}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3272127.3275064","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3272127.3275064","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3272127.3275064","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:44:04Z","timestamp":1750207444000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3272127.3275064"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,12,4]]},"references-count":65,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2018,12,31]]}},"alternative-id":["10.1145\/3272127.3275064"],"URL":"https:\/\/doi.org\/10.1145\/3272127.3275064","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,12,4]]},"assertion":[{"value":"2018-12-04","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}