Classic Iterated Function Systems

Heighway Dragon Cut Points Details

Suppose that in the construction of the Heighway dragon, the initial segment lies along the x-axis from \(x = 0\) to \(x = 1\).

Claim: The cut points for the components to the left of the central component are located at \[\begin{array}{l} x_L(n) = \frac{\sqrt{2}}{3}\,2^{-n/2} \, \cos \left( (n + 1)\frac{\pi}{4} \right) \\ y_L(n) = \frac{\sqrt{2}}{3}\,2^{-n/2}\, \sin \left( (n + 1) \frac{\pi}{4} \right) \\ \end{array}\] for $n \ge 0$, and the cut points for the components to the right of the central component are located at \[\begin{array}{l} x_R(n) = 1 - \frac{\sqrt{2}}{3}\,2^{-n/2} \, \sin \left( (n + 1)\frac{\pi}{4} \right) \\ y_R(n) = \frac{\sqrt{2}}{3}\,2^{-n/2} \, \cos \left( (n + 1)\frac{\pi}{4} \right) \\ \end{array}\] for $n \ge 1$.

The cut points are where each component touches the neighboring components on either side. The figure below shows the central (largest) component enclosed by its convex hull, a 10-sided polygon. The cut point at \((\tfrac{1}{3},\tfrac{1}{3})\) is one of the vertices of this polygon. Starting with the central component, the other components on the left can be obtained by scaling each component by \(1/\sqrt 2\) and rotating by 45° about the origin to get the next component as they spiral towards the origin. The scaling and rotation also moves each cut point to the next cut point (along with the convex hull polygon).

Click the buttons to the left to simulate this scaling and rotation about the origin of the central component to the first component on the left, and then of the first component to the second component on the left. You can also watch the Animated Video to see how the iteration of scaling each component (represented by the convex hull polygon) by \(1/\sqrt 2\) and rotating by 45° also moves each cut point to the next one for both the left and right components.

We now prove the claim for the left cut points by induction. The left cut point for the central component occurs at the point \((\tfrac{1}{3},\tfrac{1}{3})\). Since \[x_L(0) =\frac{\sqrt{2}}{3}\, 2^0\,\cos\left(\frac{\pi}{4}\right) = \frac{\sqrt{2}}{3}\,\frac{\sqrt{2}}{2} = \frac{1}{3}\] \[y_L(0) =\frac{\sqrt{2}}{3}\, 2^0\,\sin\left(\frac{\pi}{4}\right) = \frac{\sqrt{2}}{3}\,\frac{\sqrt{2}}{2} = \frac{1}{3}\] the claim is true for the first cut point on the left of the central component, i.e. for \(n = 0\).

Now assume that the claim is true for the cut point (\(x_L(n),y_L(n))\) to the left of the central component. The matrix corresponding to scaling by \(1/\sqrt 2\) and rotating by 45° about the origin is \[ \begin{bmatrix} \cos{45^\circ} & -\sin{45^\circ} \\ \sin{45^\circ} & \cos{45^\circ} \end{bmatrix} \begin{bmatrix} \frac{1}{\sqrt{2}} & 0 \\ 0 & \frac{1}{\sqrt{2}} \end{bmatrix} = \begin{bmatrix} \frac{\sqrt{2}}{2} & -\frac{\sqrt{2}}{2} \\ \frac{\sqrt{2}}{2} & \frac{\sqrt{2}}{2} \end{bmatrix} \begin{bmatrix} \frac{1}{\sqrt{2}} & 0 \\ 0 & \frac{1}{\sqrt{2}} \end{bmatrix} = \begin{bmatrix} \frac{1}{2} & -\frac{1}{2} \\ \frac{1}{2} & \frac{1}{2} \end{bmatrix} \] Therefore \[\begin{align*} \begin{bmatrix} x_L(n+1) \\ y_L(n+1) \end{bmatrix} &= \begin{bmatrix} \frac{1}{2} & -\frac{1}{2} \\ \frac{1}{2} & \frac{1}{2} \end{bmatrix} \begin{bmatrix} x_L(n) \\ y_L(n) \end{bmatrix} \\ \\ &=\begin{bmatrix} \frac{1}{2} & -\frac{1}{2} \\ \frac{1}{2} & \frac{1}{2} \end{bmatrix} \begin{bmatrix} \frac{\sqrt{2}}{3}\,2^{-n/2} \, \cos \left( (n + 1)\frac{\pi}{4} \right)\\ \frac{\sqrt{2}}{3}\,2^{-n/2}\, \sin \left( (n + 1) \frac{\pi}{4} \right) \\ \end{bmatrix} \\ \\ &=\begin{bmatrix} \frac{\sqrt{2}}{6}\,2^{-n/2}\,\left(\cos \left( (n + 1)\frac{\pi}{4} \right)-\sin \left( (n + 1)\frac{\pi}{4} \right)\right)\\ \frac{\sqrt{2}}{6}\,2^{-n/2}\,\left(\cos \left( (n + 1)\frac{\pi}{4} \right)+\sin \left( (n + 1)\frac{\pi}{4} \right)\right) \end{bmatrix} \\ \\ &=\begin{bmatrix} \frac{\sqrt{2}}{6}\,2^{-n/2}\,\sqrt{2}\cos\left( (n + 1)\frac{\pi}{4}+\frac{\pi}{4} \right) \\ \frac{\sqrt{2}}{6}\,2^{-n/2}\,\sqrt{2}\sin\left( (n + 1)\frac{\pi}{4}+\frac{\pi}{4} \right) \end{bmatrix} \\ \\ &=\begin{bmatrix} \frac{\sqrt{2}}{3} \, 2^{-(n+1)/2} \, \cos \left( (n + 2) \frac{\pi}{4} \right) \\ \frac{\sqrt{2}}{3} \, 2^{-(n+1)/2}\, \sin \left( (n + 2) \frac{\pi}{4} \right) \end{bmatrix} \end{align*} \] where we have used the trig identities \(\sin{A}+\cos{A} = \sqrt{2}\,\sin(A+\frac{\pi}{4})\) and \(\cos{A}-\sin{A} = \sqrt{2}\,\cos(A+\frac{\pi}{4})\) [Trig Proof] in the last step. By induction, the claim for the left cut points is true.

The components to the right of the central component are a copy of all the components to the left of the central component excluding the first component. The following video shows how the red copy of the dragon can be rotated by 90° around the point \((\tfrac{1}{2},\tfrac{1}{2})\) to overlap the blue copy of the dragon. This means that the cut points of the components to the right of the central component can be obtained by rotating all the cut points of the components on the left by 90° around the point \((\tfrac{1}{2},\tfrac{1}{2})\) starting with \(n=1\), i.e. excluding the cut point at \((\tfrac{1}{3},\tfrac{1}{3})\) .

Play/Pause Restore

Therefore the formula for the right cut points for \(n \ge 1\) is given by \[\begin{align*} \begin{bmatrix} x_R(n) \\ y_R(n) \end{bmatrix} &= \begin{bmatrix} \cos(90^\circ) & -\sin(90^\circ) \\ \sin(90^\circ) & \cos(90^\circ) \end{bmatrix} \begin{bmatrix} x_L(n) - \tfrac{1}{2} \\ y_L(n) - \tfrac{1}{2} \end{bmatrix} + \begin{bmatrix} \tfrac{1}{2} \\ \tfrac{1}{2} \end{bmatrix} \\ \\ &= \begin{bmatrix} 0 & -1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} x_L(n) - \tfrac{1}{2} \\ y_L(n) - \tfrac{1}{2} \end{bmatrix} + \begin{bmatrix} \tfrac{1}{2} \\ \tfrac{1}{2} \end{bmatrix} = \begin{bmatrix} -y_L(n) + 1 \\ x_L(n) \end{bmatrix} \\ \\ &= \begin{bmatrix} 1 - \frac{\sqrt{2}}{3}\,2^{-n/2} \, \sin \left( (n + 1)\frac{\pi}{4} \right) \\ \frac{\sqrt{2}}{3}\,2^{-n/2} \, \cos \left( (n + 1)\frac{\pi}{4} \right) \end{bmatrix} \end{align*} \]

A logarithmic spiral is a polar curve of the form \(r = ae^{b\theta}\). It has the property that the curve maintains a constant angle between its tangent and its radius from the origin. The parametric equations are of the form \(x = ae^{b\theta}\cos\theta\) and \(y = ae^{b\theta}\sin\theta.\)

We first find the logarithmic spiral that passes through the left cut points. Let \(\theta_n = (n+1)\frac{\pi}{4}.\) Then \(n = \frac{4}{\pi}\left(\theta_n-\frac{\pi}{4}\right).\) The left cut points satisfy the following formulas. \begin{align*} x_L(n) &= \tfrac{\sqrt{2}}{3}\,2^{-n/2}\,\cos\left((n+1)\tfrac{\pi}{4}\right) = \tfrac{\sqrt{2}}{3}\,e^{-\tfrac{n}{2}\ln2}\cos(\theta_n) \\ &= \tfrac{\sqrt{2}}{3}\,e^{-\tfrac{2}{\pi}\ln2\left(\theta_n-\frac{\pi}{4}\right)}\cos(\theta_n) = \tfrac{\sqrt{2}}{3}\,\sqrt{2}e^{\left(-\tfrac{2}{\pi}\ln2\right)\theta_n}\cos(\theta_n) \\ &=\tfrac{2}{3}\,e^{\left(-\tfrac{2}{\pi}\ln2\right)\theta_n}\cos(\theta_n) \end{align*} \begin{align*} y_L(n) &= \tfrac{\sqrt{2}}{3}\,2^{-n/2}\,\sin\left((n+1)\tfrac{\pi}{4}\right) = \tfrac{\sqrt{2}}{3}\,e^{-\tfrac{n}{2}\ln2}\sin(\theta_n) \\ &= \tfrac{\sqrt{2}}{3}\,e^{-\tfrac{2}{\pi}\ln2\left(\theta_n-\frac{\pi}{4}\right)}\sin(\theta_n) = \tfrac{\sqrt{2}}{3}\,\sqrt{2}e^{\left(-\tfrac{2}{\pi}\ln2\right)\theta_n}\sin(\theta_n) \\ &=\tfrac{2}{3}\,e^{\left(-\tfrac{2}{\pi}\ln2\right)\theta_n}\sin(\theta_n) \end{align*} These are the parametric equations for the polar curve \[r(\theta) = \tfrac{2}{3}\,e^{\left(-\tfrac{2}{\pi}\ln2\right)\theta},\] a logarithmic spiral that passes through the left cut points when \(\theta = (n+1)\frac{\pi}{4}\) for \(n \ge 0.\)

Next we find a shifted logarithmic spiral that passes through the right cut points. We first need to rewrite the formulas for the right cut points using the trig identities \(\sin\left(A+\tfrac{\pi}{4}\right) =-\cos\left(A+\tfrac{3\pi}{4}\right)\) and \(\cos\left(A+\tfrac{\pi}{4}\right) =\sin\left(A+\tfrac{3\pi}{4}\right)\) [Trig Proof]. This gives \[\begin{array}{l} x_R(n) = 1 - \frac{\sqrt{2}}{3}\,2^{-n/2} \, \sin \left( n \frac{\pi}{4} + \frac{\pi}{4} \right) = 1 + \frac{\sqrt{2}}{3}\,2^{-n/2} \, \cos \left( n \frac{\pi}{4} + \frac{3\pi}{4} \right) = 1 + \frac{\sqrt{2}}{3}\,2^{-n/2} \, \cos \left( (n+3) \frac{\pi}{4} \right)\\ y_R(n) = \frac{\sqrt{2}}{3}\,2^{-n/2} \, \cos \left( n \frac{\pi}{4} + \frac{\pi}{4} \right) = \frac{\sqrt{2}}{3}\,2^{-n/2} \, \sin \left( n \frac{\pi}{4} + \frac{3\pi}{4} \right) = \frac{\sqrt{2}}{3}\,2^{-n/2} \, \sin \left( (n+3) \frac{\pi}{4} \right) \end{array}\] Let \(\theta_n = (n+3)\frac{\pi}{4}.\) Then \(n = \frac{4}{\pi}\left(\theta_n-\frac{3\pi}{4}\right).\) The right cut points therefore satisfy \begin{align*} x_L(n)-1 &= \tfrac{\sqrt{2}}{3}\,2^{-n/2}\,\cos\left((n+3)\tfrac{\pi}{4}\right) = \tfrac{\sqrt{4}}{3}\,e^{-\tfrac{n}{2}\ln2}\cos(\theta_n) \\ &= \tfrac{\sqrt{2}}{3}\,e^{-\tfrac{2}{\pi}\ln2\left(\theta_n-\frac{3\pi}{4}\right)}\cos(\theta_n) = \tfrac{\sqrt{2}}{3}\,2\sqrt{2}e^{\left(-\tfrac{2}{\pi}\ln2\right)\theta_n}\cos(\theta_n) \\ &=\tfrac{4}{3}\,e^{\left(-\tfrac{2}{\pi}\ln2\right)\theta_n}\cos(\theta_n) \end{align*} \begin{align*} y_L(n) &=\tfrac{\sqrt{2}}{3}\,2^{-n/2}\,\sin\left((n+3)\tfrac{\pi}{4}\right) = \tfrac{\sqrt{4}}{3}\,e^{-\tfrac{n}{2}\ln2}\sin(\theta_n) \\ &= \tfrac{\sqrt{2}}{3}\,e^{-\tfrac{2}{\pi}\ln2\left(\theta_n-\frac{3\pi}{4}\right)}\sin(\theta_n) = \tfrac{\sqrt{2}}{3}\,2\sqrt{2}e^{\left(-\tfrac{2}{\pi}\ln2\right)\theta_n}\sin(\theta_n) \\ &=\tfrac{4}{3}\,e^{\left(-\tfrac{2}{\pi}\ln2\right)\theta_n}\sin(\theta_n) \end{align*} These are the parametric equations for the polar curve \[r(\theta) = \tfrac{4}{3}\,e^{\left(-\tfrac{2}{\pi}\ln2\right)\theta},\] a logarithmic spiral that when shifted to be centered at \((1,0)\) will pass through the right cut points when \(\theta = (n+3)\frac{\pi}{4}\) for \(n \ge 1.\)

Click on the "play/pause" button to watch the two logarithmic spirals pass through the Heighway dragon cut points.

Play/Pause Restore