Hutchinson's Theorem (1981)
 |
| See below for code |
A fixed point of any map $f:X\to X$ is a point $x\in X$ such that $f(x) = x$. If $X=\mathbb{R}^N$ we can define a contraction as a map $f$ which brings pairs of points closer together, i.e. we can say $f$ is a contraction if there's some $\lambda < 1$ such that for any $x_1,x_2$ we have $|f(x_1)-f(x_2)| < \lambda |x_1-x_2|$. Now, it's easy to see that if $f$ is a contraction then it has a unique fixed point. All you have to do is note that for any $x$ the following sequence converges
$$x, f(x), f^2(x), f^3(x), ...
$$
Why's that? Well if we let $\epsilon = |x-f(x)|$ then $\epsilon\lambda^{n-1}$ is an upper bound for the distance between the $n^{th}$ and $n+1^{th}$ members of the sequence. Since $\sum \epsilon\lambda^n$ converges we know that the sequence above converges too, and the thing it converges to must be a fixed point of $f$. We know the fixed point is unique because if there were two then $f$ would simultaneously leave the distance the same and make it smaller!
Hutchinson's theorem does the same thing but with shapes instead of points in $\mathbb{R}^N$. It specifies a map which takes shapes to shapes, and finds a shape that is the unique fixed point of that map. To do this we first need to generalize the concepts used above.
A metric space is any set $X$ with a "distance metric" $d:X^2\to\mathbb{R}$ with the following properties for all $x_1,x_2,x_3$
- $d(x_1,x_2) \ge 0$ with equality if and only if $x_1= x_2$
- $d(x_1,x_2) = d(x_2,x_1)$
- $d(x_1,x_2) + d(x_2,x_3) \ge d(x_1,x_3)$
The metric space is complete if any sequence $x_i$ converges whenever $\sum_{i=1}^{n} d(x_i,x_{i+1})$ is bounded. A contraction is any map $f:X\to X$ where there is a $\lambda <1$ that satisfies $d(f(x_1),f(x_2)) \lt \lambda d(x_1,x_2)$ for all $x_1,x_2$.
It's easy to show that $\mathbb{R}^N$ is a complete metric space$^\dagger$ using the metric $d(x_1,x_2) = | x_1 - x_2|$. And when we showed that every contraction of $\mathbb{R}^N$ has a unique fixed point, we only used the fact that it is a complete metric space. It follows that any contraction of any complete metric space $X$ also has a unique fixed point. The next step is to define an alternative metric space, one whose elements are shapes instead of points.
A subset $C$ of a metric space $(X,d)$ is closed if every sequence $x_i \in C$ that converges in $X$ also converges in $C$. It's bounded if there's an upper limit for distances between elements of $C$, and it's compact if it is both closed and bounded. The compact subsets of a metric space $X$ themselves form a metric space $Y$, with metric $d(C_1,C_2)$ defined as the largest distance between a point on one of the sets and its nearest neighbour on the other one. It's rote work to show that the space of compact subsets of a complete metric space with this metric is itself complete.
All we need to do now is to state the theorem, as it follows immediately from the fact that the compact subsets of a complete space form a complete space.
Hutchinson's Theorem
Suppose we have a finite number of contractions $f_1, f_2, ..., f_k$ of a complete metric space $X$, and suppose $Y$ is the metric space of compact subsets of $X$. This induces a contraction $F:Y\to Y$ where $F(C) = \bigcup f_i(C)$ and there is a unique compact set $C$ such that $C =F(C)$.
Examples
The following code finds the fixed point $C$ in the special cases where $X = \mathbb{R}^2$ and the $f_i$ are the contractions which give rise to:
- The Von Koch Snowflake curve
- The Sierpinski Gasket
- The Menger Sponge
- The Dragon Curve
#!/usr/bin/env python3 import matplotlib.pyplot as plt from matplotlib.collections import PatchCollection def buildFractal(mappings, polygons, iters=5): for i in range(iters): polygons = [ [m(x,y) for x,y in p] for p in polygons for m in mappings] return polygons def plotFractal(fractal, **kw): ax = plt.gca() patches=[] for polygon in fractal: patches.append(plt.Polygon(polygon)) ax.add_collection(PatchCollection(patches, **kw)) ax.set_aspect('equal') if __name__ == '__main__': c = 1/2 s = (3**0.5)/2 r = 2**0.5 plt.ion() fig,axes = plt.subplots(2,2) # Von Koch Snowflake Curve plt.sca(axes[0][0]) plotFractal( buildFractal((lambda x,y:(x/3,y/3), lambda x,y:((c*x-s*y)/3+1/3,(c*y+s*x)/3), lambda x,y:((c*x+s*y)/3+1/2,(c*y-s*x)/3+s/3), lambda x,y:(x/3+2/3,y/3)), [[(0,0),(1,0)]], iters=6), color='white', edgecolor='black' ) # Sierpinksi Gasket plt.sca(axes[0][1]) plotFractal( buildFractal((lambda x,y: (x/2,y/2), lambda x,y: (x/2+1/2,y/2), lambda x,y: (x/2+1/4,y/2+s/2)), [[(0,0),(1,0),(1/2,s)]], iters=6), color='white', edgecolor='black' ) # Menger Sponge plt.sca(axes[1][0]) plotFractal( buildFractal((lambda x,y: (x/3,y/3), lambda x,y: (x/3+1/3,y/3), lambda x,y: (x/3+2/3,y/3), lambda x,y: (x/3,y/3+1/3), lambda x,y: (x/3+2/3,y/3+1/3), lambda x,y: (x/3,y/3+2/3), lambda x,y: (x/3+1/3,y/3+2/3), lambda x,y: (x/3+2/3,y/3+2/3)), [[(0,0),(1,0),(1,1),(0,1)]], iters=5), color='black', edgecolor='black' ) # Dragon Curve plt.sca(axes[1][1]) plotFractal( buildFractal((lambda x,y:((x+y)/2,(y-x)/2), lambda x,y:((-x+y)/2+1,(-y-x)/2)), [[(0,0),(1,0),(1,1)]], iters=16), color='black', edgecolor='black' ) plt.autoscale() for row in axes: for ax in row: ax.axis('off') plt.tight_layout()
FOOTNOTES
- $\dagger$ $\mathbb{R}$ is complete axiomatically, and the completeness of $\mathbb{R}^N$ follows from that. The axiom is often phrased as every non-empty set of reals that is bounded above has a least upper bound, but it's easy to show this is equivalent to completeness. Without the completeness axiom the reals are not uniquely defined, as the other axioms are satisfied by every subfield of $\mathbb{R}$.
Comments
Post a Comment