Matching red and blue points in the plane 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.
What is the easiest solution for this using analysis?Can we use somehow Bolzano theorem?
 A: You need a construction algorithm, and I think both Bolzano and convex hull could help, and a little theorem:
A finite set of points has a finite set of directions of the lines that connect the points. From the continuous set of directions of lines, we can select one that is not in this set.


*

*for $n=1$ a trivial solution exists.

*take the convex hull, if it contains two different colors, there is one safe transition you can take out and have the problem reduced to $n-1$.

*if not, take a line from the theorem, and translate it through the hull, counting the difference between red and blue points on both sides of the line

*when the line enters and exits the hull the values are -1 and 1, and because of Bolzano and the unique direction that makes that the function only changes by 1, there is a point in the middle that bisects the problem in two smaller problems.

*solve recursively until problem is trivial.

A: Another construction algorithm-joke (algorithm from @Pieter21 is better)
Lemma:
For the convex polygon ABCD 
AB + CD  < AC + BD
Proof of lemma: 
Let E is the intersection point of AD and BC
AB < AE+BE, CD < CE+DE => AB+CD < (AE+EC) + (BE + ED) = AC + BD.
QED. 
Algo-joke:
Start with any pairing of red and blue points.
While this pairing has intersections: 


*

*Find  intersected segments AC and BD (A and D - red, B and C - blue)

*Remove AC and BD from pairing and add AB and CD to pairing.
At each iteration common length of segments in pairing is decreased => this algorithm will be stop;
