{"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":1783107001298,"version":"3.54.6"},"reference-count":55,"publisher":"Association for Computing Machinery (ACM)","issue":"6","funder":[{"name":"ANR","award":["ANR-22-CE46- 0006"],"award-info":[{"award-number":["ANR-22-CE46- 0006"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Graph."],"published-print":{"date-parts":[[2025,12]]},"abstract":"<jats:p>\n                    To solve the optimal transport problem between two uniform discrete measures of the same size, one seeks a bijective assignment that minimizes some matching cost. For this task, exact algorithms are intractable for large problems, while approximate ones may lose the bijectivity of the assignment. We address this issue and the more general cases of non-uniform discrete measures with different total masses, where partial transport may be desirable. The core of our algorithm is a variant of the Quicksort algorithm that provides an efficient strategy to randomly explore many relevant and easy-to-compute couplings, by matching BSP trees in loglinear time. The couplings we obtain are as sparse as possible, in the sense that they provide bijections, injective partial matchings or sparse couplings depending on the nature of the matched measures. To improve the transport cost, we propose efficient strategies to merge\n                    <jats:italic toggle=\"yes\">k<\/jats:italic>\n                    sparse couplings into a higher quality one. For\n                    <jats:italic toggle=\"yes\">k =<\/jats:italic>\n                    64, we obtain transport plans with typically less than 1% of relative error in a matter of seconds between hundreds of thousands of points in 3D on the CPU. We demonstrate how these high-quality approximations can drastically speed-up usual pipelines involving optimal transport, such as shape interpolation, intrinsic manifold sampling, color transfer, topological data analysis, rigid partial registration of point clouds and image stippling.\n                  <\/jats:p>","DOI":"10.1145\/3763281","type":"journal-article","created":{"date-parts":[[2025,12,4]],"date-time":"2025-12-04T17:15:39Z","timestamp":1764868539000},"page":"1-15","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":2,"title":["BSP-OT: Sparse transport plans between discrete measures in loglinear time"],"prefix":"10.1145","volume":"44","author":[{"ORCID":"https:\/\/orcid.org\/0009-0009-7718-5553","authenticated-orcid":false,"given":"Baptiste","family":"Genest","sequence":"first","affiliation":[{"name":"Universit\u00e9 Claude Bernard Lyon 1, Villeurbanne, France"},{"name":"CNRS, Villeurbanne, France"},{"name":"INSA Lyon, Villeurbanne, 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, Villeurbanne, France"},{"name":"Universit\u00e9 Claude Bernard Lyon 1, Villeurbanne, France"},{"name":"INSA Lyon, Villeurbanne, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5242-1585","authenticated-orcid":false,"given":"Vincent","family":"Nivoliers","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Claude Bernard Lyon 1, Villeurbanne, France"},{"name":"CNRS, Villeurbanne, France"},{"name":"INSA Lyon, Villeurbanne, France"}],"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, Villeurbanne, France"},{"name":"Universit\u00e9 Claude Bernard Lyon 1, Villeurbanne, France"},{"name":"INSA Lyon, Villeurbanne, France"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,12,4]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3550454.3555519"},{"key":"e_1_2_2_2_1","volume-title":"Massively scalable Sinkhorn distances via the Nystr\u00f6m method. Advances in neural information processing systems 32","author":"Altschuler Jason","year":"2019","unstructured":"Jason Altschuler, Francis Bach, Alessandro Rudi, and Jonathan Niles-Weed. 2019. Massively scalable Sinkhorn distances via the Nystr\u00f6m method. Advances in neural information processing systems 32 (2019)."},{"key":"e_1_2_2_3_1","volume-title":"Computing Kantorovich-Wasserstein Distances on d-dimensional histograms using (d +1)-partite graphs. Advances in Neural Information Processing Systems 31","author":"Auricchio Gennaro","year":"2018","unstructured":"Gennaro Auricchio, Federico Bassetti, Stefano Gualandi, and Marco Veneroni. 2018. Computing Kantorovich-Wasserstein Distances on d-dimensional histograms using (d +1)-partite graphs. Advances in Neural Information Processing Systems 31 (2018)."},{"key":"e_1_2_2_4_1","volume-title":"International Conference on machine learning. PMLR, 497\u2013506","author":"Backurs Arturs","year":"2020","unstructured":"Arturs Backurs, Yihe Dong, Piotr Indyk, Ilya Razenshteyn, and Tal Wagner. 2020. Scalable nearest neighbor search for optimal transport. In International Conference on machine learning. PMLR, 497\u2013506."},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR52729.2023.01315"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1287\/inte.20.4.133"},{"key":"e_1_2_2_7_1","volume-title":"MREC: a fast and versatile framework for aligning and matching point clouds with applications to single cell molecular data. arXiv preprint arXiv:2001.01666","author":"Blumberg Andrew J","year":"2020","unstructured":"Andrew J Blumberg, Mathieu Carriere, Michael A Mandell, Raul Rabadan, and Soledad Villar. 2020. MREC: a fast and versatile framework for aligning and matching point clouds with applications to single cell molecular data. arXiv preprint arXiv:2001.01666 (2020)."},{"key":"e_1_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3306346.3323021"},{"key":"e_1_2_2_9_1","volume-title":"Computer Graphics Forum","author":"Bonneel Nicolas","unstructured":"Nicolas Bonneel and Julie Digne. 2023. A survey of optimal transport for computer graphics and computer vision. In Computer Graphics Forum, Vol. 42. Wiley Online Library, 439\u2013460."},{"key":"e_1_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10851-014-0506-3"},{"key":"e_1_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2024156.2024192"},{"key":"e_1_2_2_12_1","volume-title":"Unidimensional and evolution methods for optimal transportation. Ph. D. Dissertation. Universit\u00e9 Paris Sud-Paris XI","author":"Bonnotte Nicolas","unstructured":"Nicolas Bonnotte. 2013. Unidimensional and evolution methods for optimal transportation. Ph. D. Dissertation. Universit\u00e9 Paris Sud-Paris XI; Scuola normale superiore (Pise, Italie)."},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2461912.2461986"},{"key":"e_1_2_2_14_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_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/2366145.2366190"},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2018.00367"},{"key":"e_1_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/3731147"},{"key":"e_1_2_2_18_1","volume-title":"Geometric data analysis, beyond convolutions. Applied Mathematics 3","author":"Feydy Jean","year":"2020","unstructured":"Jean Feydy. 2020. Geometric data analysis, beyond convolutions. Applied Mathematics 3 (2020)."},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-32248-9_71"},{"key":"e_1_2_2_20_1","first-page":"51706","article-title":"A robust exact algorithm for the euclidean bipartite matching problem","volume":"36","author":"Gattani Akshaykumar","year":"2023","unstructured":"Akshaykumar Gattani, Sharath Raghvendra, and Pouyan Shirzadian. 2023. A robust exact algorithm for the euclidean bipartite matching problem. Advances in Neural Information Processing Systems 36 (2023), 51706\u201351718.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_2_2_21_1","volume-title":"Computer Graphics Forum","author":"Genest Baptiste","unstructured":"Baptiste Genest, Nicolas Courty, and David Coeurjolly. 2024. Non-Euclidean Sliced Optimal Transport Sampling. In Computer Graphics Forum, Vol. 43. Wiley Online Library, e15020."},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/237170.237244"},{"key":"e_1_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR46437.2021.00929"},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3064175"},{"key":"e_1_2_2_25_1","volume-title":"Scalable optimal transport methods in machine learning: A contemporary survey","author":"Khamis Abdelwahed","year":"2024","unstructured":"Abdelwahed Khamis, Russell Tsuchida, Mohamed Tarek, Vivien Rolland, and Lars Petersson. 2024. Scalable optimal transport methods in machine learning: A contemporary survey. IEEE transactions on pattern analysis and machine intelligence (2024)."},{"key":"e_1_2_2_26_1","volume-title":"The Hungarian method for the assignment problem. Naval research logistics quarterly 2, 1\u20132","author":"Kuhn Harold W","year":"1955","unstructured":"Harold W Kuhn. 1955. The Hungarian method for the assignment problem. Naval research logistics quarterly 2, 1\u20132 (1955), 83\u201397."},{"key":"e_1_2_2_27_1","volume-title":"Tree-sliced variants of Wasserstein distances. Advances in neural information processing systems 32","author":"Le Tam","year":"2019","unstructured":"Tam Le, Makoto Yamada, Kenji Fukumizu, and Marco Cuturi. 2019. Tree-sliced variants of Wasserstein distances. Advances in neural information processing systems 32 (2019)."},{"key":"e_1_2_2_28_1","unstructured":"Bruno Levy. 2025. geogram. https:\/\/github.com\/BrunoLevy\/geogram"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1559755.1559758"},{"key":"e_1_2_2_30_1","volume-title":"International Conference on machine learning. PMLR, 4104\u20134113","author":"Liutkus Antoine","year":"2019","unstructured":"Antoine Liutkus, Umut Simsekli, Szymon Majewski, Alain Durmus, and Fabian-Robert St\u00f6ter. 2019. Sliced-Wasserstein flows: Nonparametric generative modeling via optimal transport and diffusions. In International Conference on machine learning. PMLR, 4104\u20134113."},{"key":"e_1_2_2_31_1","first-page":"35350","article-title":"Fast optimal transport through sliced generalized Wasserstein geodesics","volume":"36","author":"Mahey Guillaume","year":"2023","unstructured":"Guillaume Mahey, Laetitia Chapel, Gilles Gasso, Cl\u00e9ment Bonet, and Nicolas Courty. 2023. Fast optimal transport through sliced generalized Wasserstein geodesics. Advances in Neural Information Processing Systems 36 (2023), 35350\u201335385.","journal-title":"Advances in Neural Information Processing Systems"},{"key":"e_1_2_2_32_1","volume-title":"A convexity principle for interacting gases. Advances in mathematics 128, 1","author":"McCann Robert J","year":"1997","unstructured":"Robert J McCann. 1997. A convexity principle for interacting gases. Advances in mathematics 128, 1 (1997), 153\u2013179."},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8655(02)00328-8"},{"key":"e_1_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.amc.2009.01.013"},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/23M1567771"},{"key":"e_1_2_2_36_1","volume-title":"Sliced wasserstein estimation with control variates. arXiv preprint arXiv:2305.00402","author":"Nguyen Khai","year":"2023","unstructured":"Khai Nguyen and Nhat Ho. 2023. Sliced wasserstein estimation with control variates. arXiv preprint arXiv:2305.00402 (2023)."},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10915-020-01143-x"},{"key":"e_1_2_2_38_1","volume-title":"An efficient linear programming method for optimal transportation. arXiv preprint arXiv:1509.03668","author":"Oberman Adam M","year":"2015","unstructured":"Adam M Oberman and Yuanlong Ruan. 2015. An efficient linear programming method for optimal transportation. arXiv preprint arXiv:1509.03668 (2015)."},{"key":"e_1_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02614365"},{"key":"e_1_2_2_40_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_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/3119910"},{"key":"e_1_2_2_42_1","volume-title":"International conference on scale space and variational methods in computer vision. Springer, 435\u2013446","author":"Rabin Julien","year":"2011","unstructured":"Julien Rabin, Gabriel Peyr\u00e9, Julie Delon, and Marc Bernot. 2011. Wasserstein barycenter and its application to texture mixing. In International conference on scale space and variational methods in computer vision. Springer, 435\u2013446."},{"key":"e_1_2_2_43_1","volume-title":"Symposium on geometry processing","volume":"257","author":"Raif","unstructured":"Raif M Rustamov et al. 2007. Laplace-Beltrami eigenfunctions for deformation invariant shape representation. In Symposium on geometry processing, Vol. 257. 225\u2013233."},{"key":"e_1_2_2_44_1","volume-title":"Scalable multi-class sampling via filtered sliced optimal transport. arXiv preprint arXiv:2211.04314","author":"Sala\u00fcn Corentin","year":"2022","unstructured":"Corentin Sala\u00fcn, Iliyan Georgiev, Hans-Peter Seidel, and Gurprit Singh. 2022. Scalable multi-class sampling via filtered sliced optimal transport. arXiv preprint arXiv:2211.04314 (2022)."},{"key":"e_1_2_2_45_1","volume-title":"Optimal transport for applied mathematicians","author":"Santambrogio Filippo","unstructured":"Filippo Santambrogio. 2015. Optimal transport for applied mathematicians. Vol. 87. Springer."},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10851-016-0653-9"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1106018"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214014"},{"key":"e_1_2_2_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/2766963"},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/2601097.2601175"},{"key":"e_1_2_2_51_1","volume-title":"Trang Pham, Thanh T Chu, Tam Le, and Tan M Nguyen.","author":"Tran Hoang V","year":"2025","unstructured":"Hoang V Tran, Khoi NM Nguyen, Trang Pham, Thanh T Chu, Tam Le, and Tan M Nguyen. 2025. Distance-based tree-sliced Wasserstein distance. arXiv preprint arXiv:2503.11050 (2025)."},{"key":"e_1_2_2_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/TVCG.2019.2934256"},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/CVPR.2019.00383"},{"key":"e_1_2_2_54_1","volume-title":"Approximating 1-wasserstein distance with trees. arXiv preprint arXiv:2206.12116","author":"Yamada Makoto","year":"2022","unstructured":"Makoto Yamada, Yuki Takezawa, Ryoma Sato, Han Bao, Zornitsa Kozareva, and Sujith Ravi. 2022. Approximating 1-wasserstein distance with trees. arXiv preprint arXiv:2206.12116 (2022)."},{"key":"e_1_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.cad.2023.103511"}],"container-title":["ACM Transactions on Graphics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3763281","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,12,5]],"date-time":"2025-12-05T21:20:00Z","timestamp":1764969600000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3763281"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,12]]},"references-count":55,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2025,12]]}},"alternative-id":["10.1145\/3763281"],"URL":"https:\/\/doi.org\/10.1145\/3763281","relation":{},"ISSN":["0730-0301","1557-7368"],"issn-type":[{"value":"0730-0301","type":"print"},{"value":"1557-7368","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,12]]},"assertion":[{"value":"2025-05-23","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-08-09","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-12-04","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}