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: 711
Registered: 12/13/04
Re: polygons through a given set of points
Posted: Jun 12, 2014 10:10 AM
  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:
>>>>>
>>>>>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.


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.