Classic Iterated Function Systems

The black path for $R^3(LR)^\infty$ has a branch tip with y-coordinate 1.19607 while the green path for $(LR)^\infty$ leads to a branch tip with y-coordinate only at 0.85328 (the x-coordinates are 0.28262 and −1.11111, respectively). You can get a sense of why this might happen in this example since the green path has mostly a horizontal direction while the black path is more vertical. The value of $r$ is large enough that the black path will grow sufficiently upward to eventually extend above the end of the green path. You can see this happen by viewing the branch animation. If you watch the tree animation, you will see how this large value of $r$ produces extensive overlap of the branches as the tree grows. Also notice in the figure above that the other "peaks" along the boundary are extensions of $R^3(LR)^\infty$ using initial branches of the form $(RL)^m$.

Let $y_k$ be the y-coordinate of the $R^k(LR)^\infty$ branch tip and let $y_0$ be the y-coordinate of the $(LR)^\infty$ branch tip. For a fixed $\theta$, these coordinates depend on the value of $r$. Let \(f_\theta (r)=y_k - y_0\) be the difference between the y-coordinates of the two branch tips, so \[ f_\theta (r) = \sum_{n=0}^{k}{r^n \cos(n \theta)} + \frac{r^{k+1} \cos((k-1)\theta) + r^{k+2} \cos(k \theta) -1-r\cos( \theta)}{1-r^2} \]

If \(f_\theta (r)\) is negative then $y_k$ is less than $y_0$, and if \(f_\theta (r)\) is positive then $y_k$ is greater than $y_0$. We consider two different cases depending on the value of $\theta$.

Case 1: \(\theta = \dfrac{360^{\circ}}{k}\) where $k$ is an integer

Note that $k ≥ 3$ since $\theta < 180^\circ$, and that $\theta ≤ 1^\circ$ for all $k ≥ 360$. The largest possible angle is 120° (for $k$ = 3).

For this special case we have $k\theta = 360^\circ$ and therefore the last branch of $R^k$ is vertical, but of length $r^k$. From this point on, the branches of $R^k(LR)^\infty$ alternate in the same pattern that the $(LR)^\infty$ branches did from the beginning, but can never catch up, and thus $y_k$ will be less than $y_0$. The following image shows what happens for $\theta$ = 120° with $r$ = 0.9. The red path will have $y_0$ = 2.89474 and the black path will have $y_3$ = 2.25526.

Why does this happen for these special values of $\theta$? Because $k\theta$ = 360°, we have \(\cos(k \theta) = \cos(360^{\circ}) = 1\) and \(\cos((k-1)\theta) = \cos(360^{\circ}-\theta) = \cos(\theta)\). Therefore

It can then be shown [Near 0 Details] that the graph of \(f_\theta (r)\) starts at (0,0) and initially begins decreasing in a concave down fashion as $r$ increases. Moreover, with the help of L'Hospital's rule, we can determine that

Therefore \(\lim_{r \rightarrow 1^{-}} f_\theta(r) < 0\) suggesting that \(f_\theta(r)\) always remains negative as $r$ goes from 0 to 1. This would imply that $y_0$ is always greater than $y_k$ for all $r$ between 0 and 1 for these special values of $\theta$. To see that this is actually the case, click on the Play button below to see the graphs of \(f_\theta(r)\) for $k$ from 3 to 360, corresponding to the 358 special $\theta$ values of the form $360^\circ/k$ between 1° and 120°. The graph of $f_{\theta}$ is shown only for $0.9 ≤ r ≤ 1$ since the scale on the vertical axis will prevent the very small values of \(f_\theta(r)\) from being shown for small values of $r$.

Case 2: \(\theta \neq \dfrac{360^{\circ}}{n}\) for any integer $n$

Now the smallest integer $k$ such that $k\theta > 360^\circ$ is \(k = \left\lceil \frac{360^\circ}{\theta} \right\rceil\), where \(\lceil x \rceil\) is the ceiling function, i.e. the smallest integer greater than or equal to $x$. As in case 1, the value of $k$ can be any integer greater than or equal to 3.

As before [Near 0 Details], the graph of \(f_\theta (r)\) starts at (0,0) and initially begins decreasing in a concave down fashion as $r$ increases. This time, however, we have \(\lim_{r \rightarrow 1^{-}} f_\theta (r) = +\infty\). To see why, we just need to verify that the numerator of the fraction in the expression for \(f_\theta (r)\) is positive when $r = 1$ since the denominator is positive and goes to 0 as $r$ approaches 1 from the left. So we need to verify that \[ N(\theta) = \cos((k-1)\theta) + \cos(k \theta) -1-\cos( \theta) > 0 \text{ when } \frac{360^\circ}{k} < \theta < \frac{360^\circ}{k-1} \] where \(k = \lceil \frac{360^\circ}{\theta} \rceil\). For example, for $120^\circ < \theta < 180^\circ$ with $k = 3$, \[N(\theta) = \cos(2\theta) + \cos(3 \theta) -1-\cos( \theta) = -2 \sin^2(\theta) (2\cos(\theta)+1) > 0\] since \(2\cos(\theta)+1 < 0\) for $120^\circ < \theta < 180^\circ$. Note that $N(120^\circ) = N(180^\circ) = 0$, and that in general, $N(360^\circ/k) = N(360^\circ/(k-1)) = 0$.

Shown below is the graph of \(N(\theta)\) showing that \(N(\theta)\) is positive for all $\theta$ except for those of the form $360^\circ/k$ (which pile up very quickly as $k$ gets large and $\theta$ approaches 0.)

Because \(f_\theta (r)\) is negative for small $r$ and \(\lim_{r \rightarrow 1^{-}} f_\theta (r) = +\infty\), there must be some some $r_T$ between 0 and 1 where \(f_\theta (r_T) = 0.\) The two images below show the graphs of \(f_\theta (r)\) for $\theta$ = 65° and $\theta$ = 135°. The shapes of these graphs are typical for all values of $\theta$ in case 2.

The equation \(f_\theta (r) = 0\) can be solved numerically to find the solution $r_T$. The next two figures show the graph of $r_T$ for $0^\circ < \theta < 180^\circ$, and a close up of this graph just on the range $10^\circ < \theta < 90^\circ$.

Several observations. First, the equation \(f_\theta (r) = 0\) has no solution for $r > 0$ when $\theta$ is of the form $360^\circ/k$ for some integer $k$. These are the special angles in case 1. Therefore $r_T$ does not exist at these special values of $\theta$. However, what the graphs show is that $r_T$ approaches 1 as $\theta$ approaches one of these special angles.

Second, for $\theta < 90^\circ$, the value of the critical scaling factor $r_T$ is greater than 0.94, so for all practical purposes the top of a "reasonable" symmetric binary tree for this range of $\theta$ will be determined by the $(LR)^\infty$ path and have value \((1+r\cos(\theta))/(1-r^2)\). Any choice of ${r > 0.94}$ will produce a tree that has a massive overlap of branches.

Third, the situation is a bit different for $\theta > 90^\circ$, and in particular for $\theta > 120^\circ$. Note that on this latter interval, the value of $r_T$ converges to 1/2 as $\theta$ approaches 180°. We can, in fact, solve \(f_\theta (r) = 0\) explicitly for $r$ for those values of $\theta$ in these two intervals [Calculation Details] to get \[ \begin{align} 90^\circ < \theta < 120^\circ &\Rightarrow r_T = - \frac{{\cos ( {{{\theta}}} ) + \sqrt { - 3\cos^2 {{( {{{\theta}}} )}} + 1} }}{{4\cos^2 {{( {{{\theta}}} )}} - 1}} \\ \\ 120^\circ < \theta < 180^\circ &\Rightarrow r_T = -\frac{1}{2\cos(\theta)} \end{align} \]

Finally, it is interesting to note that for $\theta ≥ 135^\circ$, the critical scaling factor $r_T$ is the same value as $r_{sc}$ for which the binary tree of angle $\theta$ is self-contacting. Here is a comparison of the two graphs of $r_T$ versus $r_{sc}$. For $r_{sc} < r < r_T$, the binary tree will have overlapping branches, but the top of the branch tips will still correspond to the $(LR)^\infty$ path.