Pairing points

[bonanova]

Take a red pen and touch a sheet of paper with it at n randomly chosen points.

Now add n random points with a blue pen, for a total of 2n points, no three of

which lie on a straight line.

Is it possible in every case to pair the points so that no two of the n lines that

join each red point with its corresponding blue point will cross?

[k-man]

It's easy to show with n=2 that it's not possible with lines, so I will assume that you meant line segments connecting a red and a blue points.

There are two methods that can be applied in combination to solve this problem. Let's call them "Convex hull" method and "Divide and Conquer" method. Let me first describe each method and then show why they will always work together.

Convex hull

Take all 2n points and create a convex hull around them. If the convex hull contains both red and blue points, choose any red/blue segments of the convex hull and draw those lines. You just reduced the problem to a smaller set. Those points can be eliminated from any further consideration. We can now create a new convex hull excluding those points and continue until either we solve the problem or we have a convex hull containing only the points of one color.

Divide and conquer

The principle in this method is to pick a pair of red/blue points in such a way that a straight line drawn through these points would split the set of points into 2 subsets each containing equal number of red and blue points. This may not always be possible, but it's always possible when the convex hull is of one color.

Let's say our convex hull contains all red points. Let's choose any one of these points. Now imagine a straight line originating from that point and rotating clockwise like a radar starting from the left convex hull neighbor. Since no three points are collinear, as this line rotates, it will encounter one point at a time either red or blue and we'll be keeping score. The first and last points will be red. The starting point we picked is also red, so the middle area contains 3 more blue points than the red ones. At some point when the line encounters a blue point the score will be even, which means we found a red/blue line dividing the set into 2 subsets each containing equal number of red and blue points. Now we can draw that line and apply convex hull method to each of the subsets.

[bonanova]

Sorry.

That was a nice discussion, and I wasn't very clear.

Begin with n red points and n blue points randomly intermingled.

Can n (straight) line (segments) each join a red point to a blue point?

Once drawn they remain in place.

They may not cross.

Connect any red point to a blue point and coalesce them to a single point.

Do this n times. Coalescing is of no consequence since later curved lines can avoid the coalesced point with no greater ease than to avoid the curved line itself.

[k-man]

Maybe I wasn't clear, but my solution doesn't involve any curved lines. All straight line segments connecting a blue dot with a red dot and they don't cross.

[k-man]

Convex hull method identifies pairs of red/blue points on the outside of the set, so those line segments cannot cross any other line segments. As long as there are points of both colors on the convex hull, we can continue to use this method.

If convex hull contains only red points, then Divide & Conquer method will always find such blue point that splits the set into 2 subsets (see gray line in step 4) each containing equal number of red and blue points. Each subset is then solved independently of another.

[bonanova]

Nice.

I misinterpreted "points contained by the hull" as "points within the hull."

You were saying perimeter; I thought interior.

BTW there is a very simple idea that does the job

The set of connecting line segments with minimal total length contains no crossings?

.

[k-man]

The set of connecting line segments with least total length contains no crossings?

.

Suppose that you have a solution that is the least total length and it contains crossing segments. The 4 points involved in a crossing form a convex quadrilateral and the lines are its diagonals. The sum of the diagonals is always greater than the sum of the 2 opposing sides of a quadrilateral, so if the diagonals are replaced by the 2 opposing sides (connecting red/blue) then the total length would be reduced. However, this could introduce new crossings. We can continue to resolve these crossings in the same manner, but I'm not sure if this process converges or it can be cyclic.

I'll think of it some more...

[bonanova]

The set of connecting line segments with least total length contains no crossings?

.

Suppose that you have a solution that is the least total length and it contains crossing segments. The 4 points involved in a crossing form a convex quadrilateral and the lines are its diagonals. The sum of the diagonals is always greater than the sum of the 2 opposing sides of a quadrilateral, so if the diagonals are replaced by the 2 opposing sides (connecting red/blue) then the total length would be reduced. However, this could introduce new crossings. We can continue to resolve these crossings in the same manner, but I'm not sure if this process converges or it can be cyclic.

I'll think of it some more...

That's it. I don't believe it's cyclic.

BTW your solution constructs a non-crossing pairing.

This observation proves that one exists, which is all that is asked, but does not construct it.