… 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.

### Like this:

Like Loading...

*Related*

shantanu

Oct 29, 2010@ 17:50:35I had been trying to solve this problem since a day. You have provided such a simple and elegant solution. Marvelous !!!!

shantanu

Oct 29, 2010@ 20:15:47however, the difference (blue – red) should be 1, to get the line we need.

(assuming we have counted the first and the last blue nodes from the source)

Please correct me if i am wrong.

goodwind89

Oct 30, 2010@ 01:34:21Hi shantanu,

It depends on whether you count the origin point you used to calculate the angles for sorting. If we don’t count it, then yes, the difference should be 1 so that the latest line can balance the set. I forgot to note that each time the difference is increased/decreased by exactly 1, so we can find the exact balance line.

There’s another proof I found later for this:

https://goodwind89.wordpress.com/2010/09/18/problems-33-3-cont/