Pairing off points: More surprising trickiness

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

aleph_one
Posts: 140
Joined: Sun Oct 28, 2007 4:27 pm UTC
Location: Cambridge, MA

Pairing off points: More surprising trickiness

Postby aleph_one » Sat Aug 07, 2010 10:37 pm UTC

Problem wrote: There are N red points and N blue points on a plane in general position, meaning that no three are on a line. Show that there is a way to pair off red and blue points so that the line segments that connect each pair don't intersect.

I recall seeing this in a book of olympiad-style problems.
Last edited by aleph_one on Sun Aug 08, 2010 12:18 am UTC, edited 1 time in total.

User avatar
Mike_Bson
Posts: 252
Joined: Mon Jul 12, 2010 12:00 pm UTC

Re: Paring off points: More surprising trickiness

Postby Mike_Bson » Sat Aug 07, 2010 10:42 pm UTC

Each pair? So does this mean that N will always be even, so you can have a certain numbers of ''pairs''?

aleph_one
Posts: 140
Joined: Sun Oct 28, 2007 4:27 pm UTC
Location: Cambridge, MA

Re: Paring off points: More surprising trickiness

Postby aleph_one » Sat Aug 07, 2010 10:45 pm UTC

No, there are 2N points total, N red and N blue, and there are N line segments, each with a red endpoint and a blue endpoint.

User avatar
jaap
Posts: 2094
Joined: Fri Jul 06, 2007 7:06 am UTC
Contact:

Re: Paring off points: More surprising trickiness

Postby jaap » Sat Aug 07, 2010 11:09 pm UTC

I found this one easy, but only because I had seen something very similar before in one of Edsger Dijkstra's notes, though I don't know which one.
Spoiler:
a. Start with any pairing, which is likely to have intersecting line segments.
b. If any pair of segments intersects, pair those four endpoints the other way to uncross them.
c. repeat b until no more intersections exist.

Note that although the uncrossing in b removes one intersection point, it may introduce more since the new line segments may cross some of the others.
To prove that the above procedure eventually finishes, consider the total length of all the line segments. Each uncrossing decreases that length. There are only a finite number of possible pairings (N! in fact), so there are only a finite number of values that the total length could have, so only a finite number of uncrossings are possible/needed to reach a pairing with no intersections.

User avatar
OverBored
Posts: 284
Joined: Mon Dec 10, 2007 7:39 pm UTC

Re: Paring off points: More surprising trickiness

Postby OverBored » Sat Aug 07, 2010 11:24 pm UTC

Spoiler:
My approach so far:
Pick an arbitrary red point. Draw the line (not just the segment) through each blue point sequentially until there are an equal number of blues as reds on each side of the line. It is late, but I think pigeonhole proves that there always exists one blue point that satisfies this. Then just repeat on the two new sets of points.
G4!!

Grob FTW,

Hello. Smithers. You're. Quite good. At. Turning. Me. On.

User avatar
Mike_Bson
Posts: 252
Joined: Mon Jul 12, 2010 12:00 pm UTC

Re: Paring off points: More surprising trickiness

Postby Mike_Bson » Sat Aug 07, 2010 11:26 pm UTC

jaap wrote:I found this one easy, but only because I had seen something very similar before in one of Edsger Dijkstra's notes, though I don't know which one.
Spoiler:
a. Start with any pairing, which is likely to have intersecting line segments.
b. If any pair of segments intersects, pair those four endpoints the other way to uncross them.
c. repeat b until no more intersections exist.

Note that although the uncrossing in b removes one intersection point, it may introduce more since the new line segments may cross some of the others.
To prove that the above procedure eventually finishes, consider the total length of all the line segments. Each uncrossing decreases that length. There are only a finite number of possible pairings (N! in fact), so there are only a finite number of values that the total length could have, so only a finite number of uncrossings are possible/needed to reach a pairing with no intersections.

I just must add:

Spoiler:
If a line intersects more than two lines, then you should at first ignore all intersections but one, then go to the next intersection as needed.

User avatar
antonfire
Posts: 1772
Joined: Thu Apr 05, 2007 7:31 pm UTC

Re: Pairing off points: More surprising trickiness

Postby antonfire » Sun Aug 08, 2010 1:59 am UTC

You could also
Spoiler:
apply a divide and conquer strategy.

Start with a generic line and rotate it, keeping track of the number of red and blue points to one side. If one number is bigger than the other, rotating it 180 degrees switches this relationship. Since they only change by one point at a time, at some point in between they must be the same. Now recursively solve the problem in the smaller two cases.

By rotating the line carefully (say, keeping an almost constant number of red points to one side) you can even arrange it so that you split the points evenly.
Jerry Bona wrote:The Axiom of Choice is obviously true; the Well Ordering Principle is obviously false; and who can tell about Zorn's Lemma?

User avatar
Talith
Proved the Goldbach Conjecture
Posts: 848
Joined: Sat Nov 29, 2008 1:28 am UTC
Location: Manchester - UK

Re: Pairing off points: More surprising trickiness

Postby Talith » Sun Aug 08, 2010 2:55 am UTC

antonfire wrote:You could also
Spoiler:
apply a divide and conquer strategy.

Start with a generic line and rotate it, keeping track of the number of red and blue points to one side. If one number is bigger than the other, rotating it 180 degrees switches this relationship. Since they only change by one point at a time, at some point in between they must be the same. Now recursively solve the problem in the smaller two cases.

By rotating the line carefully (say, keeping an almost constant number of red points to one side) you can even arrange it so that you split the points evenly.

Spoiler:
Gotta love the Ham sandwhich theorem

User avatar
Torn Apart By Dingos
Posts: 817
Joined: Thu Aug 03, 2006 2:27 am UTC

Re: Pairing off points: More surprising trickiness

Postby Torn Apart By Dingos » Sun Aug 08, 2010 10:40 pm UTC

antonfire & Talith: Very elegant variant of OverBored's solution.

aleph_one
Posts: 140
Joined: Sun Oct 28, 2007 4:27 pm UTC
Location: Cambridge, MA

Re: Pairing off points: More surprising trickiness

Postby aleph_one » Mon Aug 09, 2010 1:20 am UTC

Torn Apart By Dingos wrote:antonfire & Talith: Very elegant variant of OverBored's solution.

I agree, these are great! I'd only seen jaap's solution before, and was going to ask if there was a computationally efficient version, but you've already answered this. :)

User avatar
Talith
Proved the Goldbach Conjecture
Posts: 848
Joined: Sat Nov 29, 2008 1:28 am UTC
Location: Manchester - UK

Re: Pairing off points: More surprising trickiness

Postby Talith » Mon Aug 09, 2010 1:41 am UTC

I wouldn't say it's computationally efficient because the theorem only implies that bisecting lines exist, actually finding the lines is another matter and could even be inefficient if points are so close to being on the same line that you have to move the line exceptionally slowly or at least at a very fine resolving level to make sure you don't 'miss points' as you're turning. As far as existence theorems go however, it's one of my favourite (especially the higher dimensional generalisation).

letterX
Posts: 535
Joined: Fri Feb 22, 2008 4:00 am UTC
Location: Ithaca, NY

Re: Pairing off points: More surprising trickiness

Postby letterX » Mon Aug 09, 2010 5:44 pm UTC

Except that you only care about lines from a red point to a blue point. So you only need to check at most N possible lines (and then for each line check that the number of red and blue points on each side of the line is balanced, for a total of N2 work at each level of recursion). So, reasonably efficient. Certainly more so than the jaap's (though I do like his for being a very simple existence proof).

User avatar
antonfire
Posts: 1772
Joined: Thu Apr 05, 2007 7:31 pm UTC

Re: Pairing off points: More surprising trickiness

Postby antonfire » Mon Aug 09, 2010 8:20 pm UTC

It's not clear to me what the computational efficiency of jaap's solution even is.
Jerry Bona wrote:The Axiom of Choice is obviously true; the Well Ordering Principle is obviously false; and who can tell about Zorn's Lemma?

Syrin
Posts: 290
Joined: Thu May 24, 2007 7:10 pm UTC
Location: Ontario, Canadia

Re: Pairing off points: More surprising trickiness

Postby Syrin » Mon Aug 09, 2010 8:24 pm UTC

antonfire wrote:It's not clear to me what the computational efficiency of jaap's solution even is.

Fast.

++$_
Mo' Money
Posts: 2370
Joined: Thu Nov 01, 2007 4:06 am UTC

Re: Pairing off points: More surprising trickiness

Postby ++$_ » Mon Aug 09, 2010 8:27 pm UTC

Syrin wrote:
antonfire wrote:It's not clear to me what the computational efficiency of jaap's solution even is.

Fast.
Proof?

User avatar
WarDaft
Posts: 1583
Joined: Thu Jul 30, 2009 3:16 pm UTC

Re: Pairing off points: More surprising trickiness

Postby WarDaft » Tue Aug 10, 2010 4:51 pm UTC

++$_ wrote:Proof?

Spoiler:
Unless there is another optimization, it very well may not be. I have no idea how many passes it would even take to get from an average pairing to a non-intersecting pairing, but each one might require an O(n Log n) task of actually finding an intersection.

Depending on how long it takes, there might be a shortcut by starting with a pairing that has a low total line segment length (as each pass reduces length, there would be fewer possible reductions necessary)


Hmm, finding the lowest total line segment length would be sufficient too, with no passes of intersection checking at all - if there was an intersection, removing it could reduce the total length.
All Shadow priest spells that deal Fire damage now appear green.
Big freaky cereal boxes of death.

User avatar
jestingrabbit
Factoids are just Datas that haven't grown up yet
Posts: 5967
Joined: Tue Nov 28, 2006 9:50 pm UTC
Location: Sydney

Re: Pairing off points: More surprising trickiness

Postby jestingrabbit » Tue Aug 10, 2010 7:37 pm UTC

WarDaft wrote:
++$_ wrote:Proof?

Spoiler:
Unless there is another optimization, it very well may not be. I have no idea how many passes it would even take to get from an average pairing to a non-intersecting pairing, but each one might require an O(n Log n) task of actually finding an intersection.

Depending on how long it takes, there might be a shortcut by starting with a pairing that has a low total line segment length (as each pass reduces length, there would be fewer possible reductions necessary)


Hmm, finding the lowest total line segment length would be sufficient too, with no passes of intersection checking at all - if there was an intersection, removing it could reduce the total length.


Spoiler:
Even to check every pair of paths for a collision is going to be O(n2). I expect that's pretty much put the kibosh on jaap's algorithm being efficient compared to the divide and conquer approach of antonfire.
ameretrifle wrote:Magic space feudalism is therefore a viable idea.

achan1058
Posts: 1783
Joined: Sun Nov 30, 2008 9:50 pm UTC

Re: Pairing off points: More surprising trickiness

Postby achan1058 » Wed Aug 11, 2010 8:21 pm UTC

jestingrabbit wrote:
Spoiler:
Even to check every pair of paths for a collision is going to be O(n2). I expect that's pretty much put the kibosh on jaap's algorithm being efficient compared to the divide and conquer approach of antonfire.
Spoiler:
O(n log n) if you do plane sweep, but still. The wiki pages says Ham and Sandwich can be done O(n) per iteration, so this gives an O(n log n) total run time algorithm.

DavCrav
Posts: 251
Joined: Tue Aug 12, 2008 3:04 pm UTC
Location: Oxford, UK

Re: Pairing off points: More surprising trickiness

Postby DavCrav » Fri Aug 13, 2010 12:43 pm UTC

This question was asked, with a few extra stages, as part of an interview question for 17-year olds at St John's Oxford. With some prodding, the idea is you can solve this in about ten-fifteen minutes. :)


Return to “Mathematics”

Who is online

Users browsing this forum: No registered users and 8 guests