Mark
Dow
Geek
art
Simple recursive systems
and fractal patterns
Thue-Morse
sequence tilings and patterns
Visually interesting two dimensional tilings can be
constructed by
abstracting the one dimensional Thue-Morse sequence to two dimensions
and choosing compatible motifs. The Thue-Morse sequence's locally
symmetric, highly repetative and redundant but non-periodic
properties result in tilings with the visual impression of order
within disorder.
Ted Bell motivated me to write a program for
constructing these tilings after I showed him a short description of
the
Thue-Morse
sequence
from a book (chapter 30 of
M.R. Schroeder
"
Number
Theory in Science and
Communication", Springer, Third edition 1997). Ted realized and
sketched
the basic tiling
scheme, a natural dual division of the plane based on the tiling, and a
higher order pattern that emerged. He also devised and made a sketch of
this Gray code
Thue-Morse
binary fractal pattern.
Since then we have thought about how to find interesting motifs (motifs
such that edges match in nontrivial ways), variations of the basic
tiling pattern, and extensions to sequences with more than two symbols.
Neigborhood dependent Thue-Morse tilings
The Thue-Morse sequence
The Thue-Morse
sequence
is a non-periodic sequence of any two symbols:
a b b a b a a b b a a b a b b
a b a a b a b b a a b b a b a a b ...
or
There are several methods for constructing the sequence. One algorithm
involves repeated concatenation;
{
Start with one symbol (a, or a
black square) and concate its
complementary symbol string (b, or a white square).
Repeat this complementary concatenation using the result as the input
to the next repetion.
}
Another method is more general - a recursive symbol replacement system.
Starting with a, replace a with a b
and b with b a,
and then repeat
these replacement rules indefinitely, always using the results as the
input for the next generation:
a;
{ a -> a b }, { b -> b a }
or
Both algorithms result in the same series of generations of symbol
strings:
generation 0:
a
generation 1:
a b
generation 2:
a b b a
generation 3:
a b b a b a
a b
generation 4:
a b b a b a
a b b a a b a b b a
generation 5:
a b b a b a
a b b a a b a b b a b a a b a b b a a b b a b a a b
.
.
.
All
sub-sequences (sets of
adjacent symbols) will reoccur in this sequence. This can be
demonstrated using the concatenation algorithm; since the complement of
every sub-sequence is repeated, after two repetitions the original
sub-sequence (the complement of the complement) will occur.
But any sub-sequence never reoccurs at the same spacing throughout the
sequence. So the sequence is non-periodic, but filled with redundant
sub-sequences.
Also, some substrings never
reoccur adjacent to each other. For example a a a a and a b b a a b b a doesn't occur
anywhere in the sequence. In fact, three of the same symbols, or
three sets of
any sub-sequence, in a row (e.g. a a a
and b b b, or b b a a b b) doesn't occur. This
property is called "cube-free".
[To Do: Overlap free, WWa also doesn't occur, see Mathworld and
Wikipedia]
Construction
of a 2-D Thue-Morse pattern
A 2-D Thue-Morse pattern, where each row and column
is a Thue-Morse
sequence, can also be formed by a recursive concatenation as described
above. The complement of an array of symbols is concatenated to itself,
first in one direction and then the other:
1st generation
(corresponding to :
a b ...
b a
... )
The two symbols, distinguished by color (black and white). |
2nd generation (corresponding to :
a b b a ...
b a a b
b a a b
a b b a
... )
Note that rows and columns are all Thue-Morse sequences. |
3rd generation
Odd generations are not bilaterally symmetric (horizontally or
vertically), but are symmetric across the diagonals. |
4th generation
Even generations are bilaterally symmetric as well as symmetric across
the diagonals. |
8th order, click for large version |
A recursive symbol replacement system that
results in the same 2-D Thue-Morse pattern:
|
 |
... |
For examples and discussion of similar symbol
replacement systems, see "Simple
recursive systems and simple fractal patterns".
[To Do: L-shaped patterns don't occur in 2-D, and other properties.]
All of the tilings on this page are formed by
replacing these 2-D
arrays of symbols with square or rectangular motifs; the motifs
are used as symbols. Many of the tilings are dual: the motifs of the
two tiles
are geometrically related. The two
motifs can be related by a rotation, mirroring, luminance inversion, or
any different coloring of the same pattern.
Double
chain
Chains are one dimensional analogs of chainmail weaves.
There is less freedom in one dimension, and I thought all 1-D
interlinkage would be periodic. But here's an example of a nontrivial
non-periodic chain, a simple replacement of the Thue-Morse sequence
with a universal motif pair.
The recursive replacement system of a single motif and its mirror image.
|
The 5th generation chain. All links are 1, 3, or 5 units long.
The chain colored to highlight the two chains, red and blue.
Although the two chains are interlinked, they are independent in that,
when taught, one can be shifted independent of the other.
The chain colored to highlight the links. The two chains are
distinguished as red-orange-yellows and blue-greens.
|
Redundant
Quadrapii
A basis motif, or tile, formed of logarithmic spirals with a pitch of
pi/4. See Logarithmic
spirals, waves and tilings for details and Matlab code for
generating logarithmic spiral divisions of the plane. |
Two square motifs, side-by-side, formed by a combination of 2x4 basis
motifs rotated and
mirrored. Note that the right set of 2x2 basis motifs are a 90
degree
rotation of the left set of 2x2 basis motifs.
The recursive replacement system that results in the 2-D Thue-Morse
pattern.
|
Fourth order Thue-Morse tiling of the motif pair. |
The tiling, colored by shapes of contiguous regions. Shape relief
rendering done with Matlab
morphological erosion and Space
Software.
[To Do: Add example volume and Matlab erosion code.]
|
Orthologia
An imaginary beast, a bugit, based on a
logarithmic
spiral similarity tiling and colored by the Thue-Morse sequence. [To
Do: Context
of a square tesselation and Thue-Morse coloring.]
The basis pattern (at left) is an infinite division
of the plane by logarithmic spirals, a binary
fractal. It's a checkerboard division (8x2) of the
plane by logarithmic spirals with a pitch of +/- pi/4 radians. The
checkerboard is colored (orthogonal to the contours) by repetition of
the third generation
(23 = 8 element) Thue-Morse sequence
[0 1 1 0 1 0 0 1], where 1 and 0 represent black and white. The
relative phase between the two sets of opposite
chirality spirals rotates through pi/2 radians; in this example the
phase of one set is fixed.
There is a nice bi-stable perception illusion in the
animation (above left): when I
first see it, I percieve a wholistic pattern rotating CW and shrinking.
But after a short time, I see half the contours as fixed, and the other
half rotating (with no shrinking). Try fixating on a single edge point
to experience the second percept.
Also see description,
notes and code for the Orthologia images, and Logarithmic
spirals, waves and tilings for details and Matlab code for
generating logarithmic spiral divisions of the plane.
Four knot
A 2-D Thue-Morse pattern where the symbols
are
replaced by a motif that visually connects all adjacent symbols. The
result is a woven pattern, with each "strand" forming a simple closed
loop.
The two square motifs, side-by-side, where each motif is a pi/2
rotation of the other.
The recursive replacement system that results in the 2-D Thue-Morse
pattern.
|
 Oblique
viewpoint rendering of the 3-D motif used to construct Thue-Morse chain
images. (Stereo pair, cross-view.)
Constructed and rendered with Space
Software, using a single chiral spline segment, rotated/mirrored
four times. (Credit to Greg Scott for writing the spline code.)
curveA_b_4.vol.gz
(2 MB) |
The Thue-Morse tiling. |
The pattern after a pi/4 rotation and coloring of connected
elements -- only those elements that are closed on this portion of the
potentially infinite tiling.
|
Matlab command (for the
Thue-Morse tiling of this motif pair):
Why this works (nested circuits in this weave
pattern, colored by connectivity in the left image) is a mystery
to me. How would a larger Thue-Morse pattern with the same motifs be
connected? I designed the motif, shading and coloring, but I didn't
design the pattern; I found it.
Thue-Morse tilings of other motifs
3-D Thue-Morse pattern
(Thue-Morse cube)
A 3-D (or higher dimensional) Thue-Morse pattern is
formed by extension
of the one and two dimensional algorithms (see above). The recursive
symbol replacement system is represented as:
where the symbols (black, white squares) occupy a cube's coordinate
volume elements.
|
 |
| A surface rendering (sterero
pair, cross view) of the 3-D Thue-Morse
pattern, or Thue-Morse cube, using empty and filled space as
symbols.
Third generation, 8x8x8. |
A 2-D slice through a
symmetry plane of the 3-D Thue-Morse cube (at left). Seventh
generation, 128x128x128. The long range self-similar structure of the
Thue-Morse pattern is more
easily seen in this slice than in the 2-D square system's pattern.
Notice the slightly lighter/darker trapezoids that repeat at different
scales; it is a discrete similarity tiling. |
[To Do: Reference and link to 3-D
L-system code. Include example
volumes.]
Thue-Morse rings
The algorithm for generating these two
figures, a discrete and continuous representation of the
Thue-Morse sequence, are nealy identical.
|
 |
 |
| Each sequential generation of
the Thue-Morse sequence in concentric rings, starting at the
horizontal. The first generation is at the center. The black and
white patterns are identical after a half
turn about the center. It is a binary
fractal. |
Each circle, centered at the
patterns singular point, is patterned as the first elements of a
Thue-Morse sequence, a longer part of the sequence at larger radii. The
second generation is at the center. The
prominant aliasing is due to the nature of the sequence, its
arithmetic subsequences and how they interact with the integer lattice
of the grid. |
Rendering of continuous rings
with a range of generation offsets.
(stereo pair, cross-view) |
MATLAB commands:
>>
Thue_Morse_rings( 100, 9, 1.0, true, true ); % Discrete version
above.
% Harcoded information:
strFilename = 'Thue-Morse_rings.png';
bDiscrete = true;
nSize = 2048;
flC = nSize/2;
>> Thue_Morse_rings( 100, 13, 2.0, true, true ); % Continuous version
above.
% Harcoded information:
strFilename = 'Thue-Morse_airfoil_2.png';
bDiscrete = false;
nSize = 2048;
flC =
1300;
% ~10.2*nSize/16 - 1;
See Thue_Morse_rings.m header for hardcoded
parameters of variations and other details.
Thue-Morse foldings
How might a Thue-Morse (TM) sequence
occur through physical processes?
Might something like a linear chain of algae, where two characteristics
are TM along the chain, form naturally? Or a non-periodic crystal with
molecular sheet structure in a TM sequence?
Repeated folding is a recursive process, and
sequences related to the TM sequences can be encoded in the direction
of folds and the layering of the folds. This is an example of a maze
derived from such a folding. Traversing the maze from one red dot to
the other crosses the horizontal midline in a TM sequence, where up and
down (direction of crossing) are the symbols of the TM sequence.
See Thue-Morse
sequence foldings for how this was constructed and some discussion.
Programs and code for general
Thue-Morse tilings, MATLAB
The MATLAB code and
resouces for generating these Thue-Morse systems, and any one or
two dimensional L-system on
a square grid are available at L-system
program
and code. Also see the work-in-progress "Simple
recurrent sequences and simple fractal patterns"
for related examples.
The MATLAB syntax for generating the 2-D Thue-Morse
pattern is:
>>
imageMatrix = L_system_tiling(
'TM', [ng], 2, 1, 0, 'motif.jpg', 0, [0 1; 1 0], [1 0; 0
1] );
where ng is the number of
generations desired, and motif.jpg
is an image file containing a pair of side-by-side motifs.
Many of these tilings are formed by replacing
each
symbol of a Thue-Morse pattern with a square (or rectangular)
image. This can be done manually using copy/paste in an image editor,
but for large tilings it is convenient to automate the process.
The one
dimensional Thue-Morse sequence can be easily generated
using MATLAB's
syntax. Using [0,1] as the symbols, a sequence that is
2n elements long is generated (using the logical NOT
operator "~") with the
code:
{
% Construct a Thue-Morse vector of
length 2^n:
vctTM = 0; %
initial element [0,1]
for i
= 1 : n % where n is the number of generations
% Double the length, using the compliment of
the original array element(s) as the new element(s).
vctTM( length(
vctTM ) + 1 : 2*length( vctTM ) ) = ~vctTM;
end
}
This can be extended to the two dimensional
Thue-Morse pattern, where each row and column is a Thue-Morse sequence.
[To Do: Show this code too.]
Program and code for
neigborhood
dependent Thue-Morse tilings, MATLAB
Some of
these tilings are neighborhood
dependent: the square (or rectangular) image that replaces the symbol
depends on what symbols surround the symbol that is replaced. For the
Thue-Morse pattern there are a only a small set of possible nearest
neighbor patterns. [To Do: Illustrate the six nearest neighbor
configuations and rotations.]
A Matlab program used for a few special cases:
The program is not general as it only handles a
couple kinds of neighborhood relationships and possible replacement .
How it operates and the reasoning behind the particular orderings is
not obvious, even to me.
Example usage (see file header for details):
>> imageMatrix = Thue_Morse_tiling( [ng],'motif.jpg' , 2 );
where ng is the number of generations desired, and motif.jpg is an image file containing a motif
specified by a 2x4 set of
basis elements.
The code is reasonably clean, but a bit hard to
follow, not very flexible or well documented.
[ To Do: Ideas for the future ]
What does the autocorrelation of TM,
TM(t), look like as the string length goes to infinity?
References
OEIS A010060
C. A. Pickover, Wonders of Numbers, Adventures in Mathematics, Mind
and
Meaning, Chapter
17, 'The Pipes of Papua,' Oxford University Press,
Oxford, England, 2000, pages 34 - 38.
C. A. Pickover, A Passion for Mathematics, Wiley, 2005; see p.
60.
The paper discusses the terminology
behind batik crafting and showed the aspects of self-similarity in its
ornaments. Even though a product of batik cannot be reduced merely into
its decorative properties, it is shown that computation can capture
some interesting aspects in the batik-making ornamentation. There are
three methods that can be exploited to the generative batik, i.e.:
using fractal as the main source of decorative patterns, the hybrid
batik that is emerged from the acquisition of L-System Thue-Morse
algorithm for the harmonization within the grand designs by using both
fractal images and traditional batik patterns, and using the random
image tessellation as well as previous tiling algorithms for generating
batik designs. The latest can be delivered by using a broad sources of
motifs and traditionally recognized graphics. The paper concludes with
certain aspects that shows how the harmony of traditional crafting and
modern computation could bring us a more creative aspects of the
beautiful harmony inherited in the aesthetic aspects of batik crafting.
We investigate from a theoretical point
of view the photonic properties of a two dimensional photonic aperiodic
crystal. These structures are obtained by removing the lattice points
from a square arrangement, following the inflation rules emerging from
the Thue-Morse sequence. The photonic bandgap analysis is performed by
means of the density of states calculation. The mechanism of bandgap
formation is investigated adopting the single scattering model, and the
Mie scattering. The electromagnetic field distribution can be
represented as quasi-localized states. Finally, a generalized method to
obtain aperiodic photonic structures has been proposed.
------------------------------------
There are no restrictions on use of the images or code
on this page. Claiming to be the originator of the material,
explicitly or implicitly, is bad karma. A link (if appropriate), a note to dow[at]uoregon.edu, and credit are appreciated but not
required.
Comments are welcome (dow[at]uoregon.edu).
Oblique
viewpoint rendering of the 3-D motif used to construct Thue-Morse chain
images. (Stereo pair, cross-view.)
