Drexel dragonThe Math ForumDonate to the Math Forum



Search All of the Math Forum:

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


Math Forum » Discussions » sci.math.* » sci.math

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

Advanced Search

Back to Topic List Back to Topic List Jump to Tree View Jump to Tree View   Messages: [ Previous | Next ]
Marnie Northington

Posts: 712
Registered: 12/13/04
Re: polygons through a given set of points
Posted: Jun 12, 2014 12:47 PM
  Click to see the message monospaced in plain text Plain Text   Click to reply to this topic Reply

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
>>>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 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
Read polygons thrugh a given set of points
quasi
6/12/14
Read Re: polygons thrugh a given set of points
Marnie Northington
6/12/14
Read Re: polygons through a given set of points
quasi
6/12/14
Read Re: polygons through a given set of points
William Elliot
6/12/14
Read Re: polygons through a given set of points
quasi
6/12/14
Read Re: polygons through a given set of points
Marnie Northington
6/12/14
Read Re: polygons through a given set of points
quasi
6/12/14
Read Re: polygons through a given set of points
Marnie Northington
6/12/14
Read Re: polygons through a given set of points
quasi
6/12/14
Read Re: polygons through a given set of points
Marnie Northington
6/12/14
Read Re: polygons through a given set of points
quasi
6/12/14
Read Re: polygons thrugh a given set of points
Timothy Murphy
6/12/14
Read Re: polygons thrugh a given set of points
quasi
6/12/14
Read Re: polygons thrugh a given set of points
Peter Percival
6/12/14
Read Re: polygons thrugh a given set of points
quasi
6/13/14
Read Re: polygons thrugh a given set of points
Peter Percival
6/13/14
Read Re: polygons thrugh a given set of points
Port563
6/13/14
Read Re: polygons thrugh a given set of points
Peter Percival
6/13/14
Read Re: polygons thrugh a given set of points
Port563
6/12/14
Read Re: polygons thrugh a given set of points
Port563
6/12/14
Read Re: polygons thrugh a given set of points
quasi
6/12/14
Read Re: polygons thrugh a given set of points
Port563
6/12/14
Read Re: polygons thrugh a given set of points
quasi
6/12/14
Read Re: polygons thrugh a given set of points
quasi
6/13/14
Read Re: polygons thrugh a given set of points
Port563
6/13/14
Read Re: polygons thrugh a given set of points
quasi
6/13/14
Read Re: polygons thrugh a given set of points
Port563
6/13/14
Read Re: polygons thrugh a given set of points
quasi
6/13/14
Read Re: polygons thrugh a given set of points
Port563
6/13/14
Read Re: polygons thrugh a given set of points
scattered
6/12/14
Read Re: polygons thrugh a given set of points
quasi
6/13/14
Read Re: polygons thrugh a given set of points
Port563
6/12/14
Read Re: polygons thrugh a given set of points
David Hartley
6/12/14
Read Re: polygons thrugh a given set of points
quasi
6/12/14
Read Re: polygons thrugh a given set of points
quasi
6/13/14
Read Re: polygons thrugh a given set of points
Port563
6/13/14
Read Re: polygons thrugh a given set of points
David Hartley
6/13/14
Read Re: polygons thrugh a given set of points
Peter Percival
6/13/14
Read Re: polygons thrugh a given set of points
Port563
6/13/14
Read Re: polygons thrugh a given set of points
quasi
6/13/14
Read Re: polygons thrugh a given set of points
Port563
6/13/14
Read Re: polygons thrugh a given set of points
quasi
6/13/14
Read Re: polygons thrugh a given set of points
quasi
6/13/14
Read Re: polygons thrugh a given set of points
Port563
6/13/14
Read Re: polygons thrugh a given set of points
Peter Percival
6/13/14
Read Re: polygons thrugh a given set of points
quasi
6/12/14
Read Re: polygons thrugh a given set of points
Bart Goddard
6/12/14
Read Re: polygons thrugh a given set of points
scattered
6/12/14
Read Re: polygons thrugh a given set of points
scattered
6/12/14
Read Re: polygons thrugh a given set of points
quasi
6/12/14
Read Re: polygons thrugh a given set of points
David Hartley
6/12/14
Read Re: polygons thrugh a given set of points
quasi
6/12/14
Read Re: polygons thrugh a given set of points
Richard Tobin
6/12/14
Read Re: polygons thrugh a given set of points
quasi
6/13/14
Read Re: polygons thrugh a given set of points
William Elliot
6/13/14
Read Re: polygons thrugh a given set of points
quasi
6/13/14
Read Re: polygons thrugh a given set of points
William Elliot
6/13/14
Read Re: polygons thrugh a given set of points
quasi
6/13/14
Read Re: polygons thrugh a given set of points
David Hartley
6/13/14
Read Re: polygons thrugh a given set of points
quasi
6/13/14
Read Re: polygons thrugh a given set of points
Phil Carmody
6/13/14
Read Re: polygons thrugh a given set of points
Phil Carmody
6/14/14
Read Re: polygons thrugh a given set of points
quasi
6/14/14
Read Re: polygons thrugh a given set of points
quasi

Point your RSS reader here for a feed of the latest messages in this topic.

[Privacy Policy] [Terms of Use]

© Drexel University 1994-2014. All Rights Reserved.
The Math Forum is a research and educational enterprise of the Drexel University School of Education.