Planar Configuration of Line Segments


I got this problem from Rustan Leino, who was told it by Radu Grigore. Rustan may have heard it 20 years earlier from Jan van de Snepscheut. I modified it slightly.

I solved it and wrote up my solution.


Given an even number of distinct points on a plane, can you partition the points into pairs and connect the two points of each pair with a single straight line segment such that the line segments don't overlap?

Solution     Reveal