Given 5 coplanar points with no three collinear, prove that there must be a subset of 4 points that form a convex quadrilateral.

This proof is a little inside-out compared to Bractals'.

Choose three of the points such that the triagle they form contains none of the other points.  This is always possible as any interior point can be eliminated from within a chosen triangle by choosing a different one with the interior point as one of the vertices, and this can be repeated until there are no interior points left among the original five.

Extend the sides of the formed triangle to full (infinite) lines.  This produces three angles that are vertical to the angles of the triangle, and divides the space outside the triangle into six subsets: three that lie within these vertical angles and three that lie between pairs of these vertical angles.

If one or both of the two points left out of the triangle is not within any of the vertical angles, then eliminate the nearest side of the triangle and connect its end points with the given outside point. The result is a convex quadrilateral.

If, however, both of the remaining points are within one or two of the vertical angles, then:

If they are within two different of the vertical angles, then these two points with the points on the triangle at the vertices of the two vertical angles, form a convex quadrilateral.

If the two outer points are within the same vertical angle, then the line connecting these two points will separate the triangle into two parts, with two points on one side and one point on the other.  The two points that are on one side, together with the two outer points, then form a convex quadrilateral.

Posted by Charlie on 2009-10-06 11:22:51