COMMENTS on the section called
"A Classification of Binary Trees"
Mathematical Details (and comments) for
an article by Mandelbrot and Frame:
Self-Contacting Fractal Trees.
by Don West, Department of Mathematics, SUNY Plattsburgh

Placing the root of the tree at the origin and choosing a trunk one unit tall (ending at (0,1) on the y-axis) Mandelbrot and Frame offer the following formulas for the y-coordinate of the point equation.gif

equation.gif

Picture of a tree Then they also claim that this y-value gives us the "total vertical extent of this branch sequence" and later "point of maximal height of the tree" (page 19). These claims, at least in their simple wording, are not true. In particular, if the angle theta is between 90 and 180 degrees and the ratio r is smaller than the (absolute value of) cosine of theta, then these tips are not at the top of the tree. In this case, the top of the tree is the top of the trunk. (See figure at right.)

Two branches of a tree
On the other hand, a large r (r just below one) can give a tree (with massive self-intersection) in which the tip point RLRLRL… does not give the highest point of the tree. The figure at the right shows just two branches of a tree with theta = 4*Pi/7 and r = .95. The tip RLRLRL… (shown in blue) has y-coordinate (rounding to) y = 8.088 while the tip point RRRRLRLRL… (shown in red) has y = 10.667.
We can get examples like this even with small theta values.
More analysis is needed here.

EQUATION (2) AS A CONDITION FOR TIP-CONTACT

For a given theta, we take N to be the smallest integer with N.theta less than 90

Mandelbrot and Frame offer the equation

equation.gif

which they label equation (2), as a condition for tip contact. The left side of the equation is the x-coordinate of the point LRN+1LRLRLR… . If this coordinate is zero, then the two symmetric branch tips RLN+1RLRLRL… and LRN+1LRLRLR… certainly coincide (on the y-axis). The authors imply that self-intersection occurs if and only if the branch length ratio r is chosen at least as large as the solution r of this equation (in the interval(0,1)) for a given theta. However, they offer no proof of this. More analysis is needed here.

It turns out that equation (2) can be written in many equivalent forms, some with no obvious relation to the original. Two of these alternate forms are:

equation.gif

equation.gif

I shall call these the cosine equation and the closed form (respectively). Clearly, the closed form can be written in many other ways.

In an e-mail note to Frame, I made the following claims for the first of these two alternate forms:

"Not only does my equation look nice, it makes it trivial to see that it has just one positive root, and to show that the value of the critical ratio r is a continuous function of theta, even at the critical angles pi/2n.

"My equation has an obvious interpretation in the geometry of the tree, though its geometric derivation is less obvious. Finally, there is a lovely relation to the Moran generator equation, which is explainable in terms of the geometric derivations of the two equations."

Next we shall show how to convert their equation (2) to the short cosine equation, and then discuss the advantages mentioned above.

CONVERTING EQUATION (2) TO THE COSINE EQUATION

We start with equation (2) in the form

equation3.gif

and clear the fraction by multiplication and distribute

equation.gif.

We combine the last two (separate) terms into the first sum, then we adjust the indices of the both sums

equation.gif

Now separate the first two terms from the first sum, noting that the second term is zero, then combine the two sums, term by term.

equation.gif

We move the negative term to the right side and we convert the summands, using the trigonometric identity equation.gif, to get

equation.gif

If the trunk of the tree is on the y-axis, then this equation is a condition for the tip of a path to have x-coordinate equal to zero. We note that the two common factors r and the sine of theta give trivial conditions for the tip to be on the y-axis (r = 0 and theta = 0) so we remove those two factors. Finally, we divide by 2 and arrive at the simple form

equation.gif

ADVANTAGES OF THE COSINE EQUATION

It looks nice, it is short and sweet.

It is easy to observe several useful features of the solution r (as a funcion of theta):

Notice that N is chosen so that the cosine sum is taken over exactly those successive terms with positive cosine values. For a particular value of theta, let

equation.gif.

Then equations.gif.

We see that S(r) is continuous, so there must be a value of r (0<r<1) where equation.gif.

The sum equation.gif defines and increasing function of r

(since each term is increasing).

Hence the solution of equation.gif such that 0<r<1 must be unique .

As theta decreases, the sum gets more and more terms, a new term being added each time theta crosses a value Pi/2n. We see that the two versions of the equation which meet at these special angles Pi/2n are identical. The implicit function theorem already tells us that each version (for each N) defines r as a continuous (indeed differentiable) function of theta. Since the equations agree at the breaks (Pi/2n) the solution is continuous everywhere.

A look at Figure 9 suggests that, for the angle theta in the range 0 to 90 degrees, the critical r-value (solution of equation (3)) is an increasing function of theta. A look at the cosine equation shows that this is true. As theta increases, all of the cosine values decrease so a larger r-value is required to get the sum equal to one half. (More on Figure 9 later.)

The Moran Generating Equation (p. 24) for the canopy (p. 21) is

equation.gif.

The striking similarity between the cosine equation and the Moran equation in not an accident. We show next a direct derivation of the cosine equation, using the same part of the canopy as is used in the derivation of the Moran equation.

Later, we will give a derivation of the second alternative form of equation (2).


[ NEXT ]      [ PREV. ]      [ INDEX ]      [ FEEDBACK ]

Copyright © 1999 All Rights Reserved