Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Begin with a polygon $P_0$.

Place two points on every edge of the polygon such that they divide each side equally into three parts. Create a new polygon $P_1$ by connecting all new points with lines.

If we begin with a square and iterate this process, what is the limit as the number of iterations approaches infinity? It is clearly not a circle, but what the correct answer is, I do not know.

share|improve this question
    
So $P_1$ is an octagon with alternate sides 1/3 and sqrt(2)/3 and all angles 3pi/4, right? –  Ross Millikan Jan 3 '11 at 12:02
    
I don't understand what you mean by "connecting all new points with lines." I don't get a (convex) polygon if I interpret this naively. –  Qiaochu Yuan Jan 3 '11 at 12:02
1  
I think the convex hull of the new points is the desired polygon at each step. Each corner will be cut off, so the number of sides will double each step. The midpoints of the sides of the original square will always be part of the polygon, so the area is bounded below by 1/2 –  Ross Millikan Jan 3 '11 at 12:13
1  
On each step you add 4 midpoints: the first 4 come from the square, the next 4 are the newer midpoints of the octagon $P_1$, then 4 come from $P_2$, etc. All these points have to lie on the limit, but it's really hard to control the corresponding equations. –  Wadim Zudilin Jan 3 '11 at 12:32
1  
@William Zudilin: I believe you add (after the second step) twice as many midpoints each generation. And they do stay permanently –  Ross Millikan Jan 3 '11 at 12:49
show 3 more comments

4 Answers 4

up vote 8 down vote accepted

Corrected per Thorny's comment: The limit curve does not appear smooth, as is visible in this picture of the first 12 polygons obtained by the process, which become visually indistiguishable at the end:

alt text

Despite appearances, and despite my initial assertion, the limit curve actually is smooth. Here is a sequence of closeups of one of the apparent corners, enlarging by a factor of 2 in successive images:

alt text

As Thorny pointed out, for the midpoint of any edge, there is an affine transformation fixing the point and taking the limit curve to itself, shrinking the edge by a factor of 3, and shrinking the plane mod the tangent to the edge by a factor of 3, and with only one eigenvector, which is tangent to the edge. Therefore, despite my initial impression, the limit curve is actually tangent to the $k$th stage polygon at the midpont of each of its edges. It looks sharp because the slopes converge slowly.

To understand this better, think of a new process scaled up by a factor of 3. If we describe the polygon by a sequence of vectors $\{v_1, \dots, v_k\}$ representing the sides, at each stage we interpolate the sum of each pair of successive vectors in circular order. The slopes of the vectors are rational, and the interpolation is by Fary addition (adding numerators and denominators). For instance, if we start with the vectors $(1,0)$ and $(0,1)$, then after 4 subdivisions we get this sequence of slopes:

{0, 1/5, 1/4, 2/7, 1/3, 3/8, 2/5, 3/7, 1/2, 4/7, 3/5, 5/8, 2/3, 5/7, 3/4, 4/5, 1, 4/5, 3/4, 5/7, 2/3, 5/8, 3/5, 4/7, 1/2, 3/7, 2/5, 3/8, 1/3, 2/7, 1/4, 1/5}

All rational slopes are obtained in this way. Since the curves are convex and the slopes are dense in the limit, the limiting curve is $C^1$, but it is not twice differentiable everywhere.

You can't expect this kind of curve to have a name (in most cases).

share|improve this answer
4  
Just a little error: there are no angles in the limit curve. It is composed of self-similar arcs under some affine transformations (with a linear part with matrix entries 1/3, 1/3, 0, 1/3, say), which are not similarities, so no nontrivial angles can be present. –  Thorny Jan 5 '11 at 14:22
    
@Thorny: Thanks for your comment, that was an embarassing oversight on my part. I've fixed the discussion. –  Bill Thurston Jan 6 '11 at 17:50
add comment

You've described de Rham's trisection method (Un peu de mathématiques à propos d'une courbe plane. Elemente der Math. 2, (1947). 73–76, 89–97.) It's the first example of a corner-cutting method. For an analysis of convergence, see Carl de Boor's Cutting corners always works (Comput. Aided Geom. Design 4 (1987), no. 1-2, 125–131). See also Chaikin's corner-cutting method and subdivision surfaces.

share|improve this answer
    
Interesting. According to the link, Chalkin's method uses the 1/4, 3/4 points for subdivision, so this one is a variation rather than a special case. According to the link, Chalkin's rule converges to a quadratic B-spline curve, so for these ratios the limit is $C^1$ smooth. –  Bill Thurston Jan 3 '11 at 16:26
    
@Bill, yes, thanks for the correction. I've edited my answer. –  lhf Jan 3 '11 at 16:47
add comment

PolyIteration
The left figure shows the first three iterations, the right after 10 iterations, when the polygon has 4096 vertices.

share|improve this answer
add comment

As noted, goes back to de Rham. Found also in:

Georges de Rham, "Sur quelques courbes définies par des equations functionnelles". Univ. e Politec. Torino. Rend. Sem. Mat. 16 1956/1957 101–113.

English tranlation in by book CLASSICS ON FRACTALS.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.