Papers › An algorithm for optimal transport between a simplex soup and a point cloud
An algorithm for optimal transport between a simplex soup and a point cloud
Quentin Mérigot, Jocelyn Meyron, Boris Thibert
The archive published only this paper's code-link row. Authors, date and abstract are from arXiv's metadata (CC0), read from the Kaggle arXiv metadata snapshot of 2026-09-12 where its title matched the archive's; the title is the archive's.
We propose a numerical method to find the optimal transport map between a measure supported on a lower-dimensional subset of R^d and a finitely supported measure. More precisely, the source measure is assumed to be supported on a simplex soup, i.e. on a union of simplices of arbitrary dimension between 2 and d. As in [Aurenhammer, Hoffman, Aronov, Algorithmica 20 (1), 1998, 61--76] we recast this optimal transport problem as the resolution of a non-linear system where one wants to prescribe the quantity of mass in each cell of the so-called Laguerre diagram. We prove the convergence with linear speed of a damped Newton's algorithm to solve this non-linear system. The convergence relies on two conditions: (i) a genericity condition on the point cloud with respect to the simplex soup and (ii) a (strong) connectedness condition on the support of the source measure defined on the simplex soup. Finally, we apply our algorithm in R^3 to compute optimal transport plans between a measure supported on a triangulation and a discrete measure. We also detail some applications such as optimal quantization of a probability density over a surface, remeshing or rigid point set registration on a mesh.
Code
Repository list and official/mentioned flags are the archive's, frozen 2025-07-28. Reachability, where shown, is from one Syntology probe window (2026-09-16 to 2026-09-18); repositories not probed show nothing. GitHub stars are not tracked.
Code Syntology ran Syntology
Not run by Syntology. Nothing on this page verifies that the listed code works.
Results from the paper archive 2025-07-28
No leaderboard rows for this paper in the archive.
Report a problem or propose a change · a person checks every report against the paper or source before anything changes; decisions are listed on /corrections