Author |
Topic: Non-Intersecting Matching (Read 1128 times) |
|
william wu
wu::riddles Administrator
Gender: 
Posts: 1291
|
 |
Non-Intersecting Matching
« on: Dec 12th, 2007, 3:56pm » |
 Quote  Modify
|
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
|
|
 IP Logged |
[ wu ] : http://wuriddles.com / http://forums.wuriddles.com
|
|
|
Aryabhatta
Uberpuzzler
Gender:
Posts: 1321
|
|
Re: Non-Intersecting Matching
« Reply #1 on: Dec 12th, 2007, 4:06pm » |
Quote Modify
|
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):
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)
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print