Almost sure convergence of the minimum bipartite matching functional in Euclidean space

Abstract

Let $L_N=L_{MBM}(X_1,...,X_N;Y_1,...,Y_N)$ be the minimum length of a bipartite matching between two sets of points in ${\mathbf{R}}^d$, where $X_1,...,X_N,...$ and $Y_1,...,Y_N,...$ are random points independently and uniformly distributed in $[0,1{]}^d$. We prove that for $d\ge 3$, $L_N/N^{1-1/d}$ converges with probability one to a constant ${\beta }_{MBM}(d)>0$ as $N\to \infty$.

To appear in Combinatorica