Binary fractal images

How can a plane be divided into two equivalent and fractal (self-similar with an infinite number of discontinuities) parts? All contiguous regions must belong to a set of geometrically similar regions (identical after scaling and rotation), and must cover the plane.

This page briefly describes a few non-trivial binary fractals, with variations.

Division by opposite logarithmic spirals, link to

logN, fractal based on our binary numeral system
logN_tally, fractal based on a binary tally numeral system
Thue-Morse Gray code, fractal based on the Thue-Morse sequence with columns that map to Gray code positions
R-tree, a space-filling curve, a fractal division of a topological torus
Chiral star checked, based on a fractal tiling with a fractal tile
Pell dart similarity tiling, based on the silver ratio
Logarithmic spirals, division of the plane by mirrored
Pentakoch, a pentagonal substitution tiling with a fractal tile

[ To Do: Symmetric block replacement L-systems and binary fractals:
L_system_tiling( 'SW', 11, 7, 1, 0, '', 1, [0 0;0 0], [11 12;10 9], [1 0;12 0], [9 0;0 0], [6 10;6 1], [6 6;6 11], [6 6;6 6] );
L_system_tiling('BF8', 11, 3, 1, 0, '', 1, [0 0;0 0], [4 2;0 4], [2 2;2 2] ); ]

logN, a fractal based on our binary numeral system

These examples (image below) are related by logarithmic scaling. Even the two basic forms ("step-wise" and "smooth") are closely related; both can be viewed as binary trees.

The patterns are derived directly from the standard binary numeral system: each pixel column represents a unique number, increasing from left to right, with the top of each portion of the image representing the least significant bit.

Matlab code: logN.m

Algorithmic complexity: < 20 Kbit

The algorithm for each pattern is different -- there are many ways to skin a fractal cat. I chose the one that made sense to me at the time.

Also, see the related logN_tally, below.

logN_11.jpg (2K x 3K, 1 MB)
logN_12.jpg (4K x 6K, 3 MB)
logN_13.jpg (8K x 12K, 10 MB)

...

logN_tally, a fractal algorithm and image based on a binary tally numbering system

This is a discrete power law scaling of the "step-wise" images in logN (above). It represents a tally, or unary numeral system -- each column's amount of black (the numer of pixels filled in) represents a number, increasing left to right.

Matlab code: logN_tally.m

logN_tally_10.jpg (1K x 1K, 27 K)
logN_tally_12.jpg (4K x 4K, 250 KB)
logN_tally_13.jpg (8K x 8K, .9 MB)

...

Thue-Morse Gray code binary fractal and algorithm

    Ted Bell suggested the figure below, while we were experimenting with 2-D Thue-Morse sequence tilings. Each row is a Thue-Morse sequence (with white and black as symbols) with symbols that double in size between rows. The number represented by each column (the number of white pixels, or the binary number encoded in the column's symbols) maps the column's index (0, 1, 2, 3, 4... from left to right) to the Gray code position of that column's index (0, 1, 3, 2, 7, ...).

    This one is 10th generation (2¹⁰ columns). Another rendering of this basic pattern is found in Stephen Wolfram's "A New Kind of Science", page 83, figure b.

    The Gray code, also known as the reflected binary code, forms a Hamiltonian cycle on a hypercube where each bit represents one dimension [To Do: Diagram of cycle on a tesseract.]. Both the Gray code and the Thue-Morse sequence can be generated by a simple recursive replacement system. Here is a description of a system that generates the Thue-Morse sequence.

    Matlab code that produces this pattern, of a given generation: Gray_Thue_Morse.m

Matlab command:
>> im = Gray_Thue_Morse( 10 );

Reference:
Hal Fredricksen, Gray Codes and the Thue-Morse-Hedlund Sequence, J. Comb. Math. and Comb. Computing, 11 (1992), pp. 3-11.

$Gray code Thue-Morse binary fractal$

...

[To Do: Direct comparison of Tally with TM-Graycode]

R-tree, a space-filling curve

The boundary between the black and white regions in the figures below would touch every point on a square if the generating algorithm were repeated ad infinitum. As a topological torus (top-left edge abutting bottom-right, and top-right to bottom left), the black fractal pattern is identical to the white fractal pattern, but for a 180 degree rotation and small shift.

[To Do: construction sequence and system description.]

The boundary is much like other space filling curves, such as the Peano Curve, Hilbert Curve, and Z-order curve, and can be generated by a recursive substitution system, such as an L-system (Lindenmayer system). These curves, and some other space filling curves, can also divide a square and can be closed on a topological torus. With the Peano and Z-order curves the two regions on a topological torus can also be identical in all respects except for a 180 degree rotation. There are many 2-D L-system figures that have this property. But, curiously, it appears to me that the Hilbert curve can't be closed such that there are two identical regions -- on a square, cylinder or torus.

Starting with the "double bar" at left, each subsequent generation is formed by a 2x2 array of the previous generation rotated by pi/2 * [0, 1, 2, 3], in the clockwise cyclic direction.

This diamond is formed from the 7th generation, a rearrangement of the four regions formed by dividing along the diagonals.

Chiral star checked, based on a fractal tiling with a fractal tile

Ted Bell came up with recursive replacement rules that generate a chiral star shaped boundary (Fig. d, below), and these are all riffs on that theme. Only Fig. a is a binary fractal. Click on the images for larger versions.

$Chiral star checked, a binary fractal tiling with a fractal tile$
Figure a: This fractal tiling uses a single fractal prototile and its similar tiles scaled by factors that are a power of two. The image was constructed by filling subregions of the boundary in Fig. b. A quarter rotation of one of the region sets (black or white) is identical to the other region. The left-right and top-bottom edges match (as on a topological torus), forming an infinite tiling with the same single prototile.	Figure b: The boundaries of Figure a can be constructed using an L-system with this square replacement rule set: This system results in a bounded fractal tiling.	Figure c: A different coloring of this boundary (Fig. b) shows that it can be viewed as a four-point chiral star. A portion of the star (purple and dark green) is self-similar to any one quadrant (light and dark green) that forms a smaller star. The boundary within one quadrant can also be formed by an L-system (Fig. d) -- this boundary is a 2 x 2 tiling of the smaller star's boundary.

$Chiral star small boundary, a fractal tiling with a fractal tile$	$Chiral star pointl boundary, a fractal tiling with a fractal tile$
Figure d: This bounded fractal tiling is composed of the same single fractal prototile as all other figures. A 2 x 2 tiling with this motif results in the boundary in Fig. b. These boundaries can be constructed using an L-system with this square replacement rule set: [ Or: Matlab command: >> imOut = L_system_tiling( 'BF', [n_g], 2, 1, 0, '', [ 0 2; 6 4 ], [0 2; 1 4], [1 1; 1 1] ); where [n_g] is the number of generations. ); ]	Figure e: This figure is the basis configuration for the boundaries in Fig. a-f. For example, a 2 x 2 tiling with this motif and its rotations results in the boundary in Fig. d. It is perfectly self-similar, in that any portion its own boundary is composed of scaled copies of the whole and vice-versa. These boundaries can be constructed using an L-system with this square replacement rule set: The rules are the same as the rules for Fig. d, but there is a single element initial condition -- a black square. [ Or: Matlab command: >> imOut = L_system_tiling( 'BF', [n_g], 2, 1, 0, '', 0, [0 2; 1 4], [1 1; 1 1] ); where [n_g] is the number of generations. ); ] Figure g: The L-system algorithms can be seen as adding white to each quadrant recursively.	Figure f: Unlike the other figures, Fig e is strictly self-similar. For example, the star in Fig. d is not repeated at smaller scales, but any one quadrant (Fig. e) is repeated at scales that are powers of two, rotated by quadrant and generation.

Pell dart similarity tiling

    The center is an inverted (or rotated) scaled copy of the whole, and corners of each quadrant are inverted scaled copies of the quadrant.

    The pattern is composed of a single "dart" shape, with a fractal but finite length boundary. The geometry of the shape is derived from Pell numbers, and the edges of the prototile have relative lengths related to the silver ratio. See compound Pell spirals for some construction details, templates and variations.

    The singularities of this pattern occur on a fractal "X" within the image. [To Do: Describe this dust (disconnected) structure as a recursive replacement system.]

Division of the plane by mirrored logarithmic spirals

Division by opposite logarithmic spirals

    Any division of the plane by mirrored logarithmic spirals, colored periodically in both directions, is an example of a binary fractal image. This particular case has two sets of similar regions, one that can be composed of the other. In general, each individual region will not have a fractal boundary.

    Note that any one section of the plane (this example is centered) will not encompass equivalent black and white areas -- there will be more of one color than the other. But considered as an infinite pattern the boundaries and regions are equivalent.

    Will a pair of patterns logically combined, with the centers offset create a binary fractal with two singular points?

    See Logarithmic spirals, waves and tilings for other examples of logarithmic spiral patterns, and code for generating the patterns.

Pentakoch

See Pentakoch by Chaim Goodman-Strauss, a pentagonal substitution tiling that is a binary fractal. Also see Chaim Goodman-Strauss, unpublished notes, works in progress and talks and his papers for material related to substitution tilings.

-----------------------------------
There are no restrictions on use of the images or algorithms and code on this page. Claiming to be the originator of the material, explicitly or implicitly, is bad karma. A link (if appropriate) and credit are appreciated but not required.

Comments are welcome (dow[at]uoregon.edu). Do you know of any more binary fractals using a different algorithm?