Discrete self-similar fractals

Discrete Self-Similar Fractals

Due to their complex, aperiodic nature, discrete self-similar fractals have provided an interesting set of infinite shapes to explore, and because of their discrete nature, a consequence of their bottom-up recursive definition, this class of fractals is particularly suited to be investigated with respect to tile assembly models such as the aTAM, which is inherently confined to the integer lattice.

Definition: Discrete Self-Similar Fractal

Let \(G=\{g_0, \ldots, g_{k-1}\}\) be a non-empty, connected set of points in \(\mathbb{N}^2\) satisfying the following where \(w\) is the largest \(x\) coordinate of a point in \(G\) plus 1 and \(h\) is the largest \(y\) coordinate plus 1:

• \((0,0) \in G\),
• There exist two points \((x_0,y_0),(x_1,y_1)\in G\) such that \(x_0 = 0\) and \(y_1=0\),
• There exist two points \((x_0,y_0), (x_1,y_1)\in G\) such that \(x_0=0\), \(x_1=w-1\) and \(y_0 = y_1\),
• There exists two points \((x_0,y_0), (x_1,y_1)\in G\) such that \(y_0=0\), \(y_1=h-1\) and \(x_0 = x_1\), and
• there exists at least one point \((x,y)\in\mathbb{N}^2\) with \(0\le x < w\) and \(0\le y < h\) such that \((x,y)\) is not in \(G\).

Define \(F_0 = G\) and, for \(i > 0\), define \(F_i = \left\{F_{i-1} + \left(w^i\cdot x, h^i\cdot y\right) : (x,y)\in G\right\}\) where a set of points \(S\) plus a point \((x,y)\) refers to translation of each point in \(S\) by the vector corresponding to \((x,y)\). Each \(F_i\) is called a stage of the fractal.

\(F = \bigcup_{i\in\mathbb{N}} F_i\) is then called a discrete self-similar fractal with generator \(G\).

Intuitively, discrete self-similar fractals can be thought of as being constructed by iteratively replacing each point in a stage by an entire copy of the generator. The first 5 stages of the Sierpinski triangle DSSF in the figure below illustrate the idea. The conditions for generators assure that the resulting DSSF is connected and not degenerate (i.e. just a point, line, or full quadrant). Condition 2 is for convenience and, along with the fact that the generator is made of points in \(\mathbb{N}^2\) rather than \(\mathbb{Z}^2\), guarantees that the smallest bounding box of the generator has the origin as a corner, conditions 3 and 4 guarantee that copies of the generator placed adjacent to each other will form a connected shape, and condition 5 guarantees that the resulting DSSF is non-trivial (i.e. not a line or the entire quadrant).

First 5 stages of the Sierpinski triangle

First 3 stages of the Sierpinski carpet

Example discrete self-similar fractals. For each, the generator is on the left, and subsequent stages are shown to the right.