
Re: polygons through a given set of points
Posted:
Jun 12, 2014 12:47 PM


quasi <quasi@null.set> wrote: > A Lurker wrote: >>quasi 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. > > I don't think so. > > The problem is that in order for your induction to continue > for n1 to n, you have to start with a choice of arbitary > pair (upper, lower, whatever your revised hypothesis is) > from the npoint set, and only _then_ try to derive the claim > for the npoint set from the assumed truth of the claim for > sets with fewer points. > > On that basic point, your proof fails.
I must say I still don't see it: any arbitrary upper/lower pair I pick from the npoint set must also be an upper/lower pair for the relevant smaller set. The revised hypothesis gives that /any/ upper/lower pair induces an edge in the polygon, so that arbitrary pair is an edge in the smaller polygon, and therefore an edge in the larger polygon. So any arbitrary upper/lower pair in the npoint set induces an edge in the ngon, as I wanted.
No need to reply, though. I'm quite confident that you're correct on this, I'll just have to find where I've made an assumption somewhere in the above, I'll just search until I've found it. This is too trivial of a matter to continue taking up your time  it has simply served as a lesson in rigor to me.

