1.4 Chapter Notes

1 Iterated Function Systems

$\newcommand{\footnotename}{footnote}$ $\def \LWRfootnote {1}$ $\newcommand {\footnote }[2][\LWRfootnote ]{{}^{\mathrm {#1}}}$ $\newcommand {\footnotemark }[1][\LWRfootnote ]{{}^{\mathrm {#1}}}$ $\let \LWRorighspace \hspace $ $\renewcommand {\hspace }{\ifstar \LWRorighspace \LWRorighspace }$ $\newcommand {\TextOrMath }[2]{#2}$ $\newcommand {\mathnormal }[1]{{#1}}$ $\newcommand \ensuremath [1]{#1}$ $\newcommand {\LWRframebox }[2][]{\fbox {#2}} \newcommand {\framebox }[1][]{\LWRframebox } $ $\newcommand {\setlength }[2]{}$ $\newcommand {\addtolength }[2]{}$ $\newcommand {\setcounter }[2]{}$ $\newcommand {\addtocounter }[2]{}$ $\newcommand {\arabic }[1]{}$ $\newcommand {\number }[1]{}$ $\newcommand {\noalign }[1]{\text {#1}\notag \\}$ $\newcommand {\cline }[1]{}$ $\newcommand {\directlua }[1]{\text {(directlua)}}$ $\newcommand {\luatexdirectlua }[1]{\text {(directlua)}}$ $\newcommand {\protect }{}$ $\def \LWRabsorbnumber #1 {}$ $\def \LWRabsorbquotenumber "#1 {}$ $\newcommand {\LWRabsorboption }[1][]{}$ $\newcommand {\LWRabsorbtwooptions }[1][]{\LWRabsorboption }$ $\def \mathchar {\ifnextchar "\LWRabsorbquotenumber \LWRabsorbnumber }$ $\def \mathcode #1={\mathchar }$ $\let \delcode \mathcode $ $\let \delimiter \mathchar $ $\def \oe {\unicode {x0153}}$ $\def \OE {\unicode {x0152}}$ $\def \ae {\unicode {x00E6}}$ $\def \AE {\unicode {x00C6}}$ $\def \aa {\unicode {x00E5}}$ $\def \AA {\unicode {x00C5}}$ $\def \o {\unicode {x00F8}}$ $\def \O {\unicode {x00D8}}$ $\def \l {\unicode {x0142}}$ $\def \L {\unicode {x0141}}$ $\def \ss {\unicode {x00DF}}$ $\def \SS {\unicode {x1E9E}}$ $\def \dag {\unicode {x2020}}$ $\def \ddag {\unicode {x2021}}$ $\def \P {\unicode {x00B6}}$ $\def \copyright {\unicode {x00A9}}$ $\def \pounds {\unicode {x00A3}}$ $\let \LWRref \ref $ $\renewcommand {\ref }{\ifstar \LWRref \LWRref }$ $ \newcommand {\multicolumn }[3]{#3}$ $\require {textcomp}$ $\newcommand {\intertext }[1]{\text {#1}\notag \\}$ $\let \Hat \hat $ $\let \Check \check $ $\let \Tilde \tilde $ $\let \Acute \acute $ $\let \Grave \grave $ $\let \Dot \dot $ $\let \Ddot \ddot $ $\let \Breve \breve $ $\let \Bar \bar $ $\let \Vec \vec $ $\renewcommand {\vec }{\boldsymbol }$ $\newcommand {\Edge }{\ensuremath {\,\textemdash \,}}$ $\newcommand \Const [1]{\text {\textsf {#1}}}$ $\DeclareMathOperator {\lerp }{lerp}$ $\DeclareMathOperator {\bitlen }{bitlen}$ $\DeclareMathOperator {\sign }{sign}$ $\newcommand {\I }{\mathrm {i}}$ $\newcommand \AND {\mathbin {\&}}$ $\newcommand \OR {\mathbin {|}}$ $\newcommand \XOR {\mathbin {{}^{\wedge }}}$ $\newcommand \shl {\ll }$ $\newcommand \shr {\ggg }$ $\newcommand \asr {\gg }$ $\newcommand \NOT {\ensuremath {\mathord {\sim }}}$ $\newcommand {\isep }{\mathrel {{.}\,{.}}}$ $\newcommand {\Id }[1]{\mathit {#1}}$ $\newcommand {\const }[1]{\mathsf {#1}}$ $\newcommand {\algorithmname }[1]{\text {\textsc {#1}}}$ $\newcommand {\bits }[1]{\text {#1}}$ $\newcommand {\hexa }[1]{\mathtt {0x#1}}$ $\newcommand {\num }[1]{#1}$ $\newcommand {\qed }{\quad \square }$ $\newcommand {\idiv }[2]{\lfloor #1/#2\rfloor }$ $\newcommand \attribdot {\ensuremath {\mkern 1.5mu.\mkern 1.5mu}}$ $\newcommand \attribxr [2]{#1\attribdot \text {#2}}$ $\newcommand \attribir [2]{\Id {#1}\attribdot \text {#2}}$ $\newcommand \attribii [2]{\Id {#1}\attribdot \Id {#2}}$ $\newcommand \textsc [1]{#1}$ $\require {colortbl}$ $\let \LWRorigcolumncolor \columncolor $ $\renewcommand {\columncolor }[2][named]{\LWRorigcolumncolor [#1]{#2}\LWRabsorbtwooptions }$ $\let \LWRorigrowcolor \rowcolor $ $\renewcommand {\rowcolor }[2][named]{\LWRorigrowcolor [#1]{#2}\LWRabsorbtwooptions }$ $\let \LWRorigcellcolor \cellcolor $ $\renewcommand {\cellcolor }[2][named]{\LWRorigcellcolor [#1]{#2}\LWRabsorbtwooptions }$ $\newcommand {\tcbset }[1]{}$ $\newcommand {\tcbsetforeverylayer }[1]{}$ $\newcommand {\tcbox }[2][]{\boxed {\text {#2}}}$ $\newcommand {\tcboxfit }[2][]{\boxed {#2}}$ $\newcommand {\tcblower }{}$ $\newcommand {\tcbline }{}$ $\newcommand {\tcbtitle }{}$ $\newcommand {\tcbsubtitle [2][]{\mathrm {#2}}}$ $\newcommand {\tcboxmath }[2][]{\boxed {#2}}$ $\newcommand {\tcbhighmath }[2][]{\boxed {#2}}$ $\newcommand {\toprule }[1][]{\hline }$ $\let \midrule \toprule $ $\let \bottomrule \toprule $ $\def \LWRbooktabscmidruleparen (#1)#2{}$ $\newcommand {\LWRbooktabscmidrulenoparen }[1]{}$ $\newcommand {\cmidrule }[1][]{\ifnextchar (\LWRbooktabscmidruleparen \LWRbooktabscmidrulenoparen }$ $\newcommand {\morecmidrules }{}$ $\newcommand {\specialrule }[3]{\hline }$ $\newcommand {\addlinespace }[1][]{}$ $\newcommand {\LWRsubmultirow }[2][]{#2}$ $\newcommand {\LWRmultirow }[2][]{\LWRsubmultirow }$ $\newcommand {\multirow }[2][]{\LWRmultirow }$ $\newcommand {\mrowcell }{}$ $\newcommand {\mcolrowcell }{}$ $\newcommand {\STneed }[1]{}$ $\newcommand {\LWRldelimtwo }[1][]{\text {#1}~\LWRbigdelim }$ $\newcommand {\LWRldelimone }[2][]{\LWRldelimtwo }$ $\def \ldelim #1#2{\def \LWRbigdelim {#1}\LWRldelimone }$ $\newcommand {\LWRrdelimtwo }[1][]{\LWRbigdelim ~\text {#1}}$ $\newcommand {\LWRrdelimone }[2][]{\LWRrdelimtwo }$ $\def \rdelim #1#2{\def \LWRbigdelim {#1}\LWRrdelimone }$ $\let \symnormal \mathit $ $\let \symliteral \mathrm $ $\let \symbb \mathbb $ $\let \symbbit \mathbb $ $\let \symcal \mathcal $ $\let \symscr \mathscr $ $\let \symfrak \mathfrak $ $\let \symsfup \mathsf $ $\let \symsfit \mathit $ $\let \symbfsf \mathbf $ $\let \symbfup \mathbf $ $\newcommand {\symbfit }[1]{\boldsymbol {#1}}$ $\let \symbfcal \mathcal $ $\let \symbfscr \mathscr $ $\let \symbffrak \mathfrak $ $\let \symbfsfup \mathbf $ $\newcommand {\symbfsfit }[1]{\boldsymbol {#1}}$ $\let \symup \mathrm $ $\let \symbf \mathbf $ $\let \symit \mathit $ $\let \symsf \symsfit $ $\let \symtt \mathtt $ $\let \symbffrac \mathbffrac $ $\newcommand {\mathfence }[1]{\mathord {#1}}$ $\newcommand {\mathover }[1]{#1}$ $\newcommand {\mathunder }[1]{#1}$ $\newcommand {\mathaccent }[1]{#1}$ $\newcommand {\mathbotaccent }[1]{#1}$ $\newcommand {\mathalpha }[1]{\mathord {#1}}$ $\def\Alpha{\unicode{x1D6E2}}$ $\def\Beta{\unicode{x1D6E3}}$ $\def\Gamma{\unicode{x1D6E4}}$ $\def\Digamma{\mathit{\unicode{x03DC}}}$ $\def\Delta{\unicode{x1D6E5}}$ $\def\Epsilon{\unicode{x1D6E6}}$ $\def\Zeta{\unicode{x1D6E7}}$ $\def\Eta{\unicode{x1D6E8}}$ $\def\Theta{\unicode{x1D6E9}}$ $\def\Vartheta{\unicode{x1D6F3}}$ $\def\Iota{\unicode{x1D6EA}}$ $\def\Kappa{\unicode{x1D6EB}}$ $\def\Lambda{\unicode{x1D6EC}}$ $\def\Mu{\unicode{x1D6ED}}$ $\def\Nu{\unicode{x1D6EE}}$ $\def\Xi{\unicode{x1D6EF}}$ $\def\Omicron{\unicode{x1D6F0}}$ $\def\Pi{\unicode{x1D6F1}}$ $\def\Rho{\unicode{x1D6F2}}$ $\def\Sigma{\unicode{x1D6F4}}$ $\def\Tau{\unicode{x1D6F5}}$ $\def\Upsilon{\unicode{x1D6F6}}$ $\def\Phi{\unicode{x1D6F7}}$ $\def\Chi{\unicode{x1D6F8}}$ $\def\Psi{\unicode{x1D6F9}}$ $\def\Omega{\unicode{x1D6FA}}$ $\def\alpha{\unicode{x1D6FC}}$ $\def\beta{\unicode{x1D6FD}}$ $\def\varbeta{\unicode{x03D0}}$ $\def\gamma{\unicode{x1D6FE}}$ $\def\digamma{\mathit{\unicode{x03DD}}}$ $\def\delta{\unicode{x1D6FF}}$ $\def\epsilon{\unicode{x1D716}}$ $\def\varepsilon{\unicode{x1D700}}$ $\def\zeta{\unicode{x1D701}}$ $\def\eta{\unicode{x1D702}}$ $\def\theta{\unicode{x1D703}}$ $\def\vartheta{\unicode{x1D717}}$ $\def\iota{\unicode{x1D704}}$ $\def\kappa{\unicode{x1D705}}$ $\def\varkappa{\unicode{x1D718}}$ $\def\lambda{\unicode{x1D706}}$ $\def\mu{\unicode{x1D707}}$ $\def\nu{\unicode{x1D708}}$ $\def\xi{\unicode{x1D709}}$ $\def\omicron{\unicode{x1D70A}}$ $\def\pi{\unicode{x1D70B}}$ $\def\varpi{\unicode{x1D71B}}$ $\def\rho{\unicode{x1D70C}}$ $\def\varrho{\unicode{x1D71A}}$ $\def\sigma{\unicode{x1D70E}}$ $\def\varsigma{\unicode{x1D70D}}$ $\def\tau{\unicode{x1D70F}}$ $\def\upsilon{\unicode{x1D710}}$ $\def\phi{\unicode{x1D719}}$ $\def\varphi{\unicode{x1D711}}$ $\def\chi{\unicode{x1D712}}$ $\def\psi{\unicode{x1D713}}$ $\def\omega{\unicode{x1D714}}$ $\def\upAlpha{\unicode{x0391}}$ $\def\upBeta{\unicode{x0392}}$ $\def\upGamma{\unicode{x0393}}$ $\def\upDigamma{\unicode{x03DC}}$ $\def\upDelta{\unicode{x0394}}$ $\def\upEpsilon{\unicode{x0395}}$ $\def\upZeta{\unicode{x0396}}$ $\def\upEta{\unicode{x0397}}$ $\def\upTheta{\unicode{x0398}}$ $\def\upVartheta{\unicode{x03F4}}$ $\def\upIota{\unicode{x0399}}$ $\def\upKappa{\unicode{x039A}}$ $\def\upLambda{\unicode{x039B}}$ $\def\upMu{\unicode{x039C}}$ $\def\upNu{\unicode{x039D}}$ $\def\upXi{\unicode{x039E}}$ $\def\upOmicron{\unicode{x039F}}$ $\def\upPi{\unicode{x03A0}}$ $\def\upVarpi{\unicode{x03D6}}$ $\def\upRho{\unicode{x03A1}}$ $\def\upSigma{\unicode{x03A3}}$ $\def\upTau{\unicode{x03A4}}$ $\def\upUpsilon{\unicode{x03A5}}$ $\def\upPhi{\unicode{x03A6}}$ $\def\upChi{\unicode{x03A7}}$ $\def\upPsi{\unicode{x03A8}}$ $\def\upOmega{\unicode{x03A9}}$ $\def\itAlpha{\unicode{x1D6E2}}$ $\def\itBeta{\unicode{x1D6E3}}$ $\def\itGamma{\unicode{x1D6E4}}$ $\def\itDigamma{\mathit{\unicode{x03DC}}}$ $\def\itDelta{\unicode{x1D6E5}}$ $\def\itEpsilon{\unicode{x1D6E6}}$ $\def\itZeta{\unicode{x1D6E7}}$ $\def\itEta{\unicode{x1D6E8}}$ $\def\itTheta{\unicode{x1D6E9}}$ $\def\itVartheta{\unicode{x1D6F3}}$ $\def\itIota{\unicode{x1D6EA}}$ $\def\itKappa{\unicode{x1D6EB}}$ $\def\itLambda{\unicode{x1D6EC}}$ $\def\itMu{\unicode{x1D6ED}}$ $\def\itNu{\unicode{x1D6EE}}$ $\def\itXi{\unicode{x1D6EF}}$ $\def\itOmicron{\unicode{x1D6F0}}$ $\def\itPi{\unicode{x1D6F1}}$ $\def\itRho{\unicode{x1D6F2}}$ $\def\itSigma{\unicode{x1D6F4}}$ $\def\itTau{\unicode{x1D6F5}}$ $\def\itUpsilon{\unicode{x1D6F6}}$ $\def\itPhi{\unicode{x1D6F7}}$ $\def\itChi{\unicode{x1D6F8}}$ $\def\itPsi{\unicode{x1D6F9}}$ $\def\itOmega{\unicode{x1D6FA}}$ $\def\upalpha{\unicode{x03B1}}$ $\def\upbeta{\unicode{x03B2}}$ $\def\upvarbeta{\unicode{x03D0}}$ $\def\upgamma{\unicode{x03B3}}$ $\def\updigamma{\unicode{x03DD}}$ $\def\updelta{\unicode{x03B4}}$ $\def\upepsilon{\unicode{x03F5}}$ $\def\upvarepsilon{\unicode{x03B5}}$ $\def\upzeta{\unicode{x03B6}}$ $\def\upeta{\unicode{x03B7}}$ $\def\uptheta{\unicode{x03B8}}$ $\def\upvartheta{\unicode{x03D1}}$ $\def\upiota{\unicode{x03B9}}$ $\def\upkappa{\unicode{x03BA}}$ $\def\upvarkappa{\unicode{x03F0}}$ $\def\uplambda{\unicode{x03BB}}$ $\def\upmu{\unicode{x03BC}}$ $\def\upnu{\unicode{x03BD}}$ $\def\upxi{\unicode{x03BE}}$ $\def\upomicron{\unicode{x03BF}}$ $\def\uppi{\unicode{x03C0}}$ $\def\upvarpi{\unicode{x03D6}}$ $\def\uprho{\unicode{x03C1}}$ $\def\upvarrho{\unicode{x03F1}}$ $\def\upsigma{\unicode{x03C3}}$ $\def\upvarsigma{\unicode{x03C2}}$ $\def\uptau{\unicode{x03C4}}$ $\def\upupsilon{\unicode{x03C5}}$ $\def\upphi{\unicode{x03D5}}$ $\def\upvarphi{\unicode{x03C6}}$ $\def\upchi{\unicode{x03C7}}$ $\def\uppsi{\unicode{x03C8}}$ $\def\upomega{\unicode{x03C9}}$ $\def\italpha{\unicode{x1D6FC}}$ $\def\itbeta{\unicode{x1D6FD}}$ $\def\itvarbeta{\unicode{x03D0}}$ $\def\itgamma{\unicode{x1D6FE}}$ $\def\itdigamma{\mathit{\unicode{x03DD}}}$ $\def\itdelta{\unicode{x1D6FF}}$ $\def\itepsilon{\unicode{x1D716}}$ $\def\itvarepsilon{\unicode{x1D700}}$ $\def\itzeta{\unicode{x1D701}}$ $\def\iteta{\unicode{x1D702}}$ $\def\ittheta{\unicode{x1D703}}$ $\def\itvartheta{\unicode{x1D717}}$ $\def\itiota{\unicode{x1D704}}$ $\def\itkappa{\unicode{x1D705}}$ $\def\itvarkappa{\unicode{x1D718}}$ $\def\itlambda{\unicode{x1D706}}$ $\def\itmu{\unicode{x1D707}}$ $\def\itnu{\unicode{x1D708}}$ $\def\itxi{\unicode{x1D709}}$ $\def\itomicron{\unicode{x1D70A}}$ $\def\itpi{\unicode{x1D70B}}$ $\def\itvarpi{\unicode{x1D71B}}$ $\def\itrho{\unicode{x1D70C}}$ $\def\itvarrho{\unicode{x1D71A}}$ $\def\itsigma{\unicode{x1D70E}}$ $\def\itvarsigma{\unicode{x1D70D}}$ $\def\ittau{\unicode{x1D70F}}$ $\def\itupsilon{\unicode{x1D710}}$ $\def\itphi{\unicode{x1D719}}$ $\def\itvarphi{\unicode{x1D711}}$ $\def\itchi{\unicode{x1D712}}$ $\def\itpsi{\unicode{x1D713}}$ $\def\itomega{\unicode{x1D714}}$ $\let \lparen ($ $\let \rparen )$ $\newcommand {\cuberoot }[1]{\,{}^3\!\!\sqrt {#1}}\,$ $\newcommand {\fourthroot }[1]{\,{}^4\!\!\sqrt {#1}}\,$ $\newcommand {\longdivision }[1]{\mathord {\unicode {x027CC}#1}}$ $\newcommand {\mathcomma }{,}$ $\newcommand {\mathcolon }{:}$ $\newcommand {\mathsemicolon }{;}$ $\newcommand {\overbracket }[1]{\mathinner {\overline {\ulcorner {#1}\urcorner }}}$ $\newcommand {\underbracket }[1]{\mathinner {\underline {\llcorner {#1}\lrcorner }}}$ $\newcommand {\overbar }[1]{\mathord {#1\unicode {x00305}}}$ $\newcommand {\ovhook }[1]{\mathord {#1\unicode {x00309}}}$ $\newcommand {\ocirc }[1]{\mathord {#1\unicode {x0030A}}}$ $\newcommand {\candra }[1]{\mathord {#1\unicode {x00310}}}$ $\newcommand {\oturnedcomma }[1]{\mathord {#1\unicode {x00312}}}$ $\newcommand {\ocommatopright }[1]{\mathord {#1\unicode {x00315}}}$ $\newcommand {\droang }[1]{\mathord {#1\unicode {x0031A}}}$ $\newcommand {\leftharpoonaccent }[1]{\mathord {#1\unicode {x020D0}}}$ $\newcommand {\rightharpoonaccent }[1]{\mathord {#1\unicode {x020D1}}}$ $\newcommand {\vertoverlay }[1]{\mathord {#1\unicode {x020D2}}}$ $\newcommand {\leftarrowaccent }[1]{\mathord {#1\unicode {x020D0}}}$ $\newcommand {\annuity }[1]{\mathord {#1\unicode {x020E7}}}$ $\newcommand {\widebridgeabove }[1]{\mathord {#1\unicode {x020E9}}}$ $\newcommand {\asteraccent }[1]{\mathord {#1\unicode {x020F0}}}$ $\newcommand {\threeunderdot }[1]{\mathord {#1\unicode {x020E8}}}$ $\newcommand {\Bbbsum }{\mathop {\unicode {x2140}}\limits }$ $\newcommand {\oiint }{\mathop {\unicode {x222F}}\limits }$ $\newcommand {\oiiint }{\mathop {\unicode {x2230}}\limits }$ $\newcommand {\intclockwise }{\mathop {\unicode {x2231}}\limits }$ $\newcommand {\ointclockwise }{\mathop {\unicode {x2232}}\limits }$ $\newcommand {\ointctrclockwise }{\mathop {\unicode {x2233}}\limits }$ $\newcommand {\varointclockwise }{\mathop {\unicode {x2232}}\limits }$ $\newcommand {\leftouterjoin }{\mathop {\unicode {x27D5}}\limits }$ $\newcommand {\rightouterjoin }{\mathop {\unicode {x27D6}}\limits }$ $\newcommand {\fullouterjoin }{\mathop {\unicode {x27D7}}\limits }$ $\newcommand {\bigbot }{\mathop {\unicode {x27D8}}\limits }$ $\newcommand {\bigtop }{\mathop {\unicode {x27D9}}\limits }$ $\newcommand {\xsol }{\mathop {\unicode {x29F8}}\limits }$ $\newcommand {\xbsol }{\mathop {\unicode {x29F9}}\limits }$ $\newcommand {\bigcupdot }{\mathop {\unicode {x2A03}}\limits }$ $\newcommand {\bigsqcap }{\mathop {\unicode {x2A05}}\limits }$ $\newcommand {\conjquant }{\mathop {\unicode {x2A07}}\limits }$ $\newcommand {\disjquant }{\mathop {\unicode {x2A08}}\limits }$ $\newcommand {\bigtimes }{\mathop {\unicode {x2A09}}\limits }$ $\newcommand {\modtwosum }{\mathop {\unicode {x2A0A}}\limits }$ $\newcommand {\sumint }{\mathop {\unicode {x2A0B}}\limits }$ $\newcommand {\intbar }{\mathop {\unicode {x2A0D}}\limits }$ $\newcommand {\intBar }{\mathop {\unicode {x2A0E}}\limits }$ $\newcommand {\fint }{\mathop {\unicode {x2A0F}}\limits }$ $\newcommand {\cirfnint }{\mathop {\unicode {x2A10}}\limits }$ $\newcommand {\awint }{\mathop {\unicode {x2A11}}\limits }$ $\newcommand {\rppolint }{\mathop {\unicode {x2A12}}\limits }$ $\newcommand {\scpolint }{\mathop {\unicode {x2A13}}\limits }$ $\newcommand {\npolint }{\mathop {\unicode {x2A14}}\limits }$ $\newcommand {\pointint }{\mathop {\unicode {x2A15}}\limits }$ $\newcommand {\sqint }{\mathop {\unicode {x2A16}}\limits }$ $\newcommand {\intlarhk }{\mathop {\unicode {x2A17}}\limits }$ $\newcommand {\intx }{\mathop {\unicode {x2A18}}\limits }$ $\newcommand {\intcap }{\mathop {\unicode {x2A19}}\limits }$ $\newcommand {\intcup }{\mathop {\unicode {x2A1A}}\limits }$ $\newcommand {\upint }{\mathop {\unicode {x2A1B}}\limits }$ $\newcommand {\lowint }{\mathop {\unicode {x2A1C}}\limits }$ $\newcommand {\bigtriangleleft }{\mathop {\unicode {x2A1E}}\limits }$ $\newcommand {\zcmp }{\mathop {\unicode {x2A1F}}\limits }$ $\newcommand {\zpipe }{\mathop {\unicode {x2A20}}\limits }$ $\newcommand {\zproject }{\mathop {\unicode {x2A21}}\limits }$ $\newcommand {\biginterleave }{\mathop {\unicode {x2AFC}}\limits }$ $\newcommand {\bigtalloblong }{\mathop {\unicode {x2AFF}}\limits }$ $\newcommand {\arabicmaj }{\mathop {\unicode {x1EEF0}}\limits }$ $\newcommand {\arabichad }{\mathop {\unicode {x1EEF1}}\limits }$

1.4 Chapter Notes¶

Iterated function systems are a popular means of constructing fractal shapes: They are easy to describe, easy to program, and can be used to model infinitely detailed geometric shapes using just a few parameters. See Paul Bourke’s website (https://paulbourke.net/fractals/ifs/) for an overview of shapes that can be generated in this way.

It is possible to extend the simple IFSs discussed in this chapter to produce still images and animations that are even more striking. The best-known example is the so-called fractal flame algorithm, which adds new function types, colorization, as well as additional transformation and post-processing steps to produce and endless variety of images and animations such as the one shown in Fig. 1.9 [31]. The Electric Sheep screen saver (https://electricsheep.org/) is based on this algorithm.

There is a deep and beautiful mathematical theory behind iterated function systems that concerns itself with questions such as:

• Under which conditions does the chaos game converge?
• How are the functions in the IFS related to the resulting fractal?
• Why does the chaos game always produce the same fractal even if we change the starting point or make different random choices during the process?

For details, see the books by Barnsley [10] and Peitgen et al. [76].

To give you a taste of this theory, let us briefly discuss one of its main results: The chaos game converges only if the functions are contractive, which means that they make everything smaller. In mathematical terms, a function $f$ is called contractive if the points $f(\vec {p})$ and $f(\vec {q})$ are closer together than $\vec {p}$ and $\vec {q}$ for every possible choice of $\vec {p}$ and $\vec {q}$:

\begin{equation*} \bigl |f(\vec {p})-f(\vec {q})\bigr | < |\vec {p}-\vec {q}|\qquad \text {for all $\vec {p}$ and $\vec {q}$}. \end{equation*}

The upper bound of the ratio $\bigl |f(\vec {p})-f(\vec {q})\bigr | / |\vec {p}-\vec {q}|$ is called the contraction factor of the function $f$. A function is therefore contractive if its contraction factor is less than 1.

Consider the function $\vec {p}\mapsto (\vec {p}+\vec {c})/2$ that we used at the beginning of this chapter to move points halfway towards the corner $\vec {c}$. It’s easy to show that this function is contractive with a contraction factor of $1/2$:

\begin{equation*} \bigl |f(\vec {p})-f(\vec {q})\bigr |=\bigl |(\vec {p}+\vec {c})/2 - (\vec {q}-\vec {c})/2\bigr | = |\vec {p}-\vec {q}|/2. \end{equation*}

Therefore, any set of functions that move their argument halfway toward a fixed set of points forms a convergent IFS.

It is also possible to derive the contraction factors of arbitrary affine transformations, but a few concepts from linear algebra are required. The main result is that the contraction factor of

\begin{equation*} f(\vec {p})=\vec {A}\vec {p} + \vec {v}, \end{equation*}

is the square root of the largest eigenvalue of $\vec {A}^t\vec {A}$, where $\vec {A}^t$ is the transpose of the matrix $\vec {A}$. For instance, in the case of the Barnsley fern, the contraction factors of the functions $f_0,\dots ,f_3$ are 0.16, 0.85, 0.32, and 0.34.