Match off points into $N$ red/blue pairs with straight lines connecting pairs, so that none of lines we draw intersect

Question

Suppose we are given $2N$ points in the plane (we may assume that no $3$ are collinear). Assume that $N$ of these points are colored red, and $N$ points are colored blue. Can we match off the points into $N$ red/blue pairs with straight lines connecting these pairs, so that none of the lines we draw intersect? If this matching exists, can we find it by an algorithm?

Answer 1

Yes, such a matching always exist.

The algorithm works recursively. You either

1) find a pair of red and blue point R and B such that the number of red points and blue points on the left side of the vector RB is the same. You match RB, and then you recursively find the matchings for all the points on each side of the vector separately.

or

2) find any line that divides the plane into two non-empty planes such that the number of red and blue points on each side of the line is equal. You recursively find matchings on these points on each side of the line separately.

We need to prove that either one of these two cases must happen. Suppose case 1) does not exists. Consider any pair of node R and B. Consider the vector RB. RB divides the remaining points into those that are on the left side of the vector, and those on the right side of the vector. Given a vector RB, let RB_left be the the number of red points on the left of RB substracted by the number of blue points on the left of RB. Since case 1 does not exist, RB_left is not zero. We also have RB_left = -BR_left. Now consider rotating the vector X=RB using until it eventually becomes BR, and consider what happens to X_left. Each time the vector is collinear with a point, then X_left will increase or decrease by 1 point. Since BR_left = -RB_right, there must be some time in which X_left = 0.