Today I found another solution to this. We randomly matched red with blue points. We then detect crossing, and switch the 2 pairs creating that crossing. We knew that this process would finally stop. In fact, it’s usually faster than the algorithm provided in the book. While I cannot bound the number of swapping operations, we can still prove that the process finally stop, e.g. although it may create new crossings after each operation, the algorithm finally stops with no crossing.

Note that the operation reduce the total length of two segments connecting 2 red and 2 blue points. Hence, each operation happening will make the total length decreasing gradually. We will finally reach a minimal total length with no possible operation, in other words, there is no crossing at the point.

To make it more concrete that a minimal total length will be reached, we note that the number of possible total lengths is finite, although many.

Advertisements