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 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.

Authors and Affiliations

1. Department of Mathematics, UCLA, Los Angeles, USA

   Levon Nurbekyan

2. Department of Mathematics and Statistics, McGill, Montreal, Canada

   Alexander Iannantuono & Adam M. Oberman

Corresponding author

Correspondence to Levon Nurbekyan.

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

L.N. was supported by Simons Foundation and the Centre de Recherches Mathématiques, through the Simons-CRM scholar-in-residence program, AFOSR MURI FA9550-18-1-0502, and ONR Grant N00014-18-1-2527. This material is based on work supported by the Air Force Office of Scientific Research under Award Number FA9550-18-1-0167.

Appendix

Proof (Theorem 3)

We assume that \(\{e_i\}_{i=1}^d\) is the standard basis in \(\mathbb {R}^d\) because the proof for a general basis is identical up to a multiplication by a suitable volume element.

1. Suppose that \(x \in \mathrm {int}\left( \mathrm {supp}(\mu )\right) \), and \(~x^{\prime }\in \mathbb {R}^d,~x\ne x^{\prime },\) but they never get separated by a hyperplane. Therefore, whenever a common subset containing \(x,x^{\prime }\) gets partitioned they always stay in the same side. Suppose that \(\{A_k\}\) is the sequence of subsets that they both belong during the cutting process. By construction, we have that

Since \(\{v_k\}_{k=1}^\infty \subset \{e_1,e_2,\ldots ,e_d\}\) we have that

where \(-\infty \le \alpha ^k_i <\beta ^k _i \le +\infty \). Denote by

Without loss of generality, assume that

Since \(\{A_k\}\) are rectangles we have that

is also a rectangle, and we denote by

and we have that

Since \(x,x^{\prime } \in R\) we have that

Furthermore, we have that

If \(\mathcal {L}^d(R)>0\) then we have that \(\mathrm {int}(R)\ne \emptyset \) and \(\mathrm {int}(R)\cap \mathrm {supp}(\mu )=\emptyset \) which contradicts to the fact that \(x \in \mathrm {int}\left( \mathrm {supp}(\mu )\right) \). Therefore, we have that \(\mathcal {L}^d(R)=0\) which means that \(\alpha _i=\beta _i\) for some \(i>l\). Without loss of generality assume that

We have that \(q\ge l\). Moreover, \(\alpha _i=\beta _i=x_i=x^{\prime }_i\), and \(-\infty<\alpha _i^k<\beta _i^k<\infty \) for all \(i>q\) and k large enough. Additionally, if \(-\infty<\alpha _i<\beta _i<\infty \) for some \(1\le i \le q\) then \(-\infty<\alpha _i^k<\beta _i^k<\infty \) for k large enough. In what follows we assume that k is so large that this previous statements hold.

Furthermore, assume that \(M>0\) is such that

Since \(\mu =fdx\), by construction we have that

Therefore, using \(c\le f \le C,~\mu \) a.e. we get that

Now, suppose that for some k the set \(A_k\) gets partitioned in the direction \(e_1\). There are three possibilities: (a) \(-\infty<\alpha _1<\beta _1<\infty \), (b) \(-\infty<\alpha _1<\beta _1=\infty \), (c) \(-\infty =\alpha _1<\beta _1<\infty \).

(a) \(-\infty<\alpha _1<\beta _1<\infty \). In this case, we have that \(-\infty<\alpha _1^k<\beta _1^k<\infty \) since k is large enough.Therefore, either

or

for some \(\alpha _1^k<\gamma <\beta _1^k\). Suppose that we are in the former case.

Since \(x\in \mathrm {int}(\mathrm {supp}(\mu ))\) we have that there exists a \(\sigma >0\) such that

We have that

and therefore

where we used the fact that \(\beta _1\le \gamma < \beta _1^k\) and

On the other hand, we have that

therefore

Hence, we obtain that

Similarly, if \(x,x^{\prime }\) fall in the upper (in \(e_1\) direction) half of \(A_k\) we get that

(b) \(-\infty<\alpha _1<\beta _1=\infty \). In this case we have that \(-\infty<\alpha _1^k<\beta _1^k=\infty \), and

for some \(\alpha _1^k<\gamma <\infty \). As before, we have that

Similarly, we have that

and thus

c) \(-\infty =\alpha _1<\beta _1<\infty \). In this case, we have that \(-\infty =\alpha _1^k<\beta _1^k<\infty \), and

Summarizing, we get whenever \(A_k\) gets partitioned in \(e_1\) we have that

We get similar estimates for partitions in any of the directions \(\{e_i\}_{i=1}^q\). Thus, if we take a subsequence \(\{A_{k_m}\}\) that get partitioned in one of these directions we get that

which contradicts to (6). Thus, the first item is proven.

2. Firstly, we will show that for every \(x\in \mathrm {int}(\mathrm {supp}(\mu ))\) there exists \(y \in \mathrm {supp}(\nu )\) such that

Assume that \(\{A_k\}\) is the sequence of partition sets that contain x. Again, we have that

and

for some \(-\infty \le \alpha ^k_i <\beta ^k _i \le +\infty \). Moreover, from the previous item we obtain that

because \(x\in \mathrm {int}(\mathrm {supp}(\mu ))\), and the intersection cannot contain any other point. Therefore, we have that \(-\infty< \alpha ^k_i<\beta ^k _i < +\infty \), and

where \(x=(x_1,x_2,\ldots ,x_d)\).

Denote by \(\{B_k\}\) the dual sequence of \(\{A_k\}\) that partition \(\nu \). Again, we have that

for some \(-\infty< \gamma ^k_i<\delta ^k _i < +\infty \). Thus, our first task is to show that

Since \(\alpha _i^k<x_i\) we have that \(\{\alpha _i^k\}_k\) is not an eventually constant sequence. Therefore, \(\{\gamma ^k_i\}_k\) is also not an eventually constant sequence. Besides, \(\{\gamma ^k_i\}_k\) and \(\{\delta ^k_i\}_k\) are, respectively, nondecreasing and nonincreasing sequences. Therefore, we have that

where

In fact, we have that

Since \(\nu (B_k)>0\) we have that \(\mathrm {cl}(B_k) \cap \mathrm {supp}(\nu ) \ne \emptyset \). Thus,

is a nested family of nonempty compact sets. Therefore, we have that

If \(W_x\cap \mathrm {int}(\mathrm {supp}(\nu )) \ne \emptyset \) then by item 1, we get that

for some \(y \in \mathrm {int}(\mathrm {supp}(\nu ))\). Hence, to complete the proof of item 1, we need to show that there exists a \(F_0 \in \mathcal {B}(\mathbb {R}^d)\) such that \(\mu (F_0)=0\), and

For every k denote by

and

Since

we obtain that

Furthermore, for every \(B \in \varDelta _k^{\prime \prime }\) we have that \(\nu (B)>0\), and therefore \(B \cap \mathrm {supp}(\nu ) \ne \emptyset \). On the other hand, \(B \cap \partial (\mathrm {supp}(\nu )) = \emptyset \), and B is connected. Hence, \(B \subset \mathrm {int}(\mathrm {supp}(\nu ))\), and

Note that

By item 1 we have that for every \(y \in \mathrm {int}(\mathrm {supp}(\nu ))\) there exists a partition rectangle B such that \(y\in B \subset \mathrm {int}(\mathrm {supp}(\nu ))\). Hence, \(B \in \varDelta ^{\prime \prime }_k\) for some k, and \(y \in G_k\). Therefore, we obtain that

Consequently,

Since \(\nu (\mathrm {int}(\mathrm {supp}(\nu )))=1\) we get that

Denote by \(\varOmega _k^{\prime }\) and \(\varOmega _k^{\prime \prime }\) the families dual to \(\varDelta _k^{\prime }\) and \(\varDelta _k^{\prime \prime }\). Furthermore, denote by

By construction, we have that

Moreover,

Denote by

Then, we have that \(F_0 \in \mathcal {B}(\mathbb {R}^d)\), and

Finally, note that if \(W_x \cap \mathrm {int}(\mathrm {supp}(\nu ))=\emptyset \) then \(x\in F_0\).

3. From items 1, 2 we have that the map \(\hat{t}: \mathrm {int}(\mathrm {supp}(\mu )) {\setminus } F_0 \rightarrow \mathrm {int}(\mathrm {supp}(\nu ))\) given by

is well defined. Our first task is to show that \(\hat{t}\) is Borel measurable. For that, we need to show that \(\hat{t}^{-1}(G) \in \mathcal {B}(\mathbb {R}^d)\) for any open set \(G \subset \mathbb {R}^d\). Since \(\mathrm {Im}(\hat{t}) \subset \mathrm {int}(\mathrm {supp}(\nu ))\) we have that

Therefore, we may assume that \(G \subset \mathrm {int}(\mathrm {supp}(\nu ))\). Furthermore, denote by

Next, define

Then we have that

From item 1, we have that for every \(y\in G\) there exists a partition set B such that \(y\in B \subset G\). Hence, we get that

This means that

On the other hand, from Eq. (4) in Theorem 2 we have that

where \(\varOmega _k^{\prime },\varOmega _k^{\prime \prime }\) are the dual families of \(\varDelta _k^{\prime },\varDelta _k^{\prime \prime }\). Therefore, we have that \(\hat{t}^{-1}(G) \in \mathcal {B}(\mathbb {R}^d)\). Furthermore, denote by

By construction, we have that

and hence

On the other hand, from construction and equations \(\mu (F_0)=0\), \(\mu (\mathrm {int}(\mathrm {supp}(\mu )))=1\), we have that

Therefore, we obtain that

Thus, \(\hat{t}\) is Borel measurable and \(\hat{t}\sharp \mu =\nu \). Finally, from item 1 we have that points in \(\mathrm {Im}(\hat{t})\subset \mathrm {int}(\mathrm {supp}(\nu ))\) get eventually separated. Therefore, by Theorem 2 we obtain that \(\hat{t}\) is half-space-preserving. \(\square \)

Proof (Theorem 4)

Denote by H the union of all the hyperplanes that partition \(\mu \). Then we have that \(\mathcal {L}^d(H)=\mu (H)=0\). We prove that \(\hat{t}\) is continuous on \(\mathrm {Dom}(\hat{t}){\setminus } H\).

Suppose \(x\in \mathrm {Dom}(\hat{t}){\setminus } H\), and \(y=\hat{t}(x)\). Furthermore, denote by \(\{A_k\}\) and \(\{B_k\}\) the rectangles that contain x and y, respectively. We have that

Moreover, since \(x\notin H\) we have that \(x\in \mathrm {int}(A_k)\) for all k. Therefore, by construction, we have that \(y\in \mathrm {int}(B_k)\) for all k. Thus, we obtain that

which yields the continuity. \(\square \)

Reprints and permissions