5
$\begingroup$

Suppose we are given $2N$ points in the plane (we may assume that no $3$ are collinear). Assume that $N$ of these points are colored red, and $N$ points are colored blue. Can we match off the points into $N$ red/blue pairs with straight lines connecting these pairs, so that none of the lines we draw intersect? If this matching exists, can we find it by an algorithm?

$\endgroup$
  • $\begingroup$ If the matching exists we can definitely find it by looking at every possible matching. Obviously this will not be an efficient algorithm. Are there any other constraints on your algorithm? $\endgroup$ – Sean English Jan 10 '16 at 21:44
  • 1
    $\begingroup$ Do the lines end at the points, or are they extended ? $\endgroup$ – true blue anil Jan 11 '16 at 12:13
2
$\begingroup$

Yes, such a matching always exist.

The algorithm works recursively. You either

1) find a pair of red and blue point R and B such that the number of red points and blue points on the left side of the vector RB is the same. You match RB, and then you recursively find the matchings for all the points on each side of the vector separately.

or

2) find any line that divides the plane into two non-empty planes such that the number of red and blue points on each side of the line is equal. You recursively find matchings on these points on each side of the line separately.

We need to prove that either one of these two cases must happen. Suppose case 1) does not exists. Consider any pair of node R and B. Consider the vector RB. RB divides the remaining points into those that are on the left side of the vector, and those on the right side of the vector. Given a vector RB, let RB_left be the the number of red points on the left of RB substracted by the number of blue points on the left of RB. Since case 1 does not exist, RB_left is not zero. We also have RB_left = -BR_left. Now consider rotating the vector X=RB using until it eventually becomes BR, and consider what happens to X_left. Each time the vector is collinear with a point, then X_left will increase or decrease by 1 point. Since BR_left = -RB_right, there must be some time in which X_left = 0.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy