No-collision Transportation Maps

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.