Given n points in the plane, no three collinear, prove that we can label them Pi so that P1P2P3 ... Pn is a simple closed polygon (with no edge intersecting any other edge except at its endpoints).
Solution
Take arbitrary x, y axes. Take P to be the point with the smallest x-coordinate, or if there are two such, the one with the smaller y-coordinate. Take Q to be the point with the largest x-coordinate, or if there are two such the one with the smaller y-coordinate. Join P to Q by a path p along the lower part of the convex hull of the points (so that all other points are above the path).
Now order the remaining points not in the path according to the size of their x-coordinate (with the largest first). Continue the path from Q back to P by taking the remaining points in this order. We can never intersect the existing path p without going outside the convex hull and we cannot intersect the later part of the path because it has smaller x-coordinate.
Comment. It is tempting to argue by induction. Take a path through the first n. Then given another point P, we can always find two earlier points Q and R, so that PQ and PR do not intersect the n-path. Then replace the segment QR by QP and PR. Unfortunately, this is false. It is not too hard to find cases where we cannot find such Q, R.
© John Scholes
jscholes@kalva.demon.co.uk
25 Jan 2002