Hey there. Thanks for the time you're putting on reading this. I would appreciate it if you could kindly help me to solve this problem.
There are N blue points and N red points on the euclidean plane. We are to match every blue point with exactly one red point with a line segment such that no two line segments intersect.
Thank you in advance.
Let's find a convex hull. If there are both colors occurring in the hull then we can also find two neighbouring (adjacent) points with different color. Then we can match them and remove. Maybe it's not true that both colors occurring in the hull. Let's assume that vertices on the hull are all red. It turns out that then we are able to divide points into two smaller sets with one vertical cut.
Let's iterate over points in the order of increasing x. Let r and b denote the number of red and the number of blue points respectively. As we iterate over points we must keep value r - b. Because of the assumption about red points on the convex hull, we know that after the leftmost point we have r - b = 1 because the first point is red. And the last point is red so r - b = - 1 at the end. As we iterate we change r - b by + 1 or - 1 so in some moment we must get exactly 0. It allows us to divide a set of points into two separate sets and we can solve smaller problems recursively.
Very well said. That was super comprehensive. Thank you sir.
Straightforward implementation of this method gives O(n^2 log n) solution, and can be improved to O(n log^2 n) if using dynamic convex hull data structure: http://www.sciencedirect.com/science/article/pii/0022000085900650
Another approach to this problem is to find a matching between two point sets with minimal sum of distances between matched points. You can do that with either mincostmaxflow or hungarian algorithm in O(n^3). Now, suppose that two line segments a1-b1 and a2-b2 intersect in the optimal matching. But that means that they are two diagonals of convex quadrilateral a1-a2-b1-b2, so by triangle inequality, |a1-b2|+|a2-b1|<|a1-b1|+|a2-b2|, which contradicts with matching optimality.
Thanks. I was trying to solve it using the same approach but could not come up with the inequality you used in the end.