Difference between revisions of "Discrete self-similar fractals"
(Created page with "==Discrete Self-Similar Fractals== Due to their complex, aperiodic nature, discrete self-similar fractals have provided an interesting set of infinite shapes to explore. {...") |
|||
(2 intermediate revisions by the same user not shown) | |||
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 tile assembly models such as the [[Abstract_Tile_Assembly_Model_(aTAM) | 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 | ||
− | | align = | + | | align = left |
− | | | + | | image_gap = 20 |
| footer = Example discrete self-similar fractals. For each, the generator is on the left, and subsequent stages are shown to the right. | | footer = Example discrete self-similar fractals. For each, the generator is on the left, and subsequent stages are shown to the right. | ||
| image1 = Sierpinski-triangle-5stages.png | | image1 = Sierpinski-triangle-5stages.png | ||
+ | | width1 = 565 | ||
| alt1 = Sierpinski triangle | | alt1 = Sierpinski triangle | ||
| caption1 = First 5 stages of the Sierpinski triangle | | caption1 = First 5 stages of the Sierpinski triangle | ||
| image2 = Sierpinski-carpet-3stages.png | | image2 = Sierpinski-carpet-3stages.png | ||
+ | | width2 = 400 | ||
| alt2 = Sierpinski carpet | | alt2 = Sierpinski carpet | ||
| caption2 = First 3 stages of the Sierpinski carpet | | caption2 = First 3 stages of the Sierpinski carpet |
Latest revision as of 15:17, 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 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).