Complexity of matching red and blue points in the plane. I'm just asking because I'm curious.
I was seeking references on the following problem, that a friend exposed to me last holidays  :
Problem
Given $n$ red points and $n$ blue points in the plane in general position (no 3 of them are aligned), find a pairing of the red points with the blue points such that the segments it draws are all disjoint.
This problem is always solvable, and admits several proof. A proof I know goes like this :
Start with an arbitrary pairing, and look for intersections of the segments it defines, if there are none you're done. If you found one, do the following operation :
r   r         r   r
 \ /          |   |
  X     =>    |   |
 / \          |   |
b   b         b   b

(uncross the crossing you have found), you may create new crossings with this operation. If you repeat this operation, you cannot cycle, because the triangle inequality shows that the sum of the length of the segments is strictly decreasing. So you will eventually get stuck at a configuration with no crossings.
Questions


*

*What is the complexity of the algorithm described in the proof ?

*What is the best known algorithm to solve this problem ?


I wouldn't be surprised to learn that this problem is a classic in computational geometry, however googling didn't give me references. Since some computational geometers are active on MO, I thought I could get interesting answers here.
 A: Check out the classic Cormen, Leiserson, Rivest, Stein, ''Introduction to algorithms'', second edition.  In chapter 33 (Computational Geometry).  See the exercises at the end of the whole chapter: exercise 33-3 is your problem.  The full solution isn't described, but you will find a hint for a polynomial time algorithm.  I have no idea whether that's the fastest algorithm known.
A: In the paper Geometry Helps in Matching, by P. Vaidya, he shows that the minimum matching (which is what you are finding here) can be found in $O(n^2 \log^3(n))$ time.
A: The Ghosts and Ghostbusters problem can be solved in $O(n\log n)$ time, which is considerably faster than the  $O(n^2\log n)$-time algorithm suggested by CLRS.
The ham sandwich theorem implies that there is a line $L$ that  splits both the ghosts and the ghostbusters exactly in half. (If the number of ghosts and ghostbusters is odd, the line passes through one of each; if the number is even, the line passes through neither.)  Lo, Matoušek, and Steiger [Discrete Comput. Geom. 1994] describe an algorithm to compute a ham-sandwich line in $O(n)$ time; their algorithm is also sketched here.  Now recursively solve the problem on both sides of $L$; the recursion stops when all subsets are empty.  The total running time obeys the mergesort recurrence $T(n) = O(n) + 2T(n/2)$ and thus is $O(n\log n)$.
This algorithm is optimal in the algebraic decision tree and algebraic computation tree models of computation, because you need $\Omega(n\log n)$ time in those models just to decide whether two sets of $n$ points are equal.
