  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 \textit{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
\textit{half-space preserving} property and establish a direct connection
between these maps and \textit{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.
