Agnes Scott College
Larry Riddle, Agnes Scott College
image

Self-Contacting Symmetric Binary Trees

Let \(\alpha\) be the complex number \(\alpha = e^{\theta i}=\cos{\theta} + i \sin{\theta}\). Multiplying a complex number by alpha corresponds to a counterclockwise rotation by \(\theta\). Multiplying by \(\alpha^{-1} = \cos{\theta} - i \sin{\theta}\) corresponds to a clockwise rotation by \(\theta\). Notice that successive rotations to the left and then the right, or by the right and then the left, would correspond to the multiplication \(\alpha \alpha^{-1} = 1\). We also have \(\alpha^n = e^{n\theta i}=\cos{(n\theta)} + i \sin{(n\theta)}\) and \(\alpha^{-n} = e^{-n\theta i}=\cos{(n\theta)} - i \sin{(n\theta)}\) for all integers n.

The initial vertical trunk of the tree is represented by the vector \(i\). The following diagram represents the branches correspond to the address LRL. Each vector is obtained from the previous vector by multiplying that vector by r (scaling) and then multiplying either by \(\alpha\) (L) or by \(\alpha^{-1}\) (R). The tip of the branch LRL is then located at the point corresponding to the complex number \(i + ir\alpha + ir^2 + ir^3\alpha\).

LRLvectors

0 < θ ≤ 90°

Let N be the smallest integer such that Nθ ≥ 90°. The images below show what needs to happen with θ=60° (N=2) for the tree to be self-contacting. The tree is on the left and the paths LR3(LR) and RL3(RL) are shown in the image on the right.

self-contactingImage self-contacting-branches

Take a look at the red path that starts with a L turn, then the first R turn creates a vertical branch. At this point we want to start making branch turns that will always get us closer to the y-axis. Until the path crosses the horizontal (90° from the vertical), this will continue to be right turns. In this example it will take two more right turns before the path crosses the horizontal. The path should then begin alternating left and right turns as it approaches the y-axis in a "mostly horizontal" direction. The blue branches follows a path symmetric to the red ones relative to the y-axis. The value of r must be chosen so that the branch tip at the end of the red path and the branch tip at the end of the blue path both coincide on the y-axis.

In general, the self-contacting r value for θ must satisfy the property that the branch tip LRN+1(LR) coincides with the branch tip RLN+1(RL), and both have x-coordinate 0. The branch tip for RLN+1(RL) = RLN-1LL(RL) will correspond to the complex number

\[ \begin{align} i &+ ir\alpha^{-1} + ir^2\alpha^0 + ir^3\alpha + ir^4\alpha^2 + \ldots + ir^N\alpha^{N-2} + \\ \\ &\quad\quad\quad+ ir^{N+1}\alpha^{N-1} + ir^{N+2}\alpha^{N} + ir^{N+3}\alpha^{N-1} + ir^{N+4}\alpha^N + ir^{N+5}\alpha^{N-1} + \cdots \\ \\ &= i\left( {1 + \sum_{k=-1}^{N-2}{r^{k+2}\alpha^k} + r^{N+1}\alpha^{N-1}\left( { 1+ r\alpha + r^2 + r^3\alpha + r^4 + \cdots } \right)} \right) \\ \\ &= i\left( {1 + \sum_{k=-1}^{N-2}{r^{k+2}\alpha^k} + r^{N+1}\alpha^{N-1}\left( { \frac{1}{1-r^2} + \frac{r\alpha}{1-r^2}} \right) } \right) \\ \\ &= i\left( {1 + \sum_{k=-1}^{N-2}{r^{k+2}\alpha^k} + \frac{r^{N+1}\alpha^{N-1}+r^{N+2}\alpha^N}{1-r^2} } \right) = iz. \end{align} \] Since \(x = \text{Re}(iz) = -\text{Im}(z)\), the scaling factor r must satisfy \[\sum_{k=-1}^{N-2}{r^{k+2}\sin(k\theta)} + \frac{r^{N+1}\sin((N-1)\theta)+r^{N+2}\sin(N\theta)}{1-r^2} = 0. \] West (1999) and Pagon (2003) have shown that this last equation can be rewritten as \[ \sum_{k=0}^{N-1}{r^{k+2}\cos(k\theta)} = \frac{1}{2}. \] West's argument is the following: \[ \begin{align} 0 &= \sum_{k=-1}^{N-2}{r^{k+2}\sin(k\theta)} + \frac{r^{N+1}\sin((N-1)\theta)+r^{N+2}\sin(N\theta)}{1-r^2} \\ \\ &= \frac{1}{1-r^2} \left( {(1-r^2) \left( {\sum_{k=-1}^{N-2}{r^{k+2}\sin(k\theta)}} \right) + r^{N+1}\sin((N-1)\theta)+r^{N+2}\sin(N\theta)} \right) \\ \\ &= \frac{1}{1-r^2} \left( {\sum_{k=-1}^{N-2}{r^{k+2}\sin(k\theta)} - \sum_{k=-1}^{N-2}{r^{k+4}\sin(k\theta)} + r^{N+1}\sin((N-1)\theta)+r^{N+2}\sin(N\theta)} \right) \\ \\ &= \frac{1}{1-r^2} \left( \left( {{\sum_{k=-1}^{N-2}{r^{k+2}\sin(k\theta)} +r^{N+1}\sin((N-1)\theta)+r^{N+2}\sin(N\theta)}} \right) - \sum_{k=-1}^{N-2}{r^{k+4}\sin(k\theta)} \right) \\ \\ &= \frac{1}{1-r^2} \left( {\sum_{k=-2}^{N-1}{r^{k+3}\sin((k+1)\theta)} - \sum_{k=0}^{N-1}{r^{k+3}\sin((k-1)\theta)} } \right) \\ \\ &= \frac{1}{1-r^2} \left( {-r\sin(\theta) + \sum_{k=0}^{N-1}{r^{k+3}\sin((k+1)\theta)} - \sum_{k=0}^{N-1}{r^{k+3}\sin((k-1)\theta)} } \right) \\ \\ &= \frac{1}{1-r^2} \left( {-r\sin(\theta) + \sum_{k=0}^{N-1}{r^{k+3}\left({ \sin((k+1)\theta) - \sin((k-1)\theta)}\right) }}\right) \\ \\ &= \frac{1}{1-r^2} \left( {-r\sin(\theta) + \sum_{k=0}^{N-1}{{r^{k+3}\left( { 2\cos(k\theta)\sin(\theta)} \right)} } } \right) \\ \\ &= \frac{r\sin(\theta)}{1-r^2}\left( {-1 + 2\sum_{k=0}^{N-1}{{r^{k+2} \cos(k\theta)} } } \right) \\ \\ \end{align} \] Since neither r nor sin(θ) can be 0, the claim follows. We can then make one final simplification with the sum to get an equation that the self-contacting r value must satisfy [see West for a derivation or use a computer algebra system to simplify the sum]: \[ \begin{align} \frac{1}{2} &= \sum_{k=0}^{N-1}{r^{k+2}\cos(k\theta)} = r^2\sum_{k=0}^{N-1}{r^{k}\cos(k\theta)} \\ \\ &= r^2\cdot \left( {\frac{r^{N+1}\cos((N-1)\theta)-r^{N}\cos(N\theta)-r\cos(\theta)+1}{r^2+1-2r\cos(\theta)}} \right) \end{align} \]

Let \(S_\theta (r) = \sum_{k=0}^{N-1}{r^{k+2}\cos(k\theta)}\). Then \(S_\theta (r)\) is a continuous function of r. In addition, \(S_\theta (0) = 0\) and \[S_\theta (1) = 1 + \cos(\theta) + \ldots + \cos((N-1)\theta) > 1\] since all the cosine values are positive because (N-1)θ < 90°. By the intermediate value theorem for continuous functions, we are guaranteed that there is a solution to \(S_\theta (r) = \frac{1}{2}\) for some 0 < r < 1. Moreover, \(S_\theta (r)\) is the sum of increasing functions of r, and thus is itself increasing for 0 < r < 1. Therefore there is a unique solution, and that is the self-contacting value rsc.

90 < θ < 135°

If 90 < θ ≤ 135°, then it will take just two turns for the path to be heading back towards the vertical trunk of the tree. The images below show what needs to happen with θ = 110° for the tree to be self-contacting. The tree is on the left and the paths L2(LR) and R2(RL) are shown in the image on the right. The blue branches follow a path symmetric to the red ones relative to the y-axis.

self-contacting-tree-110 self-contacting-path-110

For the path on the left side of the tree, after the first two left turns, the branches alternating left then right will be the ones that get us closest to the y-axis (trunk) at each turn as demonstrated in the figures below. For 90° < θ < 120°, each branch in the LR alternating pattern will move towards the y-axis. For θ = 120°, each left branch after the first two will be vertical, and the next right branch will move closer to the y-axis. For 120° < θ < 135°, after the first two left turns, both the left and right branches will move away from the y-axis, but the end of the left branch will not be as far away as the end of the right branch. So in this case, also, we want to keep alternating left and right branches to move towards the y-axis as quick as possible.

self-contacting-path-110-2 self-contacting-path-120 self-contacting-path-125
θ = 110°
red = L
blue = R
θ = 120°
red = L
blue = R
θ = 125°
red = L
blue = R

The value of r must be chosen so that the branch tip for L2(LR) and the branch tip for R2(RL) coincide on the y-axis, i.e. have x-coordinate 0.

The branch tip for R2(RL) will correspond to the complex number \[ \begin{align} i &+ ir\alpha^{-1} + ir^2\alpha^{-2} + ir^3\alpha^{-3} + ir^4\alpha^{-2} + ir^5\alpha^{-3} + \cdots \\ \\ & = i\left( 1 + r\alpha^{-1} + r^2\alpha^{-2} \left( 1 + r\alpha^{-1} + r^2 + r^3\alpha^{-1} + \cdots \right) \right) \\ \\ & = i \left( 1 + r\alpha^{-1} + r^2\alpha^{-2} \left( \frac{1}{1-r^2} + \frac{r\alpha^{-1}}{1-r^2} \right) \right) \\ \\ & = i \left( 1+ r\alpha^{-1} + \frac{r^2\alpha^{-2} + r^3\alpha^{-3}}{1-r^2} \right) = iz. \end{align} \]

Since \(x = \text{Re}(iz) = -\text{Im}(z)\), the scaling factor r must satisfy \[ 0 = r\sin(\theta) + \frac{r^2\sin(2\theta) + r^3\sin(3\theta)}{1-r^2} \] Factoring out an r and multiplying through by 1-r2 gives \[ \begin{align} 0 &= (1-r^2)\sin(\theta) + r\sin(2\theta) + r^2\sin(3\theta) \\ \\ &= r^2\left( \sin(3\theta) - \sin(\theta) \right) + r\sin(2\theta) + \sin(\theta) \\ \\ &= r^2 \left( 2\cos(2\theta)\sin(\theta) \right) + 2r\sin(\theta)\cos(\theta) + \sin(\theta) \\ \\ &= \sin(\theta)\left( 2\cos(2\theta)r^2 + 2\cos(\theta)r + 1 \right) \end{align} \] Using the quadratic formula yields \[ \begin{align} r &= \frac{-2\cos(\theta) \pm \sqrt{4\cos^2(\theta)-8\cos(2\theta)}}{4\cos(2\theta)} \\ \\ &= \frac{-\cos(\theta) \pm \sqrt{\cos^2(\theta)-2\cos(2\theta)}}{2\cos(2\theta)} \end{align} \] Since 90° < θ < 135°, we know that cos(θ) and cos(2θ) are both negative. This means that the term under the square root is positive, so we really can take the square root. In addition, it means that the square root term will be larger than |cos(θ)|. In order to get a positive value for r, we must therefore subtract the square root since the denominator is negative. Hence the solution we seek is \[ \begin{align} r_{sc} &= \frac{-\cos(\theta) - \sqrt{\cos^2(\theta)-2\cos(2\theta)}}{2\cos(2\theta)} \\ \\ &= \frac{-\cos(\theta) - \sqrt{2-3\cos^2(\theta)}}{4\cos^2(\theta)-2} \\ \\ &= \frac{1}{\sqrt{2-3\cos^2(\theta)}-\cos(\theta)} \end{align} \]

135° ≤ θ < 180°

When 135° ≤ θ < 180°, the self-contacting paths we want are L(LR) and R(RL). Here are two examples (starting with a right branch) with θ = 135° and θ > 135°.
self-contacting-path-135 self-contacting-path-140
θ = 135°
red = L
blue = R
θ = 140°
red = L
blue = R

The branch tip for R(RL) will correspond to the complex number \[ \begin{align} i &+ ir\alpha^{-1} + ir^2\alpha^{-2} + ir^3\alpha^{-1} + ir^4\alpha^{-2} + ir^5\alpha^{-1} + \cdots \\ \\ & = i\left( 1 + r\alpha^{-1} \left( 1 + r\alpha^{-1} + r^2 + r^3\alpha^{-1} + r^4 + \cdots \right) \right) \\ \\ & = i \left( 1 + r\alpha^{-1} \left( \frac{1}{1-r^2} + \frac{r\alpha^{-1}}{1-r^2} \right) \right) \\ \\ & = i \left( 1+ \frac{r\alpha^{-1} + r^2\alpha^{-2}}{1-r^2} \right) = iz. \end{align} \] Since \(x = \text{Re}(iz) = -\text{Im}(z)\), the scaling factor r must satisfy \[ \begin{align} 0 &= \frac{r\sin(\theta) + r^2\sin(2\theta)}{1-r^2} \\ \\ &= \frac{r\sin(\theta) + 2r^2\sin(\theta)\cos(\theta)}{1-r^2} \\ \\ &= \frac{r\sin(\theta) \left(1 + 2r\cos(\theta) \right)}{1-r^2} \end{align} \] Here the solution is \[ r_{sc} = -\frac{1}{2\cos(\theta)} \]

Notice that the x-coordinate at the end of the path RR is \(r\sin(\theta) + r^2\sin(2\theta)\), which, as shown above, is equal to 0 when r = rsc. By symmetry, the same will be true for the end of the path LL. This means that the paths R(RL) and L(LR) will touch at the y-axis at the end of every other branch.

self-contacting-path-140-sc
θ = 140°
r = rsc = 0.6527

 
 

References

  1. Mandelbrot, Benoit and Michael Frame. "The canopy and shortest path of a self-contacting fractal tree," The Mathematical Intelligencer, vol. 21, No. 2 (1999), 18-27.
  2. Mandelbrot, Benoit and Michael Frame. Geometry of Self-Contacting Binary Fractal Trees website.
  3. Pagon, Dusan. "Self-Similar Planar Fractals Based on Branching Trees and Bushes," Progress of Theoretical Physics Supplement, No. 150, 176-187.
  4. West, Don. "Self-Contacting Fractal Trees, Comments on and Mathematical Details for an article by Mandelbrot and Frame." Website http://web.archive.org/web/20120313124012/http://faculty.plattsburgh.edu/don.west/trees/Index.htm.