This construction can also be described by the following IFS:
|
\({f_1}({\bf{x}}) = \left[ {\begin{array}{*{20}{c}}
{1/2} & { - 1/2} \\
{1/2} & {1/2} \\
\end{array}} \right]{\bf{x}}\) |
scale by \(\frac{1}{{\sqrt 2 }}\), rotate by 45° |
|
\({f_2}({\bf{x}}) = \left[ {\begin{array}{*{20}{c}}
{ - 1/2} & { - 1/2} \\
{1/2} & { - 1/2} \\
\end{array}} \right]{\bf{x}} + \left[ {\begin{array}{*{20}{c}}
1 \\
0 \\
\end{array}} \right]\) |
scale by \(\frac{1}{{\sqrt 2 }}\), rotate by 135° |
Notice that in these four examples, the beginning of \(H_{n+1}\) (shown in green) is the same sequence of letters as \(H_n\), then followed by an R, which is then followed (in brown) by the sequence \(H_n\) in reverse order with R and L interchanged. For example, the reverse of \(H_2\) is LRR, which becomes RLL after interchanging R and L. These are the last 3 letters in \(H_3\).
This recursive pattern holds for all iterations since \[H_{n+1} = f_1(H_n) \cup f_2(H_n)\] as depicted in the following image:
The first function in the iterated function system will just rotate \(H_n\) by 45° (which becomes the green piece in the image above). This will not change the direction of the turn at each corner of \(H_n\), so the first half of \(H_{n+1}\) will have the same sequence of turns as \(H_n\). The second function in the IFS will rotate \(H_n\) by 135° (the brown piece) and then translate horizontally so that the tail of the brown piece joins the tail of the green piece. The two pieces then form a new corner that has a right turn of 90°, so an R must be added to the end of the sequence from \(H_n\). But now the brown piece must be traversed backwards from that of the green piece which reverses the sequence of turns in \(H_n\), and each original right turn in \(H_n\) will now become a left turn, and vice versa. (The IFS will also scale each piece, but this will not affect the direction of each turn.)
In their 1970 paper, Knuth and Davis expressed this relationship (with slightly different notation) as \(H_{n+1} = H_nR\overline{H_n}\) where for a sequence \(S\), \(\overline{S}\) denotes the sequence obtained from \(S\) by writing it backwards and interchanging R and L.
Since \(H_4\) = RRLRRLLRRRLLRLL, we know that \(H_5\) must start with this sequence of turns and must end with \(H_4\) backwards (i.e. LLRLLRRRLLRRLRR) but with R and L swapped (i.e. RRLRRLLLRRLLRLL), with an extra R added in the middle. So
\(H_5 = H_4R\overline{H_4}\) = RRLRRLLRRRLLRLL R RRLRRLLLRRLLRLL
The image below shows \(H_5\) with each segment colored either Red or bLue based on the sequence above. Following the curve starting at the black dot, each Red segment ends with a turn to the right, and each bLue segment ends with a turn to the left (the last segment is not part of the code, but is colored Red since in the next iteration there would be right turn at the end of this segment). Paying attention to the colors, can you trace the curve from end to end?
The curve can be traversed from the left endpoint to the right endpoint in such a way that the curve intersects only at corners and never crosses itself. [Demonstration with \(H_8\) and \(H_{12}\)]
Let the turns at the corners of \(H_n\) be denoted by \(a_i\) for \(1 \le i \le m\) and let the turns at the corners of \(H_{n+1}\) be denoted by \(b_i\) for \(1 \le i \le 2m+1\), where \(m=2^n-1\).
Therefore the odd corners are alternately R, L, R, L, R, L, etc.
The important observation is that in each case, \(H_n\) and \(H_{n+1}\) both turn in the same direction at this common corner. Therefore \(b_{2k}=a_k\) for \(1 \le k \le m\). We know, however, that \(H_{n+1}\) begins with \(H_n\) and therefore \(b_k = a_k\). This means that \(b_{2k} = b_k\) for \(1 \le k \le m\).
These two observations provide an algorithm for how to generate the symbolic code for \(H_n\). For example, here is how it could be done for \(H_4\). Since \(2^4-1=15\), there are 8 odd-numbered corners in \(H_4\).
Write out four alternating pairs of R's and L's, leaving space between them
Now fill space 2 with the value in position 1:
Fill space 4 with the value in position 2:
Fill space 6 with the value in position 3:
Fill space 8 with the value in position 4:
Fill space 10 with the value in position 5:
Fill space 12 with the value in position 6:
Fill space 14 with the value in position 7:
This is a convenient method to do by hand for small values of \(n\). For larger iterations, however, it is not difficult to write a short program to generate the code using the two observations above. [Python example]
Try it!
If \(r\) is odd, then \(k=r\) and \(m=0\). Since the odd-numbered corners are alternately R, L, R, L, R, L, etc., the R's are in position 1, 5, 9, etc., while the L's are in position 3, 7, 11, etc. The R positions are congruent to 1 mod 4 and the L positions are congruent to 3 mod 4.
If \(r\) is even where \(r = k2^m\) and \(k\) is odd, then by the second observation in method 2, the direction of the turn at corner \(r\) is the same as the direction of the turn at corner \(k\) because you can keep dividing the corner number by 2 without changing the direction of the turn. But \(k\) is odd, so now the same argument as above applies to show that the direction of the turn at corner \(k\) is determined by the value of \(k \text{ mod } 4\).
For example, in \(H_{10}\), which has 2047 corners, the direction at turn 2020 is R because \(2020=505 \cdot 2^2\) and \(505 \text{ mod } 4 = 1\).
If \(r\) is expressed as a binary number, the following binary calculation gives an immediate answer about which way the curve turns: if \( ((r \,\& \, -\!r) \lt \lt 1) \; \& \; r = 0\), then the curve makes a right turn at corner \(r\), otherwise it makes a left turn.
Here & is the bitwise AND operator and << is the bitwise left shift operator [Explanation]. With the example of r = 2020 given above, we would have (in binary)| 2020 = | 11111100100 | |
| −2020 = | 00000011100 | |
| 2020 & −2020 = | 00000000100 | |
| (2020 & −2020) << 1 = | 00000001000 | |
| ((2020 & −2020) << 1) & 2020 = | 00000000000 |
Try it!
Position r =
