A Math Gift For All

Kathryn Farley is my dear wife. We just celebrated Christmas together and then went off to London for a holiday.

Today I thought I would share a gift with you.

Kathryn and I exchange books for the holiday. We do not wrap them—our tradition, which she started years ago. I like doing this. Ken’s family re-uses wrapping paper year-to-year. I am pleased to see that there is a call to save wrapping on three gifts.

If every American family wrapped just 3 presents in reused materials, it would save enough paper to cover 45,000 football fields.

Kathryn gave me a wonderful collection of books. One of them is not the book: Computers, Rigidity, and Moduli: The Large-Scale Fractal Geometry of Riemannian Moduli Space. The author is Shmuel Weinberger a mathematician from the University of Chicago. I already had his book but finally took a look at it while browsing my other gifts. So it is a delayed gift, from a Christmas past.

The book is a combination of computer results, basic math results, and advanced math results. The last are a variety of topics that are well outside of my zone. I did like the book. Weinberger is a terrific writer, a terrific explainer, a gifted selector of topics. I was surprised to see that his book contained a puzzle that I had not thought about before. The puzzle is, like all good puzzles, easy to state—but hard to solve. At least for me. I did not see how to solve it. I hope you like it.

A Puzzle

Imagine that there are distinct points in the plane. No three points are collinear. Half of them, are labeled red and the other half are labelled green. Festive colors. Your job is to connect each red point with a unique green point by a straight line. That is easy, of course. But we hate when lines cross. So your job is more: Please select the lines so that the fewest ones cross.

Thus the problem is. Find the fewest line crossings possible. As usual we wish to know the answer as a function of . Is it ? Or ? What is the best possible in the worst case?

The artwork on the wall behind Kathryn suggests a possible arrangement, likewise the floor. The art object directly behind her is in 3D space which is not allowed—but this is a photograph so its points are projected onto a plane anyway. Again, it’s important that no three points are collinear.

There is a Best

For start we note that there is always a best. Each of red points can match one of green points. So there are only a finite number of possible matchings, namely

This shows that there is always a best answer; moreover, it can be found. But can be huge, so another part of the question is: Can you find the best answer fast? How about finding the best answer in polynomial time?

A Solution

The best answer is that the number of crossings is always at most

where is the constant

Here is a proof that this bound is correct. Suppose that you have selected the fewest number of line crossings. We will argue that there are at most line crossings. The plan is to show that we can descend—that is given a matching we can try and decrease the number of lines that cross.

Given any two red nodes and any two green nodes, we can define the operation swap by having them exchange partners. If their lines cross before the swap, then after the swap the lines will not cross. The following figure shows this:

Oops. I thought the idea was to define an operation so that the number of line crossing could always be decreased. Wait the argument does not work. In the above figure the switch increases the number of crossings.

There is a saving trick, however. Do not attempt to decrease the number of lines that cross. Instead decrease the total length of the lines selected. The above figure can be turned into a proof of a lemma that a swap of two crossing lines always decreases the sum of their lengths. The cool idea is that the swaps may actually increase the number of crossings, but they will always decrease the total length.

In the end the length is minimal and there are crossings. Thus

I cheated and used that

and so the constant is zero. Finally, no swap is ever undone—since the length always decreases—and so the process must finish within swaps.

Open Problems

Hope that you liked this puzzle. I think it shows that are sometimes methods that while simple may be hard to find. Is really the needed number of swaps? Are more than a linear number of swaps ever required?
Happy holidays to all.