Symmetric Binary Trees with Branching Ratios Larger than 1

Year: 2017 Authors: Nick Mendler; Vincent J. Matsko

Core claim

Trees with branching ratio greater than 1 have canopies exactly corresponding to reciprocal-ratio trees under the paper’s scaling and symmetry construction.

Topics

fractal binary trees, duality of canopies, digital artwork, regular polygon growth

Domains

fractal geometry, recursion, symmetry, geometric scaling, digital art, generative art, visual design, symmetry-based composition

Methods

recursive tree generation, geometric proof, scaled rendering, visual comparison

Media

digital images, binary tree diagrams, polygon-based compositions

Paper text

The text below is the locally extracted OCR/Markdown version of the paper. Raw PDF files remain local and are not published here.

Bridges 2017 Conference Proceedings

Symmetric Binary Trees with Branching Ratios Larger than 1

Nick Mendler, Vincent J. Matsko University of San Francisco

nickmendler101@gmail.com, vince.matsko@gmail.com

Abstract

Here, we explore symmetric fractal binary trees with branching ratio greater than or equal to one. We then provide a relationship between trees with reciprocal ratios which illustrates a duality between trees with branching ratios smaller than one and trees with branching ratios larger than one. In addition, we present examples of digital artwork based on these binary trees.

Introduction

Symmetric binary fractal trees and their canopies have been discussed in numerous contexts (see [1] and [3]), and may be generated many ways – but their most intuitive generation is probably using recursion. After first drawing a vertical trunk of length 1, branches of length $r$ are drawn to the left and right of the trunk at an angle $\theta$ . See the left image in Figure 3 for an example.

Figure 1: Nine nonagon trees sprouting from a base nonagon.

Figure 2: Dual trees with alternating branching ratios.

This process is repeated recursively, scaling the branches by a factor of $r$ at each iteration. We refer to the collection of all points obtained after $n$ branchings of a tree as a canopy. Mandelbrot and Frame’s treatment in [3] covers the idea of minimum connectedness in depth. This and other papers (such as [1]) familiarize us with the family of canopy sets when r < 1 . We present artistic insights into the geometry of fractal trees and reflect upon trees with branching ratios $r\ge 1$ (see Figure 3). In fact, trees with branching ratio r > 1 have canopies related to those of trees with r < 1 , as we will see below. We defer a discussion

Mendler and Matsko

of the images in Figures 1 and 2 until the section on artwork, so that we may introduce the geometry of dual trees first.

Figure 3: Binary trees of 6 iterations with $\theta =25^{\circ }$ and $r=5/8$ (left), $r=1$ (middle), and $r=8/5$ (right).

Note that trees with r > 1 become unbounded as the depth increases. For any r > 0 , scaling a rendering to depth $n$ by the scale factor ${\sigma }_{r,n}={\left({\sum }_{i=0}^n{r}^i\right)}^{-1}$ keeps trees at any depth bounded, which is useful for producing graphical images.

Duality of Trees

Figure 4: Dual trees with 7-fold symmetry.

Figure 4 illustrates the concept of dual trees which was briefly introduced above. There are seven bold copies of a symmetric tree with turning angle $180/7^{\circ }$ and branching ratio $7/10$ ; however, the lighter structures in the background are actually made up of seven copies of a different symmetric binary tree! This tree also has a turning angle of $180/7^{\circ }$ , but now with a branching ratio which is greater than 1 - branches of these trees are a factor of $10/7$ longer than the branches they came from. Because this is a divergent process, the trunk of this tree is scaled by $(7/10{)}^n$ , where $n$ is the number of iterations which will be drawn, so that scaling by $10/7$ times will result in branches reaching a length of 1 at the final stage of drawing. Notably this ratio is the reciprocal of the ratio used for the lighter trees, and the collections of canopies of these trees are exactly the same.

Why do these trees overlap exactly? Let’s look at the two trees shown in Figure 5. The black tree has a branching ratio of $5/8$ and a branching angle of $25^{\circ }$ , and is rotated $25^{\circ }$ counterclockwise. The gray tree has a reciprocal branching ratio of $8/5$ , also with a branching angle of $25^{\circ }$ . Both are rendered to a depth of 5.

Now consider the thick, black path going from $O$ to $P$ , which is created by following the sequence of instructions $RRRLL$ ( $R$ meaning branch right, and $L$ meaning branch left). Make a symmetric path (thick, gray, dashed) starting at $P$ and going to $O$ . If we start at $P$ with the same trunk length we started with at $O$ and follow the exact same instructions, we have to end up back at $O$ .

The trick is to now look at this gray path backwards, starting from $O$ . The branches now get larger each time, by a factor of 8/5 (since they were getting smaller by a factor of 5/8 when going in the opposite direction). The size of the trunk is the length of the last branch drawn in following the black path from $O$ to $P$ . This must be $(5/8{)}^5$ times the length of the trunk, since the tree is of depth 5.

Symmetric Binary Trees with Branching Ratios Larger than 1

The sequence of instructions needed to follow this gray path is $RRLLL$ . It turns out this is easy to predict from the geometry. Recall that beginning at $P$ , we followed the instructions $RRRLL$ along the gray path to get to $O$ . When we reverse this path and go from $O$ to $P$ , we follow the instructions in reverse - except that in going in the reverse direction, what was previously a left turn becomes a right turn, and vice versa.

So all we need to do to get the reverse instructions is to reverse the string $RRRLL$ to get $LLRRR$ , and then change

the $L$ ‘s to $R$ ‘s and the $R$ ‘s to $L$ ‘s, yielding $RRLLL$ .

Figure 5: Dual trees with branching ratios of $5/8$ and $8/5$ .

There is one important detail to address: the fact that the black tree with branching ratio $5/8$ is rotated by $25^{\circ }$ to make everything work out. Again, this is easy to see from the geometry of the figure. Look at the thick gray path for a moment. Since following the instructions $RRLLL$ means that in total, you make one more left turn than you do right turns, the last branch of the path must be oriented $25^{\circ }$ to the left of your starting orientation (which was vertical). This tells you precisely how much you need to rotate the black tree to make the two paths have the same starting and ending points.

Note that not all the endpoints of the paths in these trees overlap. But with enough copies drawn (as in Figure 4), all the endpoints of one set of trees will exactly overlap with those of the trees with the reciprocal ratio. We note that this exact overlap is due to the way the scale factor is defined above.

Artwork

Figure 6: Tree with branching ratio $r=1$ .

Exploring fractal binary trees with $r\ge 1$ generated more results than could be visited and more questions than could be answered in this paper.

While divergent trees can be scaled according to their iteration such that they converge to unions of convergent trees, what about scaling and convergence when $r=1$ ? Can we extend our current technique of scaling to include convergence of trees when $r=1$ ? Can we characterize what appears to be the limiting shape of the canopies as seen in Figure 6? We conjecture that when the branching angle $\theta$ is $p/q\cdot 360^{\circ }$ , with $p/q$ in lowest terms, the canopy rendered to an iteration depth of $n$ with branching ratio equal to 1 will become denser in a regular $q$ -gon as $n$ gets larger and larger. Notice how the canopy in Figure 6, generated with branching angle $1/7\cdot 360^{\circ }$ degrees to a depth of twenty iterations starts to look like a filled-in regular heptagon.

Figure 7 shows how very unexpected structures can arise from the use of parameters which do not seem intuitively applicable to binary trees; in particular, the study of dual trees brings close attention to those trees

Mendler and Matsko

Figure 7: The structure of dual trees with thirteen fold symmetry and branching ratios very close to one.

near the critical point of $r=1$ . The discovery of a large space of interesting yet non-familiar trees which visually confirmed our ideas about duality inspired much of the research and artwork.

Returning to the discussion of the initial artwork, Figure 1 illustrates nine symmetric fractal trees built of nonagons, each growing from a face of the central nonagon. In general, a union of $n$ $n$ -gon trees with branching ratios $r$ and arranged with $n$ -fold symmetry will have the same canopy as $n$ $n$ -gon trees built of $n$ -gons ascending in size according to the ratio $1/r$ (the expanding trees must be drawn with base $n$ -gon scaled by $r^i$ , where $i$ is the number of iterations being rendered).

Figure 2 illustrates another variation on the theme of dual binary trees. In this image, the branching ratios alternate between 2 and $1/4$ for the seven copies of the lighter trees, and between $1/2$ and 4 for the one copy of the darker tree.

These pieces only begin to explore the parameter space of binary trees along with their dual trees. There is still much work yet to be done.

Acknowledgments

We would like to thank the referees for their valuable comments and suggestions.

References

[1] Espigule Pons, B., Generalized Self-Contacting Symmetric Fractal Trees, Symmetry: Culture and Science, Vol. 21, Nos. 1–4, 333–351, 2013. [2] Lindenmayer, A., and Prusinkiewicz, P., The Algorithmic Beauty of Plants, Springer-Verlag, New York, 1990. [3] Mandelbrot, B., and Frame, M., The Canopy and Shortest Path in a Self-Contacting Fractal Tree, The Mathematical Intelligencer, Volume 21, Number 2, 1999.