
Re: polygons through a given set of points
Posted:
Jun 12, 2014 3:10 AM


quasi <quasi@null.set> wrote: > A Lurker wrote: >>quasi wrote: >>> >>>Let n be an integer, n >= 3. For a set of n points in the >>>plane, no 3 collinear, is there always at least one ngon >>>having those points as vertices? >> >>Yes. For n = 3 this certainly holds. >> >>For n > 3, choose two points p, q in the set such that the >>line between them divides the remaining n  2 points into two >>nonempty sets. For both such sets, build a smaller polygon >>out of {that set's elements} U {p, q} by induction, then join >>the two such polygons by equating the mutual pq edge. Since no >>three points are collinear, no two remaining edges are collinear, >>so it is easily seen that there are, in fact, n edges. >> >>This seems too straightforward. Have I missed a catch? > > I think you've missed a subtletly. > > In your use of the inductive hypothesis, how do you know the > two smaller polygons can each be forced to have the edge pq?
Indeed, that is missing. I think that can be corrected by imposing a constraint or two on the polygon created.
Let n be an integer, n >= 3. For a set of n points in the plane, no 3 collinear, with a1, a2 two uppermost* points and b1, b2 two lowermost points (perhaps with some aj = bk in the case n = 3), there is at least one ngon having these points as vertices, and also having a1a2 and b1b2 as edges.
* I'll say a1, a2 are uppermost if there is no other point with a ycoordinate strictly greater than both a1's and a2's.
As before: for n = 3 this is clear.
For n > 3, choose p and q to divide the remaining points into nonempty sets, and now without loss of generality let p and q both lie on the xaxis. (A polygon can be constructed from these points iff it can be constructed a rotation + translation of these points.) Then inductively, two smaller polygons can be created, and by noncollinearity p, q must be the lowermost points of one polygon, the uppermost points of the other. Then the two polygons can be joined along pq. Collinearity takes care of the ngon definition, and the a1a2, b1b2 edges are guaranteed because any uppermost a1, a2 of the ngon must have been uppermost points of (and present in) the upper, smaller polygon.
Hopefully I haven't muddled that up too much.

