Efficient Pythagorean trees: greed is good

Browne, C. Efficient Pythagorean trees : Greed is good LARS DBACWAE , €:

www.elsevier.com/locate/cag Chaos and Graphics Efficient Pythagorean trees: Greed is good Cameron Browne SWiSHzone.com Pty Ltd., The Basement, 33 Ewell St, Balmain 2041, Australia Abstract The Pythagorean tree is a fractal figure with a branching structure based upon the Pythagorean theorem. This paper describes the use of a greedy algorithm to encourage a homogenous spread of detail for asymmetrical trees and avoid localized regions of high detail. A model of prioritized branch growth based on this idea is used to optimize tree shape, allowing more visually interesting trees to be grown using significantly fewer segments. A comparison of the fractal dimension of the resulting shapes supports the general success of this approach. r 2007 Elsevier Ltd. All rights reserved. Keywords: Pythagorean tree; Greedy tree; Fractal; Box-counting dimension 1. Pythagorean trees The Pythagorean tree is a plane fractal constructed with squares, such that each triplet of touching squares forms a right triangle (Fig. 1). It is therefore a binary tree with the size of each parent node (a) related to the sizes of the left and right child nodes (b and c) by the Pythagorean theorem a2 ¼ b2+c2 [1]. Fig. 2 shows the first four iterations of the Pythagorean tree for y ¼ 451 (top row) and y ¼ 301 (bottom row); we denote such trees by their smallest internal angle as P45 and P30. The total number of segments s following each level of iteration i is the binomial number si ¼ 2i1 (sometimes called a Mersenne number). If the tree is generated level by level, then the segments will be created in the breadth-first order shown in Fig. 3. This order is breadth-first in the sense that from the singleroot node, all nodes of level 1 are grown, then from these level 1 nodes all nodes of level 2 are grown, and so on. Each segment’s breadth-first order (BFO) is related to its parent’s breadth-first order (BFOp) as follows: (1) BFO0 ¼ 1 for the root node, (2) BFOl ¼ 2BFOp for left children, and (3) BFOr ¼ 2BFOp+1 for right children. Tel.: +61 7 3371 1576. E-mail address: Cameron.Browne@swishzone.com. 0097-8493/$ - see front matter r 2007 Elsevier Ltd. All rights reserved. doi:10.1016/j.cag.2007.04.003 The breadth-first order indicates the distance between a given segment and the tree’s root. This can be seen graphically in Fig. 4, in which the segments of the first seven iterations of P25 are colour coded according to time of growth, so that blue represents earliest growth and red represents latest growth. For asymmetrical trees (yo451) the segments of latest growth vary in size across the figure, from areas of fine detail near the trunk to areas of coarse detail near the tip; this becomes increasingly pronounced the more asymmetrical the tree. A greedy approach will now be used to achieve a more homogenous spread of detail across the figure. 2. Greedy trees Given a set of choices in a computational problem, a greedy algorithm will always make the choice that appears to be the best at the time [2]. It makes a locally optimal choice in the hope that this will lead to a globally optimal solution. In the case of the Pythagoreans tree, the obvious ‘‘best choice’’ is to grow from the largest available segment at each step, encouraging the development of detail in more visible parts of the tree. Fig. 5 shows such a P25 greedy tree, which is similar to the tree shown in Fig. 4 (both are grown to i ¼ 7 giving 127 segments) except that the growth order is size-based rather than breadth-first in nature. It can be seen that the greedy

tree has a more homogenous spread of growth across its area at the expense of local detail, and that the points of latest growth are reasonably uniform in size. This tree is more efficient in that sense that it looks more complete for the same number of segments, and greedy growth maximizes the tree’s area coverage. Figs. 6 and 7 show the standard and greedy forms of trees P30 and P15 at i ¼ 12 (8191 segments). Note that the greedy forms are quite different in character, looking more complete and homogenous at the expense of fine detail. It can be seen that this effect is more pronounced for smaller values of y. By contrast, the two forms of the symmetrical tree P45 will be identical as the left and right children of each segment will be of equal size. 611 3. Branch prioritization We achieve a balance between these two extremes by prioritizing potential growth points based upon the relative importance of each. Given a linear weighting factor w that interpolates between the breadth-first (w ¼ 0) and greedy (w ¼ 1) forms, a segment’s branching priority p is given by wsn , p¼ ð1  wÞBF On where sn is the segment’s size normalized to the range 0–1 (inclusive) based upon the size of the tree’s root, and BFOn is the segment’s breadth-first order normalized to the range 0–1 (inclusive) based upon the total number of segments to be generated. Listing 1 shows C++ code for this weighted prioritization calculation for a given segment. Listing 2 shows C++ code for the prioritized tree growth algorithm, given a tree’s angle, greedy weighting factor w, and iteration depth i. The process starts by calculating an upper limit for the number of segments based upon i, then creating a root segment of unit size 1 and breadth-first order 1 and placing it in a priority queue (each segment is marked as a potential growth point as it is created). The highest priority segment is then removed from the front of the queue at each step, left and right children grown from it, and the children placed back in the queue according to their priority. This process is repeated until the upper limit on the number of segments is reached. Fig. 8 shows the outline of P30 at i ¼ 15 (65,535 segments) created a weighting factor of w ¼ 0:3 using this process. This weighting factor allows homogenous growth while maintaining a reasonable level of detail, using a relatively small number of segments. 4. Fractal dimension Fig. 1. Construction based upon the Pythagorean theorem. Assuming that trees with a greater level of detail across more of their area will be more visually interesting, we wish to optimize the greedy weighting factor w to achieve this. There is a biological analogy here, as real trees will Fig. 2. First four iterations of the Pythagorean trees P45 (top row) and P30 (bottom row).

generally grow in such a way as to maximize the surface area of their canopy. The fractal dimension, a measure of how completely a fractal shape fills an area or space, provides a convenient indicator for the level of detail across a shape. The fractal dimensions of similar tree structures have previously been calculated (for example, see [3] for detailed analyses); however, these are based upon trees with regular canopies, not greedy ones. The fractal dimension Db of the shape’s outline based upon the box-counting method [1] will be used instead. Db is calculated by rendering the figure at a series of increasingly coarser resolutions, counting the number of pixels (boxes) that contain at least part of the figure’s outline at each resolution, then finding the slope of the lineof-best-fit through a log plot of these values. This method Fig. 3. Breadth-first growth order of the standard tree. is fast and convenient for arbitrary shapes but loses accuracy for self-intersecting figures, as areas of intersection only get counted once per iteration. For this reason, the complete outline of the figure including intersections is used rather than its silhouette (as per Fig. 8), in an effort to minimize this inaccuracy. 5. Results Table 1 shows the resulting Db values for trees P5 through P45 with various weighting factors w in the range 0–1 (inclusive). In each case, the tree is grown to an iteration depth of i ¼ 12 for a total of 8191 segments. This data is shown graphically in Fig. 9. As expected, Db is generally greater for higher values of w. The Db of P45 is identical for all w as the shape of P45 is not changed by greedy growth; this can be taken as a baseline value. The Db of P40 is an anomaly as it is slightly greater for w ¼ 0 then tapers off imperceptibly as w increases, presumably due to inaccuracies in the boxcounting method. For the other trees, P5 through P35, it can be seen that Db is minimal for the breadth-first form (w ¼ 0) increasing monotonically with w to be maximal for the greedy form (w ¼ 1). This effect becomes more pronounced as y decreases, although most trees approach the baseline Db of P45 as w approaches 1. It should be pointed out that the fractal dimension of a figure actually applies to its limiting set, that is, its ultimate shape as its resolution approaches infinity. However, each of the measurements described above were taken at iteration depth i ¼ 12 which is essentially only a snapshot of the shape at an early stage of its potential development. The fact that higher values of w generally correspond to a greater fractal dimension indicates that for structures Fig. 4. Standard tree P25 for i ¼ {2, 3, 4, 5, 6, 7}.

Fig. 5. Greedy tree P25 for i ¼ {2, 3, 4, 5, 6, 7}. Fig. 6. Standard and greedy forms of P30 at i ¼ 12 (8191 segments). Fig. 7. Standard and greedy forms of P15 at i ¼ 12 (8191 segments). terminated at a finite depth (say i ¼ 12) than the greedier forms generally resemble the final form of the limiting set more closely, hence requiring fewer segments to visually approximate the figure’s ultimate shape. So what is the optimal greedy weighting w for a tree, given that lower values emphasize local detail while higher values emphasize homogeneity? Of the many trees generated, P30 with w ¼ 0:3 was the most aesthetically pleasing to the author (Fig. 8). It can be seen from Fig. 9 that Db reaches the baseline value and plateaus around w ¼ 0:3 for this tree, and that little advantage is gained from higher w; w ¼ 0:3 provides a

Returns: Branch priority in the range 0 to 1 (inclusive) // // Parameters: // w: Greedy weighting // 0 factor 0 to 1 (inclusive) where: = breadth-first 1 = greedy // // upper limit: Maximum number of tree segments // double CBranch::Priority(double w, int upper limit) // assume { return w * mBaseWidth - w) that the trunk is 1 unit wide + (1 * (m_BFO / (double)upper limit); } // Returns: // Pointer to the root of the new tree // // Parameters: // a: Branch angle // w: Greedy weighting // i: Iteration depth CBranch* GrowTree (double factor for branch prioritization // a, double w, int 1) { int upper limit CBranch* = pow(2, root = CPriorityQueue i) - 1; new CBranch (a); // upper // assume width=1 limit on tree size and BFO=1 queue; queue .Add (root); while (root->NumSegments() < upper limit) { // Grow from the highest-priority branch CBranch* parent CBranch* left = queue.RemoveHead () ; = parent->CreateChild (LEFT); queue.InsertInOrder( CBranch* right left, w, = parent->CreateChild(RIGHT); queue.InsertInOrder (right, w, } return root; // sets child values // sets child values upper limit); upper limit);

Fig. 8. Self-overlapping outline of P30 at i ¼ 15 (65,535 segments) for w ¼ 0:3. Table 1 Box-counting fractal dimension (Db) for Pythagorean trees of angles 5 through 45 for interpolations of w in the range 0–1 (inclusive) a¼5 a ¼ 10 a ¼ 15 a ¼ 20 a ¼ 25 a ¼ 30 a ¼ 35 a ¼ 40 a ¼ 45 w¼0 w ¼ 0.1 w ¼ 0.2 w ¼ 0.3 w ¼ 0.4 w ¼ 0.5 w ¼ 0.6 w ¼ 0.7 w ¼ 0.8 w ¼ 0.9 w¼1 1.062 1.135 1.213 1.316 1.369 1.422 1.460 1.503 1.483 1.205 1.247 1.302 1.379 1.438 1.468 1.480 1.496 1.483 1.245 1.265 1.323 1.396 1.450 1.475 1.483 1.497 1.483 1.271 1.277 1.342 1.409 1.458 1.480 1.485 1.497 1.483 1.282 1.288 1.357 1.417 1.463 1.483 1.486 1.497 1.483 1.296 1.304 1.369 1.426 1.468 1.485 1.487 1.497 1.483 1.304 1.320 1.381 1.432 1.472 1.487 1.488 1.500 1.483 1.312 1.341 1.394 1.439 1.476 1.491 1.489 1.501 1.483 1.319 1.368 1.410 1.449 1.481 1.494 1.490 1.501 1.483 1.335 1.399 1.427 1.461 1.487 1.498 1.491 1.501 1.483 1.349 1.428 1.447 1.472 1.493 1.501 1.493 1.502 1.483 only 65,535 segments are used, giving a potential 1000-fold saving. Weighted greedy trees allow significant savings for visually similar results, and do not require any knowledge of the display device resolution to be efficient. 6. Conclusion Fig. 9. Fractal dimension (Db) plotted against weighting factor w for trees P5 through P45. A greedy approach has been used to address the lack of homogenous spread of detail across asymmetrical Pythagorean trees. The shapes of the resulting trees can be customized by prioritizing tree growth based upon a linear interpolation between the standard and greedy forms, allowing the creation of visually interesting results with significantly fewer segments. A comparison of the fractal dimension Db of the resulting trees supports this observation in general.

Future work might include investigations into the applicability of this approach to branching structures other than Pythagorean trees, or, more generally, other than binary trees. Also, it may be warranted to further investigate the assertion that greedy snapshots more closely resemble a figure’s limiting set than nongreedy ones. References [1] Peitgen H, Jürgens H, Saupe D. Chaos and fractals: new frontiers of science. New York: Springer; 1992. [2] Cormen T, Leierson C, Rivest R. Introduction to algorithms. Cambridge: MIT Press; 1990. [3] Mandelbrot B, Frame M. The canopy and shortest path in a selfcontacting fractal tree. The Mathematical Intelligencer 1999;21(2):18–27.