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


quasi <quasi@null.set> wrote: > A Lurker wrote: >>quasi 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 subtlety. >>> >>>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. > > Well, it seem _closer_ to valid, but there's still an issue. > > In your inductive hypothesis you assume that for a smaller number > of points, _any_ choice of uppermost pair and lowermost pair can > be used to form a polygon. But in the joined polygon, your > argument only guarantees that there is one specific uppermost > pair and lowermost pair which works (namely, the ones actually > used). > > In other words, you don't correctly extend the full version > of your chosen inductive hypothesis.
I see I didn't handle the case of two possible pairs well. I should have phrased the statement so that an ngon is guaranteed where any uppermost pair is an edge, likewise any lowermost pair is an edge. I think that gives rigor.

