Draw straight lines matching red points to blue points. If two lines cross, swapping their destinations often looks like an obvious improvement. For ordinary Euclidean length, this intuition is correct: a shortest matching has no proper crossings.
It is tempting to imagine that eliminating crossings almost solves the problem. Yet even on a convex polygon, there remain exponentially many noncrossing matchings. Their exact number is a Catalan number. The connection is useful both conceptually and algorithmically: it gives a short counting proof, an exact uniform sampler, and a clean distinction between feasible, locally improved, and globally optimal matchings. The geometric starting point is Proposition 1.5 of my book [1].
Uncrossing: the cost matters
Let \(x_1,\ldots,x_n\) be red points and \(y_1,\ldots,y_n\) blue points in the plane. A perfect matching is a permutation \(\sigma\), with mean length
\[ E(\sigma)=\frac1n\sum_{i=1}^n|x_i-y_{\sigma(i)}|. \]This is the discrete optimal-transport problem between the equally weighted clouds with cost \(c(x,y)=|x-y|\). A proper crossing is an intersection in the interiors of two noncollinear segments.
Proposition 1 (uncrossing decreases length). A minimum-length perfect matching has no proper crossings.
Proof: reconnect at the crossing point
Suppose \([x_i,y_j]\) and \([x_k,y_\ell]\) cross properly at \(z\). The triangle inequalities are strict after reconnecting, because the original segments are not collinear:
\[ \begin{aligned} |x_i-y_\ell|&<|x_i-z|+|z-y_\ell|,\\ |x_k-y_j|&<|x_k-z|+|z-y_j|. \end{aligned} \]Adding the inequalities gives a strict improvement over \(|x_i-y_j|+|x_k-y_\ell|\). Swapping these two destinations preserves the perfect-matching constraints, a contradiction. \(\square\)
The proof uses length, not an arbitrary increasing function of length. For squared Euclidean cost, a proper crossing can actually be optimal.
A four-point counterexample for squared cost
Let \(e=(1,0)\), \(f=(1/2,\sqrt3/2)\), and choose \(x_1=-10e\), \(x_2=-f\), \(y_1=e\), \(y_2=10f\). The diagonal matching consists of two segments crossing at the origin. Its squared-cost matrix is
\[ \bigl(|x_i-y_j|^2\bigr)_{i,j} =\begin{pmatrix}121&300\\3&121\end{pmatrix}. \]The crossing assignment has total squared cost \(242\), versus \(303\) after swapping; divide both by two for the mean costs. For ordinary total length, the comparison reverses: \(22>\sqrt{300}+\sqrt3\). The choice of ground cost is essential.
Counting the survivors
Place \(2n\) points on a strictly convex polygon, with red and blue colors alternating around its boundary. Every noncrossing chord separates two arcs, and points on either arc must be matched internally. This recursive geometry is exactly the Catalan recursion [2].
Theorem 1 (Catalan multiplicity). The number of noncrossing red–blue perfect matchings of these alternating vertices is
\[ C_n=\frac1{n+1}\binom{2n}{n} \sim\frac{4^n}{\sqrt\pi\,n^{3/2}}. \]Proof: condition on the partner of the first vertex
Number the vertices \(0,\ldots,2n-1\) cyclically, starting with a red vertex. If vertex \(0\) is paired with vertex \(2k+1\), the chord leaves \(2k\) vertices on one arc and \(2(n-1-k)\) on the other. They must be matched separately. Their alternating colors are balanced, so
\[ C_0=1,\qquad C_n=\sum_{k=0}^{n-1}C_kC_{n-1-k}. \]Conversely, any two noncrossing matchings on these arcs combine with that chord to give a valid matching. If \(C(z)=\sum_{n\ge0}C_nz^n\), the recursion becomes \(C(z)=1+zC(z)^2\). The solution with constant term \(1\) is
\[ C(z)=\frac{1-\sqrt{1-4z}}{2z}. \]Expanding the square root gives \(C_n=(n+1)^{-1}\binom{2n}{n}\); Stirling's formula gives the asymptotic. Equivalently, any ordinary noncrossing perfect matching on these alternating vertices is automatically red–blue: a chord must leave an even number of vertices on each side, so its endpoints have opposite parity. \(\square\)
Already \(C_{10}=16{,}796\), and \(C_{20}=6{,}564{,}120{,}420\). Removing crossings leaves a large search space. This is a counting statement, not a computational-hardness result: minimum-cost assignment is polynomial-time solvable, for instance by the Hungarian method [3]. On a convex polygon, the same interval recursion also yields a dynamic program for the best noncrossing matching.
From counting to exact optimization in cubic time
Write the cyclically ordered vertices as \(v_0,\ldots,v_{2n-1}\). For an interval containing an even number of vertices, let \(L_{i,j}\) be its minimum total matching length; an empty interval has value zero. Conditioning on the partner of \(v_i\) gives
\[ L_{i,j} =\min_{\substack{k=i+1,i+3,\ldots,j}} \left\{|v_i-v_k|+L_{i+1,k-1}+L_{k+1,j}\right\}. \]The admissible partners have the opposite color, and the chord splits the remaining vertices into independent subproblems. Compute intervals in increasing order of length. There are \(O(n^2)\) intervals and at most \(O(n)\) choices per interval, so the minimum is found with \(O(n^3)\) arithmetic operations. The mean optimal cost is \(L_{0,2n-1}/n\). Exponentially many feasible objects need not require exponential enumeration.
Uniform exploration without rejection
Drawing a random permutation and rejecting all crossings quickly becomes wasteful. The counting proof gives a direct sampler instead.
Proposition 2 (an exact uniform sampler). Choose the partner \(2k+1\) of vertex \(0\) with probability
\[ p_k=\frac{C_kC_{n-1-k}}{C_n}, \]then sample independently and uniformly on the two remaining arcs. The resulting perfect matching is uniform over all \(C_n\) noncrossing matchings.
Proof: the number of completions cancels the sampling weight
Fix a particular matching whose first partner is \(2k+1\). By induction, its two submatchings are sampled with probabilities \(1/C_k\) and \(1/C_{n-1-k}\). Its total probability is therefore
\[ \frac{C_kC_{n-1-k}}{C_n} \frac1{C_k}\frac1{C_{n-1-k}}=\frac1{C_n}. \]The empty matching starts the induction. \(\square\)
Choosing \(k\) uniformly would be wrong: splits with more possible completions must receive more probability. This is a general recipe for exact combinatorial sampling—weight each branch of a recursive construction by its number of completions.
Improvement is different from exploration
A simple local move chooses two red points and swaps their blue destinations. Reject the move if it introduces a crossing. Otherwise, the change in mean length is
\[ \Delta E=\frac1n\left( |x_i-y_{\sigma(k)}|+|x_k-y_{\sigma(i)}| -|x_i-y_{\sigma(i)}|-|x_k-y_{\sigma(k)}| \right). \]Accepting only strict decreases permits only finitely many successful moves, because no matching can be revisited. Testing a finite batch of random swaps does not even certify local optimality; checking every pair does, but still does not certify global optimality. The distinction occurs with just three pairs on a circle.
An explicit strict local minimum which is not global
Place six alternating vertices on the unit circle at angles
\[ (\theta_0,\ldots,\theta_5) =(\pi/12,\pi/3,2\pi/3,\pi,4\pi/3,5\pi/3). \]The matching \((0,5),(2,1),(4,3)\) has total length \(2+2\sin(5\pi/24)\). The other all-adjacent matching \((0,1),(2,3),(4,5)\) is strictly shorter, with length \(2+2\sin(\pi/8)\).
Nevertheless, the three possible two-pair swaps from the first matching have total lengths
\[ 3+2\sin(\pi/8),\qquad 2+2\sin(11\pi/24),\qquad 3+2\sin(5\pi/24). \]All are larger. For the first, use
\[ 2[\sin(5\pi/24)-\sin(\pi/8)]<\pi/6<1 \]The other two comparisons are immediate. The starting matching is therefore a strict local minimum even among all pair swaps, while a better noncrossing matching exists. A simultaneous three-cycle of destinations is needed to pass directly to that better matching.
One can also turn exploration into a Metropolis sampler. At temperature \(\tau>0\), accept a symmetric proposal with probability \(\min(1,e^{-\Delta E/\tau})\). The corresponding equilibrium weights are proportional to \(e^{-E/\tau}\), as in the Markov-chain methodology of [4].
Why occasional global proposals give a valid equilibrium sampler
Write \(w(\sigma)=e^{-E(\sigma)/\tau}\) and let \(a(\sigma,\sigma')=\min(1,w(\sigma')/w(\sigma))\) be the acceptance probability. For a symmetric proposal \(q\),
\[ w(\sigma)\,q(\sigma,\sigma')\,a(\sigma,\sigma') =q(\sigma,\sigma')\min(w(\sigma),w(\sigma')). \]The expression is symmetric in the two states. Local pair swaps alone would additionally require a connectivity argument. Instead, occasionally propose a whole matching using Proposition 2. This gives positive proposal probability between every pair of states. Add a fixed probability of staying put: the resulting finite chain is irreducible and aperiodic, so it converges to its unique Boltzmann equilibrium at every fixed positive temperature.
As \(\tau\downarrow0\), those equilibrium laws concentrate on minimum-cost matchings. This statement does not assert convergence to a global optimum under an arbitrary finite cooling schedule.
Numerical experimentation
The points below alternate around an irregularly spaced convex ellipse. Draw a uniform noncrossing matching, try downhill swaps, or explore many independent matchings. “Load three-pair trap” switches to the explicit circular example above: every downhill swap is rejected even though the displayed optimum is strictly lower. The figure reports the true unrestricted assignment optimum as a reference; Proposition 1 guarantees that this optimum is attained by a noncrossing matching.
The geometry gives a useful necessary condition, the recursion counts and samples its solutions, and optimization still has to choose among them. Keeping these three tasks distinct prevents a visually pleasing noncrossing drawing from being mistaken for a proof of optimality.
References
- Gabriel Peyré. Optimal Transport for Machine Learners, 2025–2026. Proposition 1.5, p. 7.
- Richard P. Stanley. Catalan Numbers. Cambridge University Press, 2015.
- Harold W. Kuhn. The Hungarian method for the assignment problem. Naval Research Logistics Quarterly 2(1–2), 83–97, 1955.
- W. Keith Hastings. Monte Carlo sampling methods using Markov chains and their applications. Biometrika 57(1), 97–109, 1970.