{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,3]],"date-time":"2026-07-03T19:30:01Z","timestamp":1783107001552,"version":"3.54.6"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2019,7,12]],"date-time":"2019-07-12T00:00:00Z","timestamp":1562889600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100008952","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-16-CE23-0009"],"award-info":[{"award-number":["ANR-16-CE23-0009"]}],"id":[{"id":"10.13039\/501100008952","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":[[2019,8,31]]},"abstract":"<jats:p>\n            Optimal transport research has surged in the last decade with wide applications in computer graphics. In most cases, however, it has focused on the special case of the so-called \"balanced\" optimal transport problem, that is, the problem of optimally matching positive measures of equal total mass. While this approach is suitable for handling probability distributions as their total mass is always equal to one, it precludes other applications manipulating disparate measures. Our paper proposes a fast approach to the optimal transport of constant distributions supported on point sets of different cardinality via one-dimensional slices. This leads to one-dimensional partial assignment problems akin to alignment problems encountered in genomics or text comparison. Contrary to one-dimensional balanced optimal transport that leads to a trivial linear-time algorithm, such partial optimal transport, even in 1-d, has not seen any closed-form solution nor very efficient algorithms to date. We provide the first efficient 1-d partial optimal transport solver. Along with a quasilinear time problem decomposition algorithm, it solves 1-d assignment problems consisting of up to millions of Dirac distributions within fractions of a second in parallel. We handle higher dimensional problems via a slicing approach, and further extend the popular iterative closest point algorithm using optimal transport - an algorithm we call\n            <jats:italic>Fast Iterative Sliced Transport.<\/jats:italic>\n            We illustrate our method on computer graphics applications such a color transfer and point cloud registration.\n          <\/jats:p>","DOI":"10.1145\/3306346.3323021","type":"journal-article","created":{"date-parts":[[2019,7,12]],"date-time":"2019-07-12T19:04:08Z","timestamp":1562958248000},"page":"1-13","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":43,"title":["SPOT"],"prefix":"10.1145","volume":"38","author":[{"given":"Nicolas","family":"Bonneel","sequence":"first","affiliation":[{"name":"Univ. Lyon, CNRS"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David","family":"Coeurjolly","sequence":"additional","affiliation":[{"name":"Univ. Lyon, CNRS"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2019,7,12]]},"reference":[{"key":"e_1_2_2_2_1","volume-title":"arXiv:1701.07875","author":"Arjovsky Martin","year":"2017"},{"key":"e_1_2_2_3_1","volume-title":"Numerical resolution of an \"unbalanced\" mass transport problem. ESAIM: Mathematical Modelling and Numerical Analysis 37, 5","author":"Benamou Jean-David","year":"2003"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10851-014-0506-3"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2461912.2461939"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2070781.2024192"},{"key":"e_1_2_2_7_1","volume-title":"International conference on mathematics and engineering techniques in medicine and biological sciences. 239--245","author":"Charter Kevin","year":"2000"},{"key":"e_1_2_2_8_1","volume-title":"Scaling Algorithms for Unbalanced Transport Problems. Math. Comp. 87 (07","author":"Chizat Lenaic","year":"2016"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2018.00367"},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICIP.2007.4379798"},{"key":"e_1_2_2_11_1","volume-title":"The optimal partial transport problem. Archive for rational mechanics and analysis 195, 2","author":"Figalli Alessio","year":"2010"},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.3115\/112405.112428"},{"key":"e_1_2_2_13_1","volume-title":"Variational principles for Minkowski type problems, discrete optimal transport, and discrete Monge-Ampere equations. arXiv:1302.5472","author":"Gu Xianfeng","year":"2013"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/360825.360861"},{"key":"e_1_2_2_15_1","volume-title":"Closed-form solution of absolute orientation using orthonormal matrices. JOSA A 5, 7","author":"Horn Berthold KP","year":"1988"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICASSP.2006.1661259"},{"key":"e_1_2_2_17_1","volume-title":"Convergence of a Newton algorithm for semi-discrete optimal transport. arXiv:1603.05579","author":"Kitagawa Jun","year":"2016"},{"key":"e_1_2_2_18_1","volume-title":"Sliced-Wasserstein Autoencoder: An Embarrassingly Simple Generative Model. arXiv:1804.01947","author":"Kolouri Soheil","year":"2018"},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2016.568"},{"key":"e_1_2_2_20_1","volume-title":"Soviet physics doklady","author":"Levenshtein Vladimir I"},{"key":"e_1_2_2_21_1","volume-title":"A Numerical Algorithm for L2 semi-discrete optimal transport in 3D. ESAIM M2AN (Mathematical Modeling and Numerical Analysis)","author":"L\u00e9vy Bruno","year":"2015"},{"key":"e_1_2_2_22_1","volume-title":"Value-Directed Compression of Large-Scale Assignment Problems. In AAAI Conf. on Artificial Intelligence.","author":"Lu Tyler","year":"2015"},{"key":"e_1_2_2_24_1","volume-title":"A Multiscale Approach to Optimal Transport. Computer Graphics Forum","author":"M\u00e9rigot Quentin","year":"2011"},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/3272127.3275091"},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11263-007-0110-8"},{"key":"e_1_2_2_27_1","unstructured":"Gabriel Peyr\u00e9 Marco Cuturi etal 2017. Computational optimal transport. arXiv:1803.00567 (2017).  Gabriel Peyr\u00e9 Marco Cuturi et al. 2017. Computational optimal transport. arXiv:1803.00567 (2017)."},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCV.2005.166"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cviu.2006.11.011"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICIP.2010.5650823"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICIP.2014.7025983"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-24785-9_37"},{"key":"e_1_2_2_33_1","volume-title":"NY","author":"Santambrogio Filippo","year":"2015"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02289451"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/2766963"},{"key":"e_1_2_2_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/62.2160"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/34.88573"},{"key":"e_1_2_2_38_1","doi-asserted-by":"crossref","unstructured":"C\u00e9dric Villani. 2003. Topics in optimal transportation. American Mathematical Soc.  C\u00e9dric Villani. 2003. Topics in optimal transportation. American Mathematical Soc.","DOI":"10.1090\/gsm\/058"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCV.2013.184"},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICIP.2003.1246775"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3306346.3323021","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3306346.3323021","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T00:25:52Z","timestamp":1750206352000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3306346.3323021"}},"subtitle":["sliced partial optimal transport"],"short-title":[],"issued":{"date-parts":[[2019,7,12]]},"references-count":38,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2019,8,31]]}},"alternative-id":["10.1145\/3306346.3323021"],"URL":"https:\/\/doi.org\/10.1145\/3306346.3323021","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019,7,12]]},"assertion":[{"value":"2019-07-12","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}