Puzzle time - Red points and blue
-
if you can prove that you can find a single pair of red and blue points, in any given set of n, which is 'outside' the other points such that no line connecting any other pair could cross it, then you've solved the problem, because it becomes an iteration of that basic solution for successively smaller sets. Now imagine the minimal convex polyhedron containing all points. If there exists a pair of red and blue on adjacent vertices of that polyhedron, pair them and iterate the solution, because it would be impossible for any other line segment built from any other pair, to cross that one. If there does not exist such a pair, then the vertices are all one color. In this case, there must exist a line segment between a vertex and an interior point such that no other line segment could intersect with it*. Discard those two points and iterate.
I don't have an elegant proof of this yet.
-
I think I got it.
At first I thought one could get by with some kind of inductive argument, but a new point pair may completely alter the existing matching, so it's not obvious how to make that work.
But I think repeated iteration of a "repair" process will do the trick.
So, here's my proposal:
Take an arbitrary matching between the red and blue points. If it happens to have no intersection, we are done. Otherwise, pick two blue points B1 and B2 and two red points R1 and R2 with B1 matched to R1 and B2 matched to R2 such that the lines intersect. Change the matching such that B1 is now matched to R2 and B2 to R1. Repeat.
Why does this terminate?
Although one intersection is removed, new intersections with other lines may be introduced, so it is not necessarily the case that the process decreases the total number of intersections.
However, I do think it strictly decreases the total length of all line segments. The sum of the lengths of B1-R2 and B2-R1 must be strictly smaller than B1-R1 and B2-R2 (basically two applications of the triangle inequality).
That alone would still not prove termination, since there are strictly descending chains of infinite length in the real numbers (such as 1, 1/2, 1/3, 1/4, ...). However, there's only a finite number of distinct matchings, hence the process must necessarily termiante.
-
That’s exactly right. In their words:
SOLUTION: Let's first observe that any particular intersection can be avoided. If the line segment from red point R to blue point B crosses the segment from red point R' to blue point B', then the two segments are the diagonals of a quadrilateral; if you replace them with two opposite sides, namely the segments from R to B' and from R' to B, the crossing is eliminated.
But this operation (re-matching R with B', and R' with B) could create new intersections with other segments in the matching. So it's not clear that repeating this operation will ultimately eliminate all the intersections.
But notice that the operation doesn't merely eliminate an intersection; it shortens the sum of the lengths of the line segments. Why? Since the shortest distance from R to B' is the new straight segment, and not the route from R to the former intersection and thence to B', it follows that RB' + R'B < RB + R'B'.
Since every performance of the operation shortens the total length of the segments, and there are only finitely many (n factorial) matchings, you must eventually hit a matching with no intersections at all.
Another way to look at it: if you start with the matching that has the least possible total segment length, you've already got a matching with no intersections! -
Here's a question for you:
Could that argument be used for a "greedy" algorithm that constructs an intersection-free matching right away, without ever introducing intersections?
It would work as follows: Start with the empty matching. Now, always add to the existing matching the shortest possible additional red-blue edge that does not intersect with any of the existing edges.
Would that work?
edit: That question is too simple. It's too obvious that it doesn't work. Hm.
So let me sidestep the hard part like this:
Can you devise an algorithm that directly constructs the solution, without ever introducing intersections?
