wu :: forums - Print Page


    
      
        wu :: forums
        (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi)
      

        riddles >> hard >> Non-Intersecting Matching
        
(Message started by: william wu on Dec 12^th, 2007, 3:56pm)

Title: Non-Intersecting Matching
Post by william wu on Dec 12^th, 2007, 3:56pm

There are n red points and n blue points in the two-dimensional plane. The 2n points are distinct, and no three points are collinear.

Define a matching to be a set of n line segments, each of which have endpoints of different colors, and none of which share an endpoint with a different line segment.

Prove there exists a matching that does not have any intersecting line segments.

Source: Putnam 1979

Title: Re: Non-Intersecting Matching
Post by Aryabhatta on Dec 12^th, 2007, 4:06pm

I think this has appeared before in the CS section.

The matching can even be found in O(nlogn) time.

Here is an existence proof (which is not good for an efficient algorithm):
[hide]
Of all n! possible matchings (intersecting or not), consider the matching with the least sum of line segments of the matching. This has to be non-intersecting. (As uncrossing two intersecting line segments reduces the total length)
[/hide]