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 3: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:
>>>
>>>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
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.