# No-collision Transportation Maps

arXiv: https://arxiv.org/abs/1912.02317 · HTML: https://mlsanity.com/paper/1912.02317/

## Key facts

- Cited by 5 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 5 Dec 2019.

## Built on by (most cited first, 5 of 5)

- [Multisample Flow Matching: Straightening Flows with Minibatch Couplings](https://mlsanity.com/paper/2304.14772/) (2023)
- [Applications of No-Collision Transportation Maps in Manifold Learning](https://mlsanity.com/paper/2304.00199/) (2023)
- [Measure transfer via stochastic slicing and matching](https://mlsanity.com/paper/2307.05705/) (2023)
- [Improving Consistency Models with Generator-Augmented Flows](https://mlsanity.com/paper/2406.09570/) (2024)
- [SRRM: Improving Recursive Transport Surrogates in the Small-Discrepancy Regime](https://mlsanity.com/paper/2603.18781/) (2026)

## Abstract (arXiv)

Transportation maps between probability measures are critical objects in numerous areas of mathematics and applications such as PDE, fluid mechanics, geometry, machine learning, computer science, and economics. Given a pair of source and target measures, one searches for a map that has suitable properties and transports the source measure to the target one. Here, we study maps that possess the textitno-collision property; that is, particles simultaneously traveling from sources to targets in a unit time with uniform velocities do not collide. These maps are particularly relevant for applications in swarm control problems. We characterize these no-collision maps in terms of textithalf-space preserving property and establish a direct connection between these maps and textitbinary-space-partitioning (BSP) tree structures. Based on this characterization, we provide explicit BSP algorithms, of cost O(n log n), to construct no-collision maps. Moreover, interpreting these maps as approximations of optimal transportation maps, we find that they succeed in computing nearly optimal maps for q-Wasserstein metric (q=1,2). In some cases, our maps yield costs that are just a few percent off from being optimal.