farnasirim's blog

By farnasirim, history, 6 years ago, In English

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.

  • Vote: I like it
  • +29
  • Vote: I do not like it

6 years ago, # |
  Vote: I like it +68 Vote: I do not like it

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.

6 years ago, # |
  Vote: I like it +77 Vote: I do not like it

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.

  • »
    6 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    Thanks. I was trying to solve it using the same approach but could not come up with the inequality you used in the end.