Difference between revisions of "Discrete self-similar fractals"

From self-assembly wiki
Jump to navigation Jump to search
Line 1: Line 1:
 
==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.  
+
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).
  
 
  {{multiple image
 
  {{multiple image

Revision as of 15:16, 26 June 2024

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.