Consider an arbitrary polygon P1

Now form Polygon P2 by joining the midpoints of the sides of P1.

Now form P3, P4, ..... similarly.

What can be said about the limit of this series?
What happens if instead of bisecting the sides, we p-sect the sides by
cutting them in the ratio p:1-p (e.g.: 'thirding' the sides would have
p=0.3333; bisecting them has p=0.5)


Conjecture: the limit is the regular polygon or the polygon with
paralel opposite sides.

Has this been written up anywhere? (I have a reference on a book on
Recreational Maths by Cadwell.)

---

Request for Question Clarification by mathtalk-ga on 21 Sep 2004 20:37 PDT

Hi, johnbibby-ga:

I recall this problem being kicked around in a newsgroup, but it may
have been an isolated thread that never made it into Google's Groups
archives.

In any case I see that a fairly complete solution can be derived from
the eigenvalue approach outlined in the Comment I posted below.

As other Commenters have pointed out, the shapes need not become
progressively more regular.  One sees already with the triangle that
all the shapes can be similar, so that no derived polygon is any more
regular than the original.

But perhaps the real focus of your Question is in the last line, has
the problem been written up anywhere?  Please clarify whether your
interests lie more in an analysis of the convergence to a point or in
pointers to "literature" on this Question.

regards, mathtalk-ga

---

Clarification of Question by johnbibby-ga on 28 Sep 2004 15:11 PDT

Thanks for everyone's ideas on this.  I think the eigenvalue approach
may be the best way. I have found something similar for a related but
different problem in Cadwell's book on 'Mathematical Recreations'.  I
have not seen David Wells' book yet.

I'm still not sure if my conjecture (that the polygon becomes more and
more 'regular') has been proved or disproved.

1) Consider a square. Joining the midpoints of a square gives ... a
square. Given a side of s for P1, the perimeter of P1 is 4s. The
perimeter of P2 is 4(s*sqrt(2)/2), or a ratio of 4s/(2s*sqrt(2)) or
1/sqrt(2). The limit will quickly approach a point as the squares
become smaller. For every regular polygon, it is easy to see that the
midpoint-connected polygon is simply a smaller version of its
circumscribed "Parent".

I'm interested to know about the intended picture of p<>0.5... Does
this mean that P2 is merely rotated but having exactly the same number
of sides as P1? ... If so, it can probably be shown that, again, the
interior polygons will be similar to each other, with a limit that
approaches a point.

I can't see how an odd numbered polygon can ever have parallel sides,
unless it started with parallel sides.

On normal paper, draw an n-sided polygon. On tracing paper, connect
the midpoints of the polygon. You will find most probably that you can
rotate the tracing paper, and every angle will be congruent to the
parent, in the same order as the parent. Chances are, you will find
this the case for every value of p as well. (It's easy to verify p=0.5
and p=0)

An n-gon with concave sides will form an n-gon with convex sides, and
all future  n-gons will be similar convex n-gons, with limit
approaching a point.

This is a free comment.

Hi Crythias. Thanks for your comment, and for engaging with this
question so swiftly.

You've picked up on two obvious points:
     1. What a stupid question - the process obviously converges upon
a POINT! My answer: well yes it does. What I'm interested is the SHAPE
that it converges to. (If you like you could say that at each stage
you re-size the polygon so it is a standard 'size' - area, or
somesuch.)
     2. If n is odd, then it's hard for opposite sides to be parallel.
My answer: Yes indeed! For n=odd, some other criterion must apply.
(Hint - because I do have some idea of what the answer might be: I
think the polygon might be getting 'more regular', whatever that might
mean, at each stage of the iteration.)

Some more comments no your comments:


    A. You say: 'For every regular polygon, it is easy to see that the
midpoint-connected polygon is simply a smaller version of its
circumscribed "Parent".'  I agree. The regular case is not very interesting.

    B. You say: 'I'm interested to know about the intended picture of
p<>0.5... Does this mean that P2 is merely rotated but having exactly
the same number
of sides as P1? ... If so, it can probably be shown that, again, the
interior polygons will be similar to each other, with a limit that
approaches a point.'
       Yes, it is rotated and has the same number of sides. (Not sure
about the 'merely' though.) Yes, the limit approaches a point (but see
above - it's the SHAPE I'm interested in, not the SIZE).  Also, I
don;t think you are right in saynig they are 'similar' (if by that you
mean 'the same shape'.

        C. You say: 'On normal paper, draw an n-sided polygon. On
tracing paper, connect the midpoints of the polygon. You will find
most probably that you can rotate the tracing paper, and every angle
will be congruent to the
parent, in the same order as the parent.'
        Nope: 'fraid it doesn't work that way. (I used 'Geometer's
SketchPad' - see www.mathsite.co.uk  Angles are not congruent and
shapes are not similar.)

Thanks for your comments Crythias.

I think I'll revise my comment by one statement: regardless of what P1
looks like, P2 will be the shape of the subsequent inscribed n-gons.

hi johnbibby-ga!
I'm afraid your conjecture is incorrect:

Consider an equilateral but non-regular penagon (its sides are
congruent, but its angles are not; also no sides are paralell).
Now add points to trisect each side.  What you have now is a 15-gon.
Now apply your rule with p=0.5
Let's just consider one corner of your 15-gon (not one of the 10 straight angles)
Let's call the point at the corner C and the two points on each side
that are the vertices of straight angles A, B, D, and E.

    A
   /
  B
 /
C
 \
  D
   \
    E

(sorry for the bad drawing)
now apply your rule for this angle:
take midpoints and connect them.  The line segments never make their
way past B and D.  This means that segments DE and AB will never be
changed, and since none of the original segments were paralell, they
still aren't.  Thus the limiting shape for our 15-gon is not a point,
but an infinity-gon with finite area and rounded angles.
I explained this pretty badly.  If you don't understand what I'm
trying to say, please post a comment.

I don't understand how you can increase the number of sides ... unless
you're talking about all the vertices ever used, parent and child. We
must agree that  P(x+1) is based upon one vertex per side of P(x).

Px as x->infinity is simply the n-gon of P2 with a size of P2*(P3/P2)^(x-2)

That's my story and I'm sticking to it. :)

Dear Crythia and jhenry

Thanks for your comments - I think jhenry is working on a different
problem from me (but maybe eaully interesting)

In my problem, each side just generate ONE point - it may be the
midpoint, it may be the thirdile (one-third of the way along from
either end), or it can be any p-ile.

However in my problem you do NOT trisect the side and thus get two new
points - which I think is what jhenry was looking at.

Crythias said:
      I think I'll revise my comment by one statement: regardless of what P1
looks like, P2 will be the shape of the subsequent inscribed n-gons.

This may be true for some P1, but not for all. (If P1 is any
quadrilateral, then P2 is a paralelogram, and so are P3, P4, P5
........)

I'm interested in knowing whether the ANGLES BETWEEN THE SIDES become
closer to each other as n increases.

Thank you all for looking at this

JOHN

I said:
      I think I'll revise my comment by one statement: regardless of what P1
looks like, P2 will be the shape of the subsequent inscribed n-gons.

You said:
This may be true for some P1, but not for all. (If P1 is any
quadrilateral, then P2 is a paralelogram, and so are P3, P4, P5
........)

I reply: 
I think we must be in agreement, then. P3, P4, P5... are similar
n-gons to P2, regardless of what P1 looks like, which is the crux of
my adjusted statement.

You further comment:
I'm interested in knowing whether the ANGLES BETWEEN THE SIDES become
closer to each other as n increases.

I reply:
Do you mean "p"? or "n" being the number of sides or "n" being the nth
iteration of Pn?
A brief non-scientific proof of "p" being inconsequential is this: If
we can agree that the premise of P3 being similar to P2 when p=0
(conguency) and p being similar to P2 when p=0.5 (this is true for
triangles and quadrilaterals), then we can probably assume that the
same percentage affects all proportions of segments connected at point
p anywhere on 0<=p<=1, in a triangular/linear fashion. That is to say,
the smallest n-gon P3 can be will be when p=0.5. It will
proportionally decrease in size as p increases from 0<=p<=0.5, and
increase in size proportionally as p increases 0.5<=p<=1. Since all
p-connections change at the same proportion/rate, the n-gon likewise
retains the same shape as parent, AFTER P2.

I have to say, no, there will not be and cannot be any changes to
angles after P2 no matter what p is. (trivial to check p=0, p=0.5, and
p=1)

This comment considers the case p=0.5, that is, connecting the midpoints.

If P1 is a triangle, then P1, P2, P3,... are similar triangles.

If P1 is a quadrilateral, then P2, P4, P6,... are similar
parallelograms, and P3, P5, P7,... are similar parallelograms.  But
the Pevens are not similar to the Podds in general (and of course, P1
is not similar to P3, P5, P7,... in general).  So in this case there
is not one limiting shape, but two.

If the number so sides of P1 is greater than 4, my guess is that there
are multiple limiting shapes (i.e. a repeating pattern with more than
one shape), and that in general the sides are not all the same length.

One approach to such problems is to consider the mapping as a linear
transformation or matrix multiplication.

A polygon has N vertices in 2 dimensions, which can be modelled as an Nx2 matrix.

We multiply both columns on the left by an NxN circulant matrix which
takes the appropriate (weighted) average of consecutive vertices to
produce each new vertex.  Note that the averaging of the x-coordinates
and y-coordinates are "decoupled".

Now this circulant matrix is in fact an irreducible probability
transition matrix, and as was proven here in a more general setting:

http://answers.google.com/answers/threadview?id=379557

the Perron-Froebenius Theorem tells us we have one simple eigenvalue =
1 which is "dominant".  Thus repeated averaging of the vertices
converges geometrically to the midpoint (mean of the vertices) of the
original polygon.

I suspect the stable "shapes" in the sequence correspond to other
eigenvalues of the NxN matrix multiplication.

regards, mathtalk-ga

:) I admit it. I was most likely wrong. Here's a thought, though... as
sides will inevitably grow smaller, the ratio of side lengths will get
closer to 1, therefore, you could possibly say that you're approaching
a regular n-gon. Of course, that may require division by zero, but
that hasn't stopped me before :).

Turns out your conjecture about parallel opposite sides is correct. 
If you have access to MATLAB, run the following code.  Of course, this
is only true for N even.  If N is odd, I'm not sure how to describe
the limiting shape quantitatively, except to say that it approaches an
elliptical shape.  In fact, I think that in the limit as N goes to
infinity, the limiting shape is an ellipse.  It is also possible that
the limiting shape for any N has vertices which lie on an ellipse, but
I haven't checked that.

Incidentally, here's a related problem: can every convex quadrilateral
be inscribed in an ellipse?

N = 6;
n = 100;
A = eye(N) + diag(ones(N-1,1),1);
A(N,1) = 1;
A = A/2;
xy = rand(N,2);
xy = xy - ones(N,1)*mean(xy);
plot([xy(:,1); xy(1,1)],[xy(:,2); xy(1,2)])
axis equal
for i=1:n
  xy = A*xy;
end
figure
plot([xy(:,1); xy(1,1)],[xy(:,2); xy(1,2)])
axis equal

from memory this question was posited in "You are a Mathematician" by David Wells

RE: your clarification of question-- 

It has been proved, empirically.  If you don't have access to MATLAB,
you can write a code in whatever you do have.  Or you can just trust
me.  The code I posted, used with even N, always yeilds a polygon with
parallel opposite sides.  As the number of sides gets large, either
even or odd, the shape of the polygon approximates an ellipse.

After playing some more:

The limiting shapes are not regular polygons, but they're close. 
They're stretched regular polygons.  After enough iterations,
regardless of the value of N (the number of sides), the polygon you
get can be obtained by drawing a regular polygon, and then evenly
stretching the paper on which it's drawn along some axis and by some
amount.  Another way to say it is that the limiting shape can always
be obtained by viewing a regular polygon from the proper angle.

This has a couple of geometrical implications: any triangle can be
formed by stretching an equilateral triangle.  Any parallelogram can
be formed by stretching a square.