Search All of the Math Forum:

Views expressed in these public forums are not endorsed by NCTM or The Math Forum.

Notice: We are no longer accepting new posts, but the forums will continue to be readable.

Topic: polygons thrugh a given set of points
Replies: 63   Last Post: Jun 14, 2014 4:29 AM

 Messages: [ Previous | Next ]
 Marnie Northington Posts: 1,251 Registered: 12/13/04
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 n-gon
>>>>>>>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
>>>>>>non-empty 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 straight-forward. 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 n-gon 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 y-coordinate 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 non-empty sets, and now without loss of generality let
>>>>p and q both lie on the x-axis. (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 non-collinearity 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 n-gon definition, and the
>>>>a1a2, b1b2 edges are guaranteed because any uppermost a1, a2
>>>>of the n-gon 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

>>
>>I see I didn't handle the case of two possible pairs well.
>>I should have phrased the statement so that an n-gon 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 n-1 to n, you have to start with a choice of arbitary
> pair (upper, lower, whatever your revised hypothesis is)
> from the n-point set, and only _then_ try to derive the claim
> for the n-point 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 n-point 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 n-point set induces an edge in the
n-gon, 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.

Date Subject Author
6/12/14 quasi
6/12/14 Marnie Northington
6/12/14 quasi
6/12/14 William Elliot
6/12/14 quasi
6/12/14 Marnie Northington
6/12/14 quasi
6/12/14 Marnie Northington
6/12/14 quasi
6/12/14 Marnie Northington
6/12/14 quasi
6/12/14 Timothy Murphy
6/12/14 quasi
6/12/14 Peter Percival
6/12/14 quasi
6/13/14 Peter Percival
6/13/14 Port563
6/13/14 Peter Percival
6/13/14 Port563
6/12/14 Port563
6/12/14 quasi
6/12/14 Port563
6/12/14 quasi
6/12/14 quasi
6/13/14 Port563
6/13/14 quasi
6/13/14 Port563
6/13/14 quasi
6/13/14 Port563
6/13/14 scattered
6/12/14 quasi
6/13/14 Port563
6/12/14 David Hartley
6/12/14 quasi
6/12/14 quasi
6/13/14 Port563
6/13/14 David Hartley
6/13/14 Peter Percival
6/13/14 Port563
6/13/14 quasi
6/13/14 Port563
6/13/14 quasi
6/13/14 quasi
6/13/14 Port563
6/13/14 Peter Percival
6/13/14 quasi
6/12/14 Bart Goddard
6/12/14 scattered
6/12/14 scattered
6/12/14 quasi
6/12/14 David Hartley
6/12/14 quasi
6/12/14 Richard Tobin
6/12/14 quasi
6/13/14 William Elliot
6/13/14 quasi
6/13/14 William Elliot
6/13/14 quasi
6/13/14 David Hartley
6/13/14 quasi
6/13/14 Phil Carmody
6/13/14 Phil Carmody
6/14/14 quasi
6/14/14 quasi