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 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 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 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