12
$\begingroup$

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.

Improve this question
$\endgroup$
8
  • $\begingroup$ So $P_1$ is an octagon with alternate sides 1/3 and sqrt(2)/3 and all angles 3pi/4, right? $\endgroup$
    – Ross Millikan
    Commented Jan 3, 2011 at 12:02
  • $\begingroup$ 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. $\endgroup$
    – Qiaochu Yuan
    Commented Jan 3, 2011 at 12:02
  • 3
    $\begingroup$ 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 $\endgroup$
    – Ross Millikan
    Commented Jan 3, 2011 at 12:13
  • 1
    $\begingroup$ 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. $\endgroup$
    – Wadim Zudilin
    Commented Jan 3, 2011 at 12:32
  • 1
    $\begingroup$ @William Zudilin: I believe you add (after the second step) twice as many midpoints each generation. And they do stay permanently $\endgroup$
    – Ross Millikan
    Commented Jan 3, 2011 at 12:49

4 Answers 4

Reset to default
8
$\begingroup$

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 http://dl.dropbox.com/u/5390048/chippedsquare.jpg

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 http://dl.dropbox.com/u/5390048/CornerCloseup.jpg

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 Farey 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).

Improve this answer
$\endgroup$
2
  • 4
    $\begingroup$ 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. $\endgroup$
    – Thorny
    Commented Jan 5, 2011 at 14:22
  • $\begingroup$ @Thorny: Thanks for your comment, that was an embarassing oversight on my part. I've fixed the discussion. $\endgroup$
    – Bill Thurston
    Commented Jan 6, 2011 at 17:50
7
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$
    – Bill Thurston
    Commented Jan 3, 2011 at 16:26
  • $\begingroup$ @Bill, yes, thanks for the correction. I've edited my answer. $\endgroup$
    – lhf
    Commented Jan 3, 2011 at 16:47
6
$\begingroup$

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

Improve this answer
$\endgroup$
3
$\begingroup$

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 my book CLASSICS ON FRACTALS.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .