Classic Iterated Function Systems

The two branches are obtained from the trunk by scaling by a factor of $r$, rotating counterclockwise by $\theta$ (left) and $-\theta$ (right), then translating to the top of the trunk. The third function needed is the identity. This keeps the branches already drawn in their current locations while the first two functions add the new branches.

Note that function 3 in this iterated function system is not a contractive mapping. Therefore the theory of contractive iterated function systems cannot necessarily be applied here. However, in this case the iterates of an initial set under this iterated function system do converge to a limit set, but the limit will depend on the initial set [Proof]. This type of iterated function system is often called an IFS with condensation.

If only the first two functions are used as the iterated function system, the system will be contractive and all initial sets will converge to the branch tips. Both of the trees above have the same branch tips shown below.

If the scaling factor $r$ is too small, the branches of the tree will be self-avoiding, while if $r$ is too large the branches will overlap. Mandelbrot and Frame showed that for each angle $\theta$, there is a unique scaling factor $r_{sc}$ such that the symmetric binary tree with that $\theta$ and $r$ will be self-contacting, that is, branches may touch at a single point but may not cross. In this case, the branch tips of left-side branches will coincide with branch tips of some right-side branches, but no branch tip will coincide with any non-tip point of the tree. Three examples are shown below for $\theta$=60°.

Let the tree be defined by the angle $\theta$ and scaling factor $r$. We will take the base of the tree to be at the origin and the initial vertical trunk to be of length 1. By the "top" of the tree we will mean the top of the branch tips, that is, the largest y-coordinate of the branch tips. The "bottom" of the tree will mean the bottom of the branch tips, that is, the smallest y-coordinate of the branch tips. The "right side" of the tree will be the largest x-coordinate of the branch tips (and by symmetry, the left side will be the negative of this x-coordinate.)

For most symmetric binary trees, the top of the tree will correspond to the y-coordinate of the branch tip of the path $(LR)^\infty$, or equivalently $(RL)^\infty = R(LR)^\infty$; the right side will correspond to the x-coordinate of the branch tip of the path $R^k(LR)^\infty$ where $k$ is the smallest integer with $k\theta \ge 90^\circ$; and the bottom will correspond to the y-coordinate of the branch tip of the path $R^k(LR)^\infty$ where $k$ is the smallest integer with $k\theta \ge 180^\circ$.

As observed by Don West for the top of the tree, however, the branch tip for $(LR)^\infty$ or $(RL)^\infty$ may not always have the largest y-coordinate. Indeed, for every $\theta$ that is not of the form $360^\circ/n$ for some integer $n$, there will be a critical value $r_T$ such that if $r \gt r_T$, then the branch tip for the path $R^k(LR)^\infty$, or equivalently, $L^k(RL)^\infty$, will have a greater y-coordinate, where k is the smallest integer such that $k\theta \ge 360^\circ$.These scaling factors will be fairly large, however, and the resulting binary trees will have massively overlapping branches as shown in the example below. Notice how the branch tip for $R^3(LR)^\infty$ has a larger y-coordinate than the branch tip for $(LR)^\infty$.

Similar exceptions hold for the bottom and sides of a binary tree for certain intervals of $\theta$. None of these exceptions will happen, however, for self-contacting trees or when $r \lt r_{sc}$. For these trees, the top, bottom, and sides will always be determined by the paths described in the first paragraph. Click for the mathematical details.