I have to write an algorithm that given n blue and n red points in a 2D space will connect red and blue points with lines without any of them intersecting. In other words, I want to have n disjoint pairs (each consisting of a blue and a red point). When I connect the points in each pair the connecting line segments cannot intersect. The algorithm has to run in O(n^2*logn) time.
After a lot of reading I decided to go with the following idea: recursively divide the plane in halfs so that there is always the same number of blue and red points on each side until there is only one red and one blue point left - these can be connected with a line. Such divide and conquer approach will give that logarithmic complexity that I was looking for.
The question was how to divide a plane with a line so that there is an equal number of blue and red points on each side. Again, after some reading, I found the ham sandwich algorithm which is supposed to do exactly what I'm looking for in linear time. I am, however, having hard time understanding how it works exactly and translating it into code. This and this link were the most helpful to me but they only describe in general the steps of this algorithm and lack some implementation details.
The major question is: is my approach correct? If so, can you explain to me the algorithm of ham sandwich or maybe provide some additional materials/pseudocode?
