Given $2n$ points in the plane such that no three points lie on one line. Prove that it is possible to draw $n$ segments such that each segment connects a pair of these points and no two segments intersect.
So I know there is a solution that examines 4 points at a time and the two line segments, and if they intersect change the positioning of the 2 line segments for those points so they don't. It can be shown that the sum of the distance of the line segments monotonically decreases, so the process must terminate eventually, as there are only a finite number of possible configurations given the $2n$ points.
I was wondering if this can be done in the following way:
Lemma: Given $2n$ points in the plane, we can partition the plane into two sets $A_1,A_{n-1}$, where $A_1$ contains 2 points, $A_{n-1}$ contains the other $2n-2$ points, in a way such that the line connecting the two points in $A_1$ does not intersect any possible line segment formed by connecting two points of $A_{n-1}$ (basically, having $A_1,A_{n-1}$ disjoint).
Using this lemma, we first partion the $2n$ points into $A_1,A_{n-1}$. Then we could apply the lemma to $A_{n-1}$, partitioning the plane into sets $A_1,A_2,A_{n-2}$ such that $A_1,A_2$ contain 2 points each, with the segment connecting those two points not intersect any of the possible line segments formed by connecting two points of $A_{n-2}$, or each other.
Then we could repeat the lemma until we can finally partition the plane $P=A_1\cup A_2\cup A_3\cdots\cup A_{\frac{n}{2}}$, with all the $A_i$ disjoint.
The lemma seems kind of obvious (based on trying examples), just partition the plane using a line that separates two of the extreme points in the plane from the rest (e.g. the two "lowest" ones on the plane), however I do not know how to rigorously prove it.
Does anyone have any idea of how to prove this lemma? Also could someone check if this argument works?
Thanks!
Best Answer
This approach can work. If all the points would have different $y$ coordinates it is easy to separate the bottom two by a horizontal line. But if some points have the same $y$ coordinate we can just rotate the points around the origin by some angle.
Since there is only a finite number of pairs of points, and any given pair can have the same $y$ coordinate under only $2$ different angles of rotation. So there must be some angle such that all points end up with different $y$ coordinates.