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

J. Boutet De Monvel 1, Olivier C. Martin 2

COMBINATORICA 22 (2002) 523-530

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

  • 1. Center for Hearing and Communication Research,
    Karolinska Institutet
  • 2. Laboratoire de Physique Théorique et Modèles Statistiques (LPTMS),
    CNRS : UMR8626 – Université Paris XI - Paris Sud