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

 Search Thread: Advanced Search

 Messages: [ Previous | Next ]
 Marnie Northington Posts: 1,251 Registered: 12/13/04
Re: polygons through a given set of points
Posted: Jun 12, 2014 3:10 AM
 Plain Text Reply

quasi <quasi@null.set> 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 subtletly.
>
> 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.

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

© The Math Forum at NCTM 1994-2018. All Rights Reserved.