4

Given an even number of points in general positions on the plane (that is, no three points co-linear), can you partition the points into pairs and connect the two points of each pair with a single straight line such that the straight lines do not overlap?

user106448
  • 301
  • Meaning that no two straight lines overlap? Or there is no point at which all of the lines cross simultaneously? – Jack M Nov 08 '13 at 21:17

2 Answers2

2

Suppose the result is true for $2n$ points. We show it is true for $2(n+1)$ points.

Let $S$ be a set of $2(n+1)$ points. Draw a straight line $\ell$ such that all points of $S$ are on one side of the line, and none is on the line.

Move the line $\ell$ parallel to itself, slowly towards $S$. After a while, it just meets $S$, say at point $P$. If it also meets $S$ at another point $Q$, be happy. Else rotate the line slowly about $P$ until it first meets $S$ at another point $Q$.

Join $PQ$ by a line segment. By the induction hypothesis, the rest of the points of $S$ can be split into pairs, and the pairs joined by non-intersecting line segments. By the choice of $P$ and $Q$, these line segments do not meet $PQ$.

Remark: In fewer words, the convex hull of $S$ is a polygon. We can let $P$ and $Q$ be any two consecutive vertices of the polygon.

André Nicolas
  • 507,029
  • Or choose the line $\ell$ so it's not parallel to any line determined by two points in $S$. The moving line crosses the points of $S$ one by one. Stop at any point where there are an even (nonzero) number of points on either side. – bof Nov 08 '13 at 22:06
  • @bof: That is a nice way of doing the induction. – André Nicolas Nov 08 '13 at 22:11
  • Mathematical induction is hardly needed here. Perhaps the simplest way to present the proof: Rotate $S$ so that no two points lie on a vertical line, index the points from left to right as $P_1,\dots,P_n$, and draw the segments $P_1P_2,P_3P_4,\dots,P_{2n-1}P_{2n}$. The same argument shows that a finite set of points in $R^n$, if its cardinality is divisible by $k$, can be partitioned into $k$-element set whose convex hulls are pairwise disjoint. – bof Nov 08 '13 at 23:32
1

Yes. There are a finite number of ways to partition the points into pairs. Choose a partition which minimizes the sum of the squares of the lengths of the resulting line segments. If two of the segments intersect, it's clear from the parallelogram law that the sum could be made smaller. ("General position" is irrelevant for this; all you need is an even number of distinct points in the plane.)

bof
  • 6,156