Download (direct link):
Random binary trees
Figure 6. Self-similar ramification matrices 3.5. Ramification matrices in physics Many studies have recently been made in physics concerning tree-like structures occuring in nature. We will quote for example electric breakdowns, Niemeyer, Pietronero, Wiesman , electrolytic metal deposit, Sawada, Dougherty, Gollub , the so-called viscous fingers, Nittmann, Daccord, Stanley , VanDamme et al.  or the well-known Dijfusion Aggregation Process (DLA) of Witten and Sanders ,and Ball  for a survey.
The patterns are (or approximated by) branching fractal structures. The visual aspect of these patterns is usually measured by physicists with a single number: the fractal mass dimension (see Mandelbrot ). Very recently, the branching structures of these patterns have been taken into account by applying the ramification matrix model, Vannimenus , Vannimenus, Viennot . The viscous fingers, the 2D DLA model and the so-called 2D branching Eden model have been studied. The ramification matrices are again self-similar. The corresponding curves are close to the one corresponding to random binary trees (see Figure 6). It is known that, in high dimension, these models should behave as random increasing binary trees. The difference between the two curves (associated to random binary and random increasing binary trees) of Figure 6 shows the strong influence of the planarity constraint. 4. Generation and visualization of trees using ramification matrices 4.1. Generation of the topological tree A stochastic triangular (s-l)xs matrix R is given, together with a number S<s. The algorithm generates randomly a binary tree T having Strahler number S and whose ramification matrix is (almost) the same as the one obtained by taking the rows 2 to S of R. This randomness insures a more natural aspect to the final image.
The generation starts with a tree T1 reduced to a single edge (its root edge) labelled S. Then, iteratively, a sequence Tn of labelled binary trees will be constructed. The tree Tn+1 is obtained from Tn by choosing one terminal edge of T11 labelled k*l, and by dividing this edge into two edges labelled respectively ê and i<k or both k-1. The choice (k,i) or (k-l,k-l) is made from a random selection according to the biorder distribution probability given by the êë row of the matrix R. The algorithm stops when all the terminal edges are labelled 1.
33Experiments show that the ramification matrix of the final tree T is close to the given matrix R, especially for the first rows (corresponding to the small orders) and when the size of the tree is sufficiently large (more than a few hundred nodes). The control of the size of the tree is made by choosing the Strahler number S. In the pictures below, the Strahler number is chosen between 5 and 10, with a size of the tree varying from a few hundred branching nodes to several thousand.
4.2. Orientation of the structure
In the algorithm described in 4.1, in the case of a biorder (k,i) with i<k, we have not completely described which edge (left or right son) receives the label ê (this edge will be called the main edge of the branching). The second step of the method is to make this choice explicit.
There are essentially four options in the program. The first is to make this choice randomly (usually with probability 1/2). The second option is to make this choice such that the main edges alternate (left and right) when moving along a segment of the tree. The third option is to fix the choice such that the main edge is always on the same side; this may give a simulation of a wind effect in the final image of the tree. The last option is to choose the orientation such that the main edge is closer to the vertical direction than the other edge. This choice cannot be decided until the coordinates of the branching nodes on a 2D or 3D image are computed (see below 4.3).
4.3. Generation of the geometrical tree
The third step of our method is the application of an elementary geometry, once the topological tree has been obtained, by determining the position in the space of each node of the tree.
By elementary geometry, we mean the choices (Figure 7):
- for each edge e, a width W(e) and a length L(e),
- for each branching node v, two angles O1(V) and 82(v),
-in the case of a 3D drawing, a third angle 03(v) is necessary, corresponding to the so-called phyllotaxy botanical phenomenon.
Figure 7. The 2D geometry : width, length and two branching angles.
One of the main ideas of our method is to make the width and length of an edge depend only on the order ê of that edge, and the two angles G1 and 02 relative to a branching node depend only on the biorder of that node.
We have chosen certain arbitrary laws for these four parameters, corresponding to a certain aesthetic effect of the image of the tree, together with a certain realism from the botany; for a more precise study, see Honda , Leopold , Mendes-France, Stevens, Usually, for botanical trees, as for many other natural branching patterns, the width of the branches decreases when moving from the root to the terminal nodes. In general, it is the same for the length of the branches, although the decrease is less important. Thus, it is natural to choose the laws of width and length as non-decreasing functions W(k) and L(k) of the order k. In the pictures presented below, the laws are linear or quadratic for L(k) and polynomial or exponential for W(k) : L(k) = ñ, * ê or L(k) = C1 * k2 ; W(k) = C2 * k" or W(k) = C2 * ?* with C1, c2, a and ? some numerical constants. For the choice of a, good visual aspects are obtained with a such that W(k) = c3 * L(k)s'2, that is a=S or S/2 in the quadratic or linear cases for the length.