Dragon curve

A dragon curve is any member of a family of self-similar fractal curves, which can be approximated by recursive methods such as Lindenmayer systems. The dragon curve is probably most commonly thought of as the shape that is generated from repeatedly folding a strip of paper in half, although there are other curves that are called dragon curves that are generated differently.

Heighway dragon

The Heighway dragon (also known as the Harter–Heighway dragon or the Jurassic Park dragon) was first investigated by NASA physicists John Heighway, Bruce Banks, and William Harter. It was described by Martin Gardner in his Scientific American column Mathematical Games in 1967. Many of its properties were first published by Chandler Davis and Donald Knuth. It appeared on the section title pages of the Michael Crichton novel Jurassic Park.^[1]

Construction

The Heighway dragon can be constructed from a base line segment by repeatedly replacing each segment by two segments with a right angle and with a rotation of 45° alternatively to the right and to the left:^[2]

The Heighway dragon is also the limit set of the following iterated function system in the complex plane:

f_{1}(z)={\frac {(1+i)z}{2}}

f_{2}(z)=1-{\frac {(1-i)z}{2}}

with the initial set of points $S_{0}=\{0,1\}$ .

Using pairs of real numbers instead, this is the same as the two functions consisting of

f_{1}(x,y)={\frac {1}{\sqrt {2}}}{\begin{pmatrix}\cos 45^{\circ }&-\sin 45^{\circ }\\\sin 45^{\circ }&\cos 45^{\circ }\end{pmatrix}}{\begin{pmatrix}x\\y\end{pmatrix}}

f_{2}(x,y)={\frac {1}{\sqrt {2}}}{\begin{pmatrix}\cos 135^{\circ }&-\sin 135^{\circ }\\\sin 135^{\circ }&\cos 135^{\circ }\end{pmatrix}}{\begin{pmatrix}x\\y\end{pmatrix}}+{\begin{pmatrix}1\\0\end{pmatrix}}

Folding the dragon

The Heighway dragon curve can be constructed by folding a strip of paper, which is how it was originally discovered.^[1] Take a strip of paper and fold it in half to the right. Fold it in half again to the right. If the strip was opened out now, unbending each fold to become a 90-degree turn, the turn sequence would be RRL, i.e. the second iteration of the Heighway dragon. Fold the strip in half again to the right, and the turn sequence of the unfolded strip is now RRLRRLL – the third iteration of the Heighway dragon. Continuing folding the strip in half to the right to create further iterations of the Heighway dragon (in practice, the strip becomes too thick to fold sharply after four or five iterations).

The folding patterns of this sequence of paper strips, as sequences of right (R) and left (L) folds, are:

1st iteration: R
2nd iteration: R R L
3rd iteration: R R L R R L L
4th iteration: R R L R R L L R R R L L R L L.

Each iteration can be found by copying the previous iteration, then an R, then a second copy of the previous iteration in reverse order with the L and R letters swapped.^[1]

Properties

Many self-similarities can be seen in the Heighway dragon curve. The most obvious is the repetition of the same pattern tilted by 45° and with a reduction ratio of $\textstyle {\sqrt {2}}$ . Based on these self-similarities, many of its lengths are simple rational numbers.

Lengths

Self-similarities

The dragon curve can tile the plane. One possible tiling replaces each edge of a square tiling with a dragon curve, using the recursive definition of the dragon starting from a line segment. The initial direction to expand each segment can be determined from a checkerboard coloring of a square tiling, expanding vertical segments into black tiles and out of white tiles, and expanding horizontal segments into white tiles and out of black ones.^[3]
As a space-filling curve, the dragon curve has fractal dimension exactly 2. For a dragon curve with initial segment length 1, its area is 1/2, as can be seen from its tilings of the plane.^[1]
The boundary of the set covered by the dragon curve has infinite length, with fractal dimension $2\log _{2}\lambda \approx 1.523627086202492,$ where $\lambda ={\frac {1+(28-3{\sqrt {87}})^{1/3}+(28+3{\sqrt {87}})^{1/3}}{3}}\approx 1.69562076956$ is the real solution of the equation $\lambda ^{3}-\lambda ^{2}-2=0.$ ^[4]

Twindragon

The twindragon (also known as the Davis–Knuth dragon) can be constructed by placing two Heighway dragon curves back to back. It is also the limit set of the following iterated function system:

f_{1}(z)={\frac {(1+i)z}{2}}

f_{2}(z)=1-{\frac {(1+i)z}{2}}

where the initial shape is defined by the following set $S_{0}=\{0,1,1-i\}$ .

It can be also written as a Lindenmayer system – it only needs adding another section in the initial string:

angle 90°
initial string FX+FX+
string rewriting rules
- X ↦ X+YF
- Y ↦ FX−Y.

It is also the locus of points in the complex plane with the same integer part when written in base $(-1\pm i)$ .^[5]

Terdragon

The terdragon can be written as a Lindenmayer system:

angle 120°
initial string F
string rewriting rules
- F ↦ F+F−F.

It is the limit set of the following iterated function system:

f_{1}(z)=\lambda z

f_{2}(z)={\frac {i}{\sqrt {3}}}z+\lambda

f_{3}(z)=\lambda z+\lambda ^{*}

{\mbox{where }}\lambda ={\frac {1}{2}}-{\frac {i}{2{\sqrt {3}}}}{\text{ and }}\lambda ^{*}={\frac {1}{2}}+{\frac {i}{2{\sqrt {3}}}}.

Lévy dragon

The Lévy C curve is sometimes known as the Lévy dragon.^[6]

Variants

The dragon curve belongs to a basic set of iteration functions consisting of two lines with four possible orientations at perpendicular angles:

Curve	Creators and Creation Year of Dragon Family Members
Lévy Curve	Ernesto Cesàro (1906), Georg Faber (1910), Paul Lévy (1914)
Dragon curve	John Heighway (1966), Bruce Banks (1966), William Harter (1966)
Davis Diamond	Chandler Davis (1970), Donald J. Knuth (1970)
Knuth Wedge	Chandler Davis (1970), Donald J. Knuth (1970)
Unicorn Curve	Peter van Roy (1989)
Lion Curve	Bernt Rainer Wahl (1989)

It is possible to change the turn angle from 90° to other angles. Changing to 120° yields a structure of triangles, while 60° gives the following curve:

The dragon curve, 60° variant. Self-similarity is clearly visible.

A discrete dragon curve can be converted to a dragon polyomino as shown. Like discrete dragon curves, dragon polyominoes approach the fractal dragon curve as a limit.

Occurrences of the dragon curve in solution sets

Having obtained the set of solutions to a linear differential equation, any linear combination of the solutions will, because of the superposition principle, also obey the original equation. In other words, new solutions are obtained by applying a function to the set of existing solutions. This is similar to how an iterated function system produces new points in a set, though not all IFS are linear functions. In a conceptually similar vein, a set of Littlewood polynomials can be arrived at by such iterated applications of a set of functions.

A Littlewood polynomial is a polynomial: $p(x)=\sum _{i=0}^{n}a_{i}x^{i}\,$ where all $a_{i}=\pm 1$ .

For some $|w|<1$ we define the following functions:

f_{+}(z)=1+wz

f_{-}(z)=1-wz

Starting at z=0 we can generate all Littlewood polynomials of degree d using these functions iteratively d+1 times.^[7] For instance: $f_{+}(f_{-}(f_{-}(0)))=1+(1-w)w=1+1w-1w^{2}$

It can be seen that for $w=(1+i)/2$ , the above pair of functions is equivalent to the IFS formulation of the Heighway dragon. That is, the Heighway dragon, iterated to a certain iteration, describe the set of all Littlewood polynomials up to a certain degree, evaluated at the point $w=(1+i)/2$ . Indeed, when plotting a sufficiently high number of roots of the Littlewood polynomials, structures similar to the dragon curve appear at points close to these coordinates.^[7]^[8]^[9]

References

^ ^a ^b ^c ^d Tabachnikov, Sergei (2014), "Dragon curves revisited", The Mathematical Intelligencer, 36 (1): 13–17, doi:10.1007/s00283-013-9428-y, MR 3166985, S2CID 14420269
^ Edgar, Gerald (2008), "Heighway's Dragon", in Edgar, Gerald (ed.), Measure, Topology, and Fractal Geometry, Undergraduate Texts in Mathematics (2nd ed.), New York: Springer, pp. 20–22, doi:10.1007/978-0-387-74749-1, ISBN 978-0-387-74748-4, MR 2356043
^ Edgar (2008), "Heighway’s Dragon Tiles the Plane", pp. 74–75.
^ Edgar (2008), "Heighway Dragon Boundary", pp. 194–195.
^ Knuth, Donald (1998). "Positional Number Systems". The art of computer programming. Vol. 2 (3rd ed.). Boston: Addison-Wesley. p. 206. ISBN 0-201-89684-2. OCLC 48246681.
^ Bailey, Scott; Kim, Theodore; Strichartz, Robert S. (2002), "Inside the Lévy dragon", The American Mathematical Monthly, 109 (8): 689–703, doi:10.2307/3072395, JSTOR 3072395, MR 1927621.
^ ^a ^b "The n-Category Café".
^ "Week285".
^ "The Beauty of Roots". 2011-12-11.

External links

[tabachnikov-1] Tabachnikov, Sergei (2014), "Dragon curves revisited", The Mathematical Intelligencer, 36 (1): 13–17, doi:10.1007/s00283-013-9428-y, MR 3166985, S2CID 14420269

[2] Edgar, Gerald (2008), "Heighway's Dragon", in Edgar, Gerald (ed.), Measure, Topology, and Fractal Geometry, Undergraduate Texts in Mathematics (2nd ed.), New York: Springer, pp. 20–22, doi:10.1007/978-0-387-74749-1, ISBN 978-0-387-74748-4, MR 2356043

[3] Edgar (2008), "Heighway’s Dragon Tiles the Plane", pp. 74–75.

[4] Edgar (2008), "Heighway Dragon Boundary", pp. 194–195.

[Knuth2-5] Knuth, Donald (1998). "Positional Number Systems". The art of computer programming. Vol. 2 (3rd ed.). Boston: Addison-Wesley. p. 206. ISBN 0-201-89684-2. OCLC 48246681.

[6] Bailey, Scott; Kim, Theodore; Strichartz, Robert S. (2002), "Inside the Lévy dragon", The American Mathematical Monthly, 109 (8): 689–703, doi:10.2307/3072395, JSTOR 3072395, MR 1927621.

[ncafe-7] "The n-Category Café".

[8] "Week285".

[9] "The Beauty of Roots". 2011-12-11.

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

v t e Fractals
Characteristics	Fractal dimensions Assouad Box-counting Higuchi Correlation Hausdorff Packing Topological Recursion Self-similarity
Iterated function system	Barnsley fern Cantor set Koch snowflake Menger sponge Sierpiński carpet Sierpiński triangle Apollonian gasket Fibonacci word Space-filling curve Blancmange curve De Rham curve Minkowski Dragon curve Hilbert curve Koch curve Lévy C curve Moore curve Peano curve Sierpiński curve Z-order curve String T-square n-flake Vicsek fractal Gosper curve Pythagoras tree Weierstrass function
Strange attractor	Multifractal system
L-system	Fractal canopy Space-filling curve H tree
Escape-time fractals	Burning Ship fractal Julia set Filled Newton fractal Douady rabbit Lyapunov fractal Mandelbrot set Misiurewicz point Multibrot set Newton fractal Tricorn Mandelbox Mandelbulb
Rendering techniques	Buddhabrot Orbit trap Pickover stalk
Random fractals	Brownian motion Brownian tree Brownian motor Fractal landscape Lévy flight Percolation theory Self-avoiding walk
People	Michael Barnsley Georg Cantor Bill Gosper Felix Hausdorff Desmond Paul Henry Gaston Julia Niels Fabian Helge von Koch Paul Lévy Aleksandr Lyapunov Benoit Mandelbrot Hamid Naderi Yeganeh Lewis Fry Richardson Wacław Sierpiński
Other	Coastline paradox Fractal art List of fractals by Hausdorff dimension The Fractal Geometry of Nature (1982 book) The Beauty of Fractals (1986 book) Chaos: Making a New Science (1987 book) Kaleidoscope Chaos theory

v t e Mathematics of paper folding
Flat folding	Big-little-big lemma Crease pattern Huzita–Hatori axioms Kawasaki's theorem Maekawa's theorem Map folding Napkin folding problem Pureland origami Yoshizawa–Randlett system
Strip folding	Dragon curve Flexagon Möbius strip Regular paperfolding sequence
3d structures	Miura fold Modular origami Paper bag problem Rigid origami Schwarz lantern Sonobe Yoshimura buckling
Polyhedra	Alexandrov's uniqueness theorem Flexible polyhedron (Bricard octahedron, Steffen's polyhedron) Net Blooming Common net Source unfolding Star unfolding
Miscellaneous	Fold-and-cut theorem Lill's method
Publications	Geometric Exercises in Paper Folding Geometric Folding Algorithms Geometric Origami A History of Folding in Mathematics Origami Polyhedra Design Origamics
People	Roger C. Alperin Margherita Piazzola Beloch Yan Chen Robert Connelly Erik Demaine Martin Demaine Rona Gurkewitz David A. Huffman Tom Hull Kôdi Husimi Humiaki Huzita Toshikazu Kawasaki Robert J. Lang Anna Lubiw Jun Maekawa Kōryō Miura Joseph O'Rourke Tomohiro Tachi Eve Torrence