Iterated Function
Systems
Larry Riddle
Home Sierpinski Gasket Sierpinski Carpet Sierpinski Pentagon Heighway Dragon
McWorter Pentigree Pentadentrite Koch Curve Koch Snowflake Levy Dragon

Heighway's Dragon

 





Construction
Animation
(18Kb)

Construction via line segments

Begin with a line segment. As the first iteration, replace this segment with two segments, each scaled by a ratio r = , in such a way that the original segment would have been the hypotenuse of an isosceles right triangle. Following along the original segment, we place the two new segments to the left. For the second iteration, replace each of the segments with two new segments at right angles, each scaled by the ratio r. The new segments are placed to the left then to the right along the segments of the first iteration. Continue this construction, always alterning the new segments between left and right along the segments of the previous iteration. This generates the "dragon curve". The following figure shows the first three iterations for this construction.

Construction via paper folds

Here is how Heighway originally constructed the dragon. Fold a sheet of cardboard in half. Fold again in the same direction (Example). Continue folding, always folding in the same direction. After several folds, open the sheet so that every fold is a right angle and view the sheet from the edge. In general, n folds produces an order-n dragon. The following picture shows an order-3 dragon (bottom) and order-4 dragon (top) constructed from a narrow sheet of cardboard.


Construction
Animation
(19Kb)

Construction via triangles

For yet another way to construct the Heighway dragon, start with an isoceles right triangle H0. Replace this triangle with two isoceles right triangles so that the hypotenuses of the new triangles lie on the equal sides of the old triangle. Working around H0, starting from the left side, we place the first new triangle so that it points out from the old triangle and the other new triangle so that it points into the old triangle to get H1. For the next step, repeat the process on each of the triangles that make up H1, this time placing the new triangles so they point Out, In, In, Out, respectively, as illustrated in the figure below. This pattern of Out, In, In, Out is repeated for each subsequent iteration of the construction.

The Heighway dragon is the limiting set of this iterative construction. Notice that the line segments that make up the hypotenuses of the triangles form the same path as described in the first construction above.

To think of this construction as a result of affine transformations, consider the first iteration of the line segment from (0,0) to (1,0) as shown by the two red line segments in the following figure.

Because of the need to alternate left and right when constructing the dragon, we need to think of constructing the second line segment by a rotation through 135° followed by a translation of the origin to the point (1,0). This yields the following IFS


IFS
Animation
(27Kb)

where r = . The fixed invariant set of this IFS will be the same as the dragon curve.

Angle 45
Axiom FX
F --> Z
X --> +FX- - FY+
Y --> -FX++FY-


First four iterations of the L-system

We have a hyperbolic IFS with each map being a similitude of ratio r < 1. Therefore the similarity dimension, d, of the unique invariant set of the IFS is the solution to

Heighway's dragon was first investigated by physicists John Heighway, Bruce Banks, and William Harter. It was described by Martin Gardner in his Mathematical Games column of Scientific American where he stated that Harter used the dragon as a cover design for a booklet prepared for a NASA seminar on group theory. Many of its properties were first published by Chandler Davis and Donald Knuth.

The iteration of the L-system generates the "dragon curve". The individual line segments never cross. For a proof, see the text by Edgar. Now consider drawing the segments so that the corners always occur at integer lattice points in the plane. Harter was the first to show that copies of the dragon could be fitted together to cover all lattice points. For example, shown below is the 7th iterate (in black) and three copies, each rotated by 90°. The dot indicates the beginning of the curve (the tail).

Now join each of the curves tail to tail to form the following arrangement (curves have been enlarged for a better view). Notice all the lattice points that are covered in the region around the common tails.

The entire plane can be covered by continuing to fit these pieces together. More details can be found in the paper by Davis and Knuth.

Let H be the unique invariant set for the IFS. There is a continuous curve f defined on [0,1] such that f([0,1]) = H and such that f is a space filling curve. This means that H has a non-empty interior.


Lévy to
Heighway
Animation
(106Kb)
 The construction of the Lévy dragon and the Heighway dragon are very similar. In each case one can start with an isoceles right triangle and replace this triangle with two isoceles right triangles so that the hypotenuse of each new triangle lies on one of the equal sides of the old triangle. The difference is how those new triangles are placed relative to sides of the old triangle. For the Lévy dragon, both are placed towards the "outside"; for the Heighway dragon, one is placed pointing out while the other is placed pointing in. Because of this similarity, it is perhaps not surprising that one can transform the Lévy dragon into the Heighway dragon through a continuous transformation. Indeed, for each t in the interval [0,1] define an iterated function system by

Let A(t) be the unique attractor of the iterated function system corresponding to the value t. Then A is a continuous function from the unit interval to the space of compact sets with the Hausdorff topology, with A(0) equal to the Lévy dragon and A(1) equal to the Heighway dragon. The Quicktime movie gives an animation of A(t) as t goes from 0 to 1.
 
  1. Bannon, Thomas. "Fractals and Transformations," Mathematics Teacher, March 1991, 178-185.
  2. Crichton, Michael. Jurassic Park, Ballantine Books, New York 1990. If you read the book or saw the movie, you will remember that chaos theory, in particular the idea of sensitive dependence on initial conditions, was a major reason why the mathematician Ian Malcolm believed the idea of creating a prehistoric world of dinosaurs would never work. Each chapter of the book is illustrated with an iteration of the Heighway Dragon.
  3. Davis, Chandler and Donald J. Knuth. "Number representations and dragon curves" J. Recreational Math. 3 (1970) 66-81 (Part 1), 133-149 (Part 2).
  4. Edgar, Gerald A. Measre, Topology, and Fractal Geometry, Sringer-Verlag, 1990.
  5. Gardner, Martin. "Mathematical Games," Scientific American, March, April, July, 1967.
  6. Jones, Juw. "Fractals Before Mandelbrot-A Selective History," in Fractals and Chaos, Crilly, Earnshaw, and Jones, Editors, Springer-Verlag 1991.
  7. Lauwerier, Hans. Fractals, Princeton Science Library, Princeton, N.J. 1991 (Translated by Sophia Gill-Hoffstadt from the 1987 edition), p.50.
  8. Mandelbrot, Benoit. The Fractal Geometry of Nature, W.H. Freeman and Co. 1983, p66.
  9. McWorter Jr., William A. and Jane Morrill Tazelaar. "Creating Fractals," Byte, August 1987, 123-132.
  10. Prusinkiewicz, Przemyslaw and James Hanan. Lindenmayer Systems, Fractals, and Plants, Lecture Notes in Biomathematics #79, Springer-Verlag 1989.
  11. Prusinkiewicz, Przemyslaw and Aristid Lindenmayer. The Algorithmic Beauty of Plants, Springer-Verlag, 1990.
Home Sierpinski Gasket Sierpinski Carpet Sierpinski Pentagon Heighway Dragon
McWorter Pentigree Pentadentrite Koch Curve Koch Snowflake Levy Dragon