… in CLRS.

This problem is interesting. I have encountered it 3 times, each time it took me a week, before finally managed to solve it in my solution book. The problem statement reduces to sth like this: given n red points and n blue points with no colinear triplets, is there a way to match a red with a blue such that no segment crosses?

We provide an algorithm that matches a red point with a blue point, drawing a line through them, and then recursively solve for each half-plane.

To find the suitable pair such that it can separate the rest into two halves where each half is balanced between red and blue, we proceed as follow:

Take the bottom point as in Graham scan, and sort the other points. Without loss of generality, let the origin point be blue. If the first point in the scan is red, we just connect them. Same goes for the last point in the scan.

Now we know already 3 points to be blue. We know that the number of red points is the same as the number of blue points. We follow the scan, and keep track of the difference between the number of scanned blue points and the scanned red points, and stop only when we reach -1. When we stop, that should be a red point we just scanned (because we have always been greater than 0, so if we reach -1, it must have been a decrease right before that). So we just connect it with the origin.