Classic Iterated Function Systems

Dihedral Group and Sierpinski Relatives

The eight transformations of a square shown below form a finite group called the dihedral group of order 8. Transformations 2, 3, and 4 are counterclockwise rotations by 90°, 180°, and 270° respectively. Transformations 5 and 6 are vertical and horizontal reflections, while transformations 7 and 8 are reflections across the two diagonals of the square.

The following table shows the result of combining one transformation with another. The one down the rows is done first, followed by the one across the columns. If we call the transformations $T_n$ for n = 1, 2, 3, 4, 5, 6, 7, 8 then the table shows the result of the composition $T_c \circ T_r$, where r and c denote row and column.

\[\begin{array}{cc} {} & {\begin{array}{cccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ \end{array}} \\ {\begin{array}{c} 1 \\ 2 \\ 3 \\ 4 \\ 5 \\ 6 \\ 7 \\ 8 \\ \end{array}} & {\boxed{\begin{array}{cccccccc} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ 2 & 3 & 4 & 1 & 8 & 7 & 5 & 6 \\ 3 & 4 & 1 & 2 & 6 & 5 & 8 & 7 \\ 4 & 1 & 2 & 3 & 7 & 8 & 6 & 5 \\ 5 & 7 & 6 & 8 & 1 & 3 & 2 & 4 \\ 6 & 8 & 5 & 7 & 3 & 1 & 4 & 2 \\ 7 & 6 & 8 & 5 & 4 & 2 & 1 & 3 \\ 8 & 5 & 7 & 6 & 2 & 4 & 3 & 1 \\ \end{array}}} \\ \end{array}\]

So, for example, applying a reflection across the lower left to upper right diagonal (#7) followed by a rotation by 270° (#4) is the same as doing a vertical reflection (#5), as illustrated below. Hence $T_5 = T_4 \circ T_7$.

In fact, you only need transformations 2 (rotation by 90°) and 5 (vertical reflection across a horizontal line) to generate the non-identity transformations:

$T_2 = T_2$
$T_3 = (T_2)^2$
$T_4 = (T_2)^3$
$T_5 = T_5$
$T_6 = (T_2)^2 \circ T_5$
$T_7 = T_2 \circ T_5$
$T_8 = (T_2)^3 \circ T_5$

As an example, consider the Sierpinski relative 365. We will take the initial set to be the unit square with vertex at the origin.

The first function (top left) must scale by 1/2 and rotate by 180. As the figure below shows, the square must also be translated 1/2 to the right and up by 1.

\[\begin{aligned} {f_1}({\mathbf{x}}) &= \left[ {\begin{array}{cc} {\cos {{(180)}^ \circ }} & { - \sin {{(180)}^ \circ }} \\ {\sin {{(180)}^ \circ }} & {\cos {{(180)}^ \circ }} \\ \end{array} } \right]\left[ {\begin{array}{cc} {1/2} & 0 \\ 0 & {1/2} \\ \end{array} } \right]{\mathbf{x}} + \left[ {\begin{array}{c} {1/2} \\ {1} \\ \end{array} } \right] \\ &= \left[ {\begin{array}{cc} { - 1/2} & {0} \\ { 0} & { - 1/2} \\ \end{array} } \right]{\mathbf{x}} + \left[ {\begin{array}{c} {1/2} \\ {1} \\ \end{array} } \right] \\ \end{aligned} \]

The second function (bottom left) must scale by 1/2, followed by a reflection across the vertical axis. As the figure below shows, this must then by followed by a translation by 1/2 to the right.

\[\begin{aligned} {f_2}({\mathbf{x}}) &= \left[ {\begin{array}{cc} { - 1} & 0 \\ 0 & 1 \\ \end{array} } \right]\left[ {\begin{array}{cc} {1/2} & 0 \\ 0 & {1/2} \\ \end{array} } \right]{\mathbf{x}} + \left[ {\begin{array}{c} {1/2} \\ 0 \\ \end{array} } \right] \\ &= \left[ {\begin{array}{cc} {-1/2} & {0} \\ {0} & { 1/2} \\ \end{array} } \right]{\mathbf{x}} + \left[ {\begin{array}{c} {1/2} \\ 0 \\ \end{array} } \right] \\ \end{aligned} \]

The third function (bottom right) must scale by 1/2, followed by a reflection across the horizontal axis. The square must then be translated by 1/2 to the right and 1/2 up.

\[\begin{aligned} {f_3}({\mathbf{x}}) &= \left[ {\begin{array}{cc} { 1} & {0} \\ 0 & {-1} \\ \end{array} } \right]\left[ {\begin{array}{cc} {1/2} & 0 \\ 0 & {1/2} \\ \end{array} } \right]{\mathbf{x}} + \left[ {\begin{array}{c} {1/2} \\ {1/2} \\ \end{array} } \right] \\ &= \left[ {\begin{array}{cc} {1/2} & {0} \\ {0} & { -1/2} \\ \end{array} } \right]{\mathbf{x}} + \left[ {\begin{array}{c} {1/2} \\ {1/2} \\ \end{array} } \right] \\ \end{aligned} \]

This IFS produces the following Sierpinski relative.

Watch an animated video of the construction of relative 365 using the transformations 3, 5, and 6 of the dihedral group.