Dragon curve

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. 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: 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. • 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. == 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). == 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. == 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| 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. 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. == Variants ==

The dragon curve belongs to a basic set of iteration functions consisting of two lines with four possible orientations at perpendicular angles 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: 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. == See also ==