{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,3]],"date-time":"2026-07-03T19:30:00Z","timestamp":1783107000660,"version":"3.54.6"},"reference-count":44,"publisher":"Association for Computing Machinery (ACM)","issue":"4","funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["ERC AdG 101054420 EYAWKAJKOS"],"award-info":[{"award-number":["ERC AdG 101054420 EYAWKAJKOS"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["ANR-22-CE46-000 (StableProxies)"],"award-info":[{"award-number":["ANR-22-CE46-000 (StableProxies)"]}],"id":[{"id":"10.13039\/501100001665","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":[[2025,8,1]]},"abstract":"<jats:p>Matching probability distributions allows to compare or interpolate them, or model their manifold. Optimal transport is a tool that solves this matching problem. However, despite the development of numerous exact and approximate algorithms, these approaches remain too slow for large datasets due to the inherent challenge of optimizing transport plans. Taking intuitions from recent advances in rectified flows we propose an algorithm that, while not resulting in optimal transport plans, produces transport plans from uniform densities to densities stored on grids that resemble the optimal ones in practice. Our algorithm has linear-time complexity with respect to the problem size and is embarrassingly parallel. It is also trivial to implement, essentially computing three summed-area tables and advecting particles with velocities easily computed from these tables using simple arithmetic. This already allows for applications such as stippling and area-preserving mesh parameterization. Combined with linearized transport ideas, we further extend our approach to match two non-uniform distributions. This allows for wider applications such as shape interpolation or barycenters, matching the quality of more complex optimal or approximate transport solvers while resulting in orders of magnitude speedups. We illustrate our applications in 2D and 3D.<\/jats:p>","DOI":"10.1145\/3731147","type":"journal-article","created":{"date-parts":[[2025,7,27]],"date-time":"2025-07-27T04:02:22Z","timestamp":1753588942000},"page":"1-13","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":3,"title":["Linear-Time Transport with Rectified Flows"],"prefix":"10.1145","volume":"44","author":[{"ORCID":"https:\/\/orcid.org\/0009-0001-9887-7470","authenticated-orcid":false,"given":"Khoa","family":"Do","sequence":"first","affiliation":[{"name":"University of Michigan, Ann Arbor, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3164-8697","authenticated-orcid":false,"given":"David","family":"Coeurjolly","sequence":"additional","affiliation":[{"name":"CNRS, Lyon, France"},{"name":"Universit\u00e9 Claude Bernard Lyon 1, Lyon, France"},{"name":"INSA Lyon 1, Lyon, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8811-6889","authenticated-orcid":false,"given":"Pooran","family":"Memari","sequence":"additional","affiliation":[{"name":"CNRS, Palaiseau, France"},{"name":"LIX, Palaiseau, France"},{"name":"\u00c9cole Polytechnique, Palaiseau, France"},{"name":"INRIA, IP-Paris, Palaiseau, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5243-4810","authenticated-orcid":false,"given":"Nicolas","family":"Bonneel","sequence":"additional","affiliation":[{"name":"CNRS, Lyon, France"},{"name":"Universit\u00e9 Claude Bernard Lyon 1, Lyon, France"},{"name":"INSA Lyon, Lyon, France"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,7,27]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/2980179.2980218"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3550454.3555519"},{"key":"e_1_2_2_3_1","volume-title":"Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration. Advances in neural information processing systems 30","author":"Altschuler Jason","year":"2017","unstructured":"Jason Altschuler, Jonathan Niles-Weed, and Philippe Rigollet. 2017. Near-linear time approximation algorithms for optimal transport via Sinkhorn iteration. Advances in neural information processing systems 30 (2017)."},{"key":"e_1_2_2_4_1","volume-title":"Gradient flows: in metric spaces and in the space of probability measures","author":"Ambrosio Luigi","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."},{"key":"e_1_2_2_5_1","doi-asserted-by":"crossref","unstructured":"Uri M Ascher and Linda R Petzold. 1998. Computer methods for ordinary differential equations and differential-algebraic equations. SIAM.","DOI":"10.1137\/1.9781611971392"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3306346.3323021"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1111\/cgf.14778"},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10851-014-0506-3"},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/2024156.2024192"},{"key":"e_1_2_2_10_1","volume-title":"Sinkhorn distances: Lightspeed computation of optimal transport. Advances in neural information processing systems 26","author":"Cuturi Marco","year":"2013","unstructured":"Marco Cuturi. 2013. Sinkhorn distances: Lightspeed computation of optimal transport. Advances in neural information processing systems 26 (2013)."},{"key":"e_1_2_2_11_1","volume-title":"Blue Noise through Optimal Transport. ACM Trans. Graph. (SIGGRAPH Asia) 31","author":"de Goes Fernando","year":"2012","unstructured":"Fernando de Goes, Katherine Breeden, Victor Ostromoukhov, and Mathieu Desbrun. 2012. Blue Noise through Optimal Transport. ACM Trans. Graph. (SIGGRAPH Asia) 31 (2012). Issue 6."},{"key":"e_1_2_2_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3610548.3618243"},{"key":"e_1_2_2_13_1","volume-title":"Texture mapping via optimal mass transport","author":"Dominitz Ayelet","year":"2009","unstructured":"Ayelet Dominitz and Allen Tannenbaum. 2009. Texture mapping via optimal mass transport. IEEE transactions on visualization and computer graphics 16, 3 (2009), 419\u2013433."},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-32248-9_71"},{"key":"e_1_2_2_15_1","volume-title":"The 22nd International Conference on Artificial Intelligence and Statistics. PMLR, 2681\u20132690","author":"Feydy Jean","year":"2019","unstructured":"Jean Feydy, Thibault S\u00e9journ\u00e9, Fran\u00e7ois-Xavier Vialard, Shun-ichi Amari, Alain Trouv\u00e9, and Gabriel Peyr\u00e9. 2019b. Interpolating between optimal transport and mmd using sinkhorn divergences. In The 22nd International Conference on Artificial Intelligence and Statistics. PMLR, 2681\u20132690."},{"key":"e_1_2_2_16_1","first-page":"1","article-title":"Pot: Python optimal transport","volume":"22","author":"Flamary R\u00e9mi","year":"2021","unstructured":"R\u00e9mi Flamary, Nicolas Courty, Alexandre Gramfort, Mokhtar Z Alaya, Aur\u00e9lie Boisbunon, Stanislas Chambon, Laetitia Chapel, Adrien Corenflos, Kilian Fatras, Nemo Fournier, et al. 2021. Pot: Python optimal transport. Journal of Machine Learning Research 22, 78 (2021), 1\u20138.","journal-title":"Journal of Machine Learning Research"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/3269376.3269423"},{"key":"e_1_2_2_18_1","volume-title":"A geometry-based approach for solving the transportation problem with Euclidean cost. arXiv preprint arXiv:1706.07403","author":"Hartmann Valentin","year":"2017","unstructured":"Valentin Hartmann. 2017. A geometry-based approach for solving the transportation problem with Euclidean cost. arXiv preprint arXiv:1706.07403 (2017)."},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3592418"},{"key":"e_1_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00211-020-01154-8"},{"key":"e_1_2_2_21_1","volume-title":"The minimum cost flow problem and the network simplex method. Master's thesis","author":"Kelly Damian","year":"1991","unstructured":"Damian Kelly and Garrett O'Niell. 1991. The minimum cost flow problem and the network simplex method. Master's thesis (1991)."},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1179352.1141916"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1051\/m2an\/2015055"},{"key":"e_1_2_2_24_1","volume-title":"Simulating fluids with a computer: Introduction and recent advances. arXiv preprint arXiv:1811.05636","author":"Levy Bruno","year":"2018","unstructured":"Bruno Levy. 2018. Simulating fluids with a computer: Introduction and recent advances. arXiv preprint arXiv:1811.05636 (2018)."},{"key":"e_1_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1093\/mnras\/stab1676"},{"key":"e_1_2_2_26_1","volume-title":"Rectified flow: A marginal preserving approach to optimal transport. arXiv preprint arXiv:2209.14577","author":"Liu Qiang","year":"2022","unstructured":"Qiang Liu. 2022. Rectified flow: A marginal preserving approach to optimal transport. arXiv preprint arXiv:2209.14577 (2022)."},{"key":"e_1_2_2_27_1","volume-title":"Flow straight and fast: Learning to generate and transfer data with rectified flow. arXiv preprint arXiv:2209.03003","author":"Liu Xingchao","year":"2022","unstructured":"Xingchao Liu, Chengyue Gong, and Qiang Liu. 2022. Flow straight and fast: Learning to generate and transfer data with rectified flow. arXiv preprint arXiv:2209.03003 (2022)."},{"key":"e_1_2_2_28_1","doi-asserted-by":"crossref","unstructured":"William E Lorensen and Harvey E Cline. 1998. Marching cubes: A high resolution 3D surface construction algorithm. In Seminal graphics: pioneering efforts that shaped the field. 347\u2013353.","DOI":"10.1145\/280811.281026"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cag.2017.05.001"},{"key":"e_1_2_2_30_1","volume-title":"International Conference on Artificial Intelligence and Statistics. PMLR, 3186\u20133196","author":"M\u00e9rigot Quentin","year":"2020","unstructured":"Quentin M\u00e9rigot, Alex Delalande, and Frederic Chazal. 2020. Quantitative stability of optimal transport maps and linearization of the 2-Wasserstein space. In International Conference on Artificial Intelligence and Statistics. PMLR, 3186\u20133196."},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3272127.3275056"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1093\/imaiai\/iaac023"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/3272127.3275091"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/1015706.1015750"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3386569.3392395"},{"key":"e_1_2_2_36_1","doi-asserted-by":"crossref","unstructured":"Gabriel Peyr\u00e9 Marco Cuturi et al. 2019. Computational optimal transport: With applications to data science. Foundations and Trends\u00ae in Machine Learning 11 5\u20136 (2019) 355\u2013607.","DOI":"10.1561\/2200000073"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICCV.2005.166"},{"key":"e_1_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-24785-9_37"},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/3550454.3555484"},{"key":"e_1_2_2_40_1","volume-title":"Principal geodesic analysis for probability measures under the optimal transport metric. Advances in Neural Information Processing Systems 28","author":"Seguy Vivien","year":"2015","unstructured":"Vivien Seguy and Marco Cuturi. 2015. Principal geodesic analysis for probability measures under the optimal transport metric. Advances in Neural Information Processing Systems 28 (2015)."},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/2766963"},{"key":"e_1_2_2_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2601097.2601107"},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11263-012-0566-z"},{"key":"e_1_2_2_44_1","volume-title":"Arie Kaufman, Jian Sun, Jie Gao, and Feng Luo.","author":"Zhao Xin","year":"2013","unstructured":"Xin Zhao, Zhengyu Su, Xianfeng David Gu, Arie Kaufman, Jian Sun, Jie Gao, and Feng Luo. 2013. Area-preservation mapping using optimal mass transport. IEEE transactions on visualization and computer graphics 19, 12 (2013), 2838\u20132847."}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3731147","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,27]],"date-time":"2026-03-27T17:57:14Z","timestamp":1774634234000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3731147"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,7,27]]},"references-count":44,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,8,1]]}},"alternative-id":["10.1145\/3731147"],"URL":"https:\/\/doi.org\/10.1145\/3731147","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,7,27]]},"assertion":[{"value":"2025-07-27","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}