Discrete self-similar fractals

From self-assembly wiki
Revision as of 15:16, 26 June 2024 by \('"2\)'"7
(\(1) \)2 | \(3 (\)4) | \(5 (\)6)
Jump to navigation Jump to search

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 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).

Sierpinski triangle
First 5 stages of the Sierpinski triangle
Sierpinski carpet
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.