A matching problem in the plane

摘要

Suppose we are given 2n distinct points in the plane, no three of which are collinear, n of which are colored blue and the remaining n are colored red. The problem we consider is that of finding a one to one correspondence between red and blue points such that if we join every pair of corresponding points by a straight line segment, then no two of the resulting n segments intersect. We give an O(n log2 n) time algorithm for computing the desired one to one correspondence.