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 no-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 half-space preserving property and establish a direct
connection between these maps and binary-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.