Classic Iterated Function Systems

Larry Riddle, Agnes Scott College

Heighway Dragon

Description


 

Construction
Animation
 
 

Geogebra
Animation

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 = \frac{1}{{\sqrt 2 }}\) 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 alternating 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.

First three iterations

Each iteration can be represented symbolically by a sequence consisting of the letters R and L. One can imagine moving along the individual segments making up the curve start at the left endpoint. A 90° corner is labeled R if the curve makes a right turn there, and is labeled L if the curve makes a left turn at that corner. So the three iterations shown above are represented by the sequences R, RRL, and RRLRRLL, respectively. [Code Details]

Construction via paper folds

Here is how Heighway originally constructed the dragon. Fold a long narrow sheet 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 pictures show an order-3 dragon (left) and order-4 dragon (right) constructed from a narrow slice of a manila folder.

Photo of 3 folds of a narrow strip Photo of 4 folds of a narrow strip

The same symbolic representation described above can be used to describe the sequence of folds. The order-4 dragon curve shown above is RRLRRLLRRRLLRLL. [More Code details]

 
 
 

Construction
Animation

Construction via triangles

For yet another way to construct the Heighway dragon, start with an isosceles right triangle $H_0$. Replace this triangle with two isosceles right triangles so that the hypotenuses of the new triangles lie on the equal sides of the old triangle. Working around $H_0$, 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 $H_1$. For the next step, repeat the process on each of the triangles that make up $H_1$, 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.

First 4 iterations

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.


Iterated
Function
System

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.

Red segments in isosceles triangle forming angles of 45 degrees with base


IFS
Animation
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
 
\( f_1(\mathbf{x})= \left[ \begin{array}{cc} 1/2 & -1/2\\ 1/2 & 1/2 \end{array} \right]\mathbf{x} \)
scale by \(r\), rotate by 45°
\( f_2(\mathbf{x})= \left[ \begin{array}{cc} -1/2 & -1/2\\ 1/2 & -1/2 \end{array} \right]\mathbf{x} + \left[ \begin{array}{c} 1\\ 0 \end{array} \right] \)
scale by \(r\), rotate by 135°

where \(r = \frac{1}{{\sqrt 2 }}\). The attractor of this IFS will be the Heighway dragon. It consists of two self-similar pieces corresponding to the two functions in the IFS [Similarity Demonstration].

Heighway dragon split into 2 self-similar pieces
[Enlarge]
[See this design in backstitch]


IFS
Animation

There is another way to visualize the action of this IFS. At each iteration, scale the current figure by \(r = \frac{1}{{\sqrt 2 }}\) and rotate by 45 around the origin. This is the same as function \(f_1\). Then make a copy of this figure and rotate it by 90° around the point (1/2,1/2). This will give an equivalent result as the function \(f_2\). Click the button to the left to watch an animation of the IFS iteration.

L-System

 
 

L-system
Animation
Angle 45
Axiom FX
F —> Z
X —> +FX−−FY+
Y —> −FX++FY−


First four iterations of the L-system

Similarity
Dimension

The Heighway dragon is self-similar with 2 non-overlapping copies of itself, each scaled by the factor $r \lt 1$. Therefore the similarity dimension, $d$, of the attractor of the IFS is the solution to

\[\sum\limits_{k = 1}^2 {{r^d}} = 1 \quad \Rightarrow \quad d = \frac{{\log (1/2)}}{{\log (1/\sqrt 2 )}} = 2\]

Special
Properties

Photo of John Heighway
John Heighway

Photo of William Harter
William Harter

Photo of Bruce Banks
Bruce Banks
The Heighway dragon was discovered by John Heighway in 1966 and named by William Harter. It was investigated by Heighway, Harter, and Bruce Banks while they were working as physicists with NASA. The dragon curve was described by Martin Gardner in 1967 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 in 1970. The version that Harter used for the NASA cover, and which was reproduced in Gardner's column, looked like the following (with 11 iterations, but the original had rounded corners.)

NASA Cover with dragon looking towards the left

In his column Gardiner wrote that "the curve vaguely resembles a sea dragon paddling to the left with clawed feet, his curved snout and coiled tail just above an imaginary waterline." Donald Knuth reported in his book about how Harter remarked to him that the iterations of the dragon in Michael Crichton's novel, Jurassic Park, are upside down or "as dead dragons". The Heighway dragon now appears in many different orientations depending on how it is drawn [See Examples].

Area

The Heighway dragon as described here starting with a line segment of length 1 has area 1/2 [Area Details]. If the initial line segment has length $b$, then the area of the Heighway dragon will be $b^2/2$ [see the derivation of area based on the Heighway boundary].

Bounding
Rectangle

The copy of the Heighway dragon below lies on top of a grid of size 1/6 by 1/6 with it's tail located at the origin. It demonstrates that the Heighway dragon lies within a rectangle with $-2/6 \lt x \lt 7/6$ and $-2/6 \lt y \lt 4/6$, i.e. a rectangle of width 1.5 and height 1 [Rectangle Details].

Heighway dragon on grid of size 1/6 by 1/6

Tiling

The Heighway dragon can be used to tile the plane [Tiling Details].

Four copies of the dragon rotated around a common point to form a tile
[See this design in back stitch]

Boundary

The boundary of the Heighway dragon is also a fractal with dimension 1.523627 [Boundary Details].

Heighway dragon with boundary highlighted

Components

The Heighway dragon is composed of an infinite union of geometrically similar components that spiral around two curves ending at the endpoints of the initial line segment in the construction of the dragon. Each component consists of two copies of the dragon (forming a twindragon), one copy of the component scaled by 1/2 and rotated by 180°, and two copies of the component scaled by 1/4 [Component Details].

The components drawn in different colors
[See this design in back stitch]

Space
Filling

Let $H$ be the attractor 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. For a proof, see the book by Edgar. [Click for another example of a space filling curve generated by an iterated function system.]

Other Angles


Birth of a
Heighway Dragon
Animation
The Heighway dragon can be constructed by replacing a line segment with two segments that make an angle of 45° with the initial segment. If the angle of the two line segments is less than 45° then a different dragon curve will be formed. If we let the angle grow from 0° to 45°, we can watch the Heighway dragon being born. See the animation.

 

Similarity
to
Lévy Dragon

The construction of the Lévy dragon and the Heighway dragon are very similar. In each case one can start with an isosceles right triangle and replace this triangle with two isosceles 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 Heighway dragon into the Lévy dragon through a continuous transformation. Indeed, for each t in the interval [0,1] define an iterated function system by


Heighway
to
Lévy
Animation
\[\begin{array}{l} {f_1}(t)({\bf{x}}) = \left[ {\begin{array}{cc} {1/\sqrt 2 } & 0 \\ 0 & {1/\sqrt 2 } \\ \end{array}} \right]\left[ {\begin{array}{cc} {\cos ({{45}^ \circ })} & { - \sin ({{45}^ \circ })} \\ {\sin ({{45}^ \circ })} & {\cos ({{45}^ \circ })} \\ \end{array}} \right]{\bf{x}} \\ {f_2}(t)({\bf{x}}) = \left[ {\begin{array}{cc} {1/\sqrt 2 } & 0 \\ 0 & {1/\sqrt 2 } \\ \end{array}} \right]\left[ {\begin{array}{cc} {\cos ({{135}^ \circ } - {{180}^ \circ }t)} & { - \sin ({{135}^ \circ } - {{180}^ \circ }t)} \\ {\sin ({{135}^ \circ } - {{180}^ \circ }t)} & {\cos ({{135}^ \circ } - {{180}^ \circ }t)} \\ \end{array}} \right]{\bf{x}} + \left[ {\begin{array}{c} {1 - t/2} \\ {t/2} \\ \end{array}} \right] \\ \end{array}\]

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 Heighway dragon and A(1) equal to the Lévy dragon. The animation shows A(t) as t goes from 0 to 1. Watch a one-minute YouTube video showing the transformation of the Heighway dragon into the Lévy dragon, and then back to the Heighway dragon (with a cameo appearance by the twindragon along the way.)

Variations

Twindragon

The twindragon is constructed by placing two Heighway dragons back-to-back (so one is rotated by 180°).

2 heighway dragons in different colleges forming a twindragon
[See this design in back stitch]

Terdragon

The terdragon is a variation of the paper folding construction of the Heighway dragon in which the folds trisect the paper at each step instead of bisecting it. It was first introduced by Davis and Knuth in their 1970 paper on dragon curves.

Terdragon

Golden Dragon

The golden dragon is constructed similarly to the Heighway dragon construction via line segments, except using different scaling factors and angles. It has this name because its similarity dimension is the golden ratio.

Golden Dragon

$Z_2$ Heighway Dragon

If the elements of the $Z_2$ cyclic group are applied to the functions in the Heighway dragon IFS, a new IFS is created whose attractor exhibits rotational symmetry through 180°.

HeighwayZ2-sm

 

References

  1. Bannon, Thomas. "Fractals and Transformations," Mathematics Teacher, March 1991, 178-185.
  2. Budinski, Natalija and Miroslav Novta. "Folding the Dragon Curve Fractal," Proceedings of Bridges 2017: Mathematics, Art, Music, Architecture, Education, Culture, 573–578.
  3. 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.
  4. Davis, Chandler and Donald J. Knuth. "Number representations and dragon curves" J. Recreational Math. 3 (1970) 66-81 (Part 1), 133-149 (Part 2). Reprinted with extra addendum in Selected Papers on Fun and Games, Donald Knuth, CSLI Publications, 2011.
  5. Edgar, Gerald A. Measure, Topology, and Fractal Geometry, Springer-Verlag, 1990.
  6. Gardner, Martin. "Mathematical Games," Scientific American, March, April, July, 1967. [Reprinted in his Mathematical Magic Show, Knopf, 1977]
  7. Jones, Juw. "Fractals Before Mandelbrot-A Selective History," in Fractals and Chaos, Crilly, Earnshaw, and Jones, Editors, Springer-Verlag 1991.
  8. Helmberg, Gilbert. Getting Acquainted with Fractals, de Gruyter Publishing, 2007. [See Preview at Google Books]
  9. Lauwerier, Hans. Fractals, Princeton Science Library, Princeton, N.J. 1991 (Translated by Sophia Gill-Hoffstadt from the 1987 edition), p.50.
  10. Mandelbrot, Benoit. The Fractal Geometry of Nature, W.H. Freeman and Co. 1983, p66.
  11. McWorter Jr., William A. and Jane Morrill Tazelaar. "Creating Fractals," Byte, August 1987, 123-132.
  12. Prusinkiewicz, Przemyslaw and James Hanan. Lindenmayer Systems, Fractals, and Plants, Lecture Notes in Biomathematics #79, Springer-Verlag 1989.
  13. Prusinkiewicz, Przemyslaw and Aristid Lindenmayer. The Algorithmic Beauty of Plants, Springer-Verlag, 1990. [Available from the Algorithmic Botany website]
  14. Angle Chang and Tianrong Zhang. "The Fractal Geometry of the Boundary of Dragon Curves," J. Recreational Mathematics, Vol. 30, No. 1 (1999-2000), 9-22. [Available at http://poignance.coiraweb.com/math/Fractals/Dragon/Bound.html]
  15. Ngai, Sze-Man and Nhu Nguyen. "The Heighway Dragon Revisited," Discrete and Computational Geometry, Vol. 29, no. 4 (2003), 603-623. [Available at Springer Link].
  16. Benedek, Agnes and Rafael Panzone. "On Some Notable Plane Sets, II: Dragons," Revista de la Unión Matemática Argentina, Vol. 39 (1994), 76-89 (pdf).
  17. Tabachnikov, Sergie. "Dragon Curves Revisited," Mathematical Intelligencer, 36, No 1 (2014), 13-17. [Available at https://drive.google.com/file/d/1HnbOWSFyTuUbBHVrSDKWn97YEA0kPrH2/view>]
  18. Ryde, Kevin. Iterations of the Dragon Curve, http://user42.tuxfamily.org/dragon/index.html. An extensive investigation of "Various properties of finite iterations of the Heighway/Harter dragon curve and twindragon curve, including boundary, area, convex hull, minimum rectangle, XY convex hull, centroid, inertia, complex base i±1, area tree, and some properties of the fractal limit including boundary and fixed point."