On the Fractal Structure of the Boundary of Dragon Curve [pdf]

Angel Chang <angelx@alum.mit.edu>
Tianrong Zhang <tianrong@ansoft.com>

Abstract: This paper discusses the fractal geometry of the boundary of the dragon curves by analyzing the boundary’s structure, calculating its Hausdorff dimension, and computing the area enclosed within the boundary. The algorithms for generating computer graphics for the boundary curves have also been included.

Fractals are everywhere in this world. From clouds, coastlines, leaves, to biological organs, many scientists can use fractal geometry to describe complex natural objects and processes [1-3]. Opening several new research areas in mathematics, geometry, and computer graphics, fractal geometry seems to describe natural shapes and forms more gracefully and succinctly than does Euclidean geometry,

The concept of scale invariance or self-similarity is an underlying theme in all fractal structures with many examples going back to the classical mathematicians. What we know so well as the Cantor set, the Koch curve, the Hilbert curve, are among these these classical irregular curves along with the dragon curve.

The dragon curve is a space filling curve with dimension 2 which originally came from the repeated folding of a long stripe of paper [4] in the same direction. After pleating the paper, it is then unfolded with each adjacent segments of paper formed into a right angle. The dragon curve emerges slowly with striking complexity and beauty. As shown in Figure 1, it is a construction that fills a finite area in a plane but has a fractal boundary. This same curve can also be constructed by a computer algorithm using IFS (Iterated Function Systems) or the chaos game [3].

Although the dragon curve has already been investigated in several papers, its boundary has remained unexplored. To alleviate this neglect, it is the purpose of this paper is to study the boundary of dragon curve. To do so, we partitioned the boundary into several pieces to find its IFS structure and then calculated the Hausdorff dimension of the boundary. Included in this paper are several algorithms to generate the boundary using a computer. Finally, we also computed the area enclosed by the border of the dragon curve.

While it is evident that the boundary of the dragon curve is a fractal with recurring self-similarity, its exact structure remains elusive. To discover its hidden pattern, we partition the complete boundary of the dragon curve into four similar pieces as shown in Figure 2. In order to investigate the geometry of the boundary, we examine one section of the border as shown in Figure 3. Upon observation, it is apparent that this piece can be constructed with an infinite number of self-similar copies of itself with different sizes and rotated at various angles.

To analyze the curve in Figure 3, let its size be represented by the length of line segment as shown in Figure 4. Placed in opposite directions, the first two copies and their sizes can be represented by the line segments A₁B₁ and B₁A₂ with

(1)

The rest of the infinite number of copies can be grouped into pairs with each pair containing two exact duplicates placed in the opposite directions. All pairs form an infinite sequence such that each element in the sequence is reduced by a factor of 2^1/2 , and rotated by an angle of -45 degrees with respect to the previous one, i.e.

for

(2)

Using the formula showed by Huchinson [5], the fractal dimension d of a self-similar curve constructed by N similar pieces with reduction factors can be calculated by solving the following equation:

(3)

For the curve as shown in Figure 3, it is easy to show that

(4)

and

for

(5)

By substituting (4) and (5) into (3), the equation for d can be rewritten as

(6)

When N ® ¥ , formula (6) results in

(7)

where

(8)

Solving equation (8) for x yields a real solution and two conjugated complex solutions. From the real solution, the fractal dimension d of the curve in Figure 3 can be expressed as

(9)

where ,

the numerical value of d is calculated to be approximately 1.523627085.

An alternative method to compute d is to partition the curve in Figure 3 into three similar pieces as shown in Figure 5. Then the equation for d is

(10)

which can be reduced to the same algebraic equation as (8) to yield the same solution for the fractal dimension d.

Since the boundary of dragon curve is composed of four copies of the curve we just examined, the fractal dimension of the entire boundary is also d = 1.523627085.

In accordance with the two different methods for determining the dimension of the boundary of the dragon curve, we present two different algorithms for generating the four sections making up the boundary. Like the first method for calculating d, Algorithm 1 uses the idea of separating the boundary into an infinite number of copies while Algorithm 2 corresponds with the second method by viewing the boundary as three similar pieces. From Figure 6 and Figure 7, we see that Algorithm 1 is quicker to converge and aesthetically more pleasing than Algorithm 2.

Algorithm 1 :

Algorithm 2:

To produce the entire boundary of the dragon curve, four similar pieces of the border, generated by the above algorithms, have to be arranged as shown in Figure 8. With a suitable scaling of n and the orientation of the curve, the pieces should fit together the boundary dragon curve

The boundary of the dragon curve can also be generated using the chaos game. For the generation of the boundary of the dragon curve using the chaos game, we utilize the IFS structure that we had analyzed earlier in Figure 5. According to the theory of the chaos game [2], the boundary as shown in Figure 5 can be generated by a random iterated system which corresponds the these three linear affine transformations.

T₁(x,y) = ((x-y)/4-1/2, (x+y)/4+1)
T₂(x,y) = ((y-x)/4+1/2, -(x+y)/4+1)
T₃(x,y) = ((x+y)/2+1, (y-x)/2)

Because the complete boundary is pieced together from four similar fractals, the computer is required to "play" four similar chaos games at the same time to generate the entire border. Figure 9 shows the progress of the boundary of the dragon curve as generated by the chaos game.

We now turn our attention to the area enclosed by the boundary of the dragon curve. To determine the area, let us consider the generation of the dragon curve by iteration as shown in Figure 10.

The area at any level i can approximated by adding up the number of squares that are enclosed by the segments. Because each square is formed by four segments and each segment is shared by two squares, the number of squares is equal to the number of segments multiplied by 2/4 and the total area can be represented by the following equation:

(11)

where d_i is the length of the segment and n_i, is the number of segments at level i.

Letting the initial length of the segment at level 0 be equal to a, d_i and n_i can be expressed

as follows:

and

(12)

From equations (11) and (12) we can compute the area of the dragon curve, represented by S, the limit of S_i as i approaches infinity.

(13)

Therefore, the area of the dragon curve is a²/2.

An alternate method to compute the area enclosed within the boundary of the dragon curve involves the second IFS boundary structure discussed. Letting b be the length shown in Figure 11 and S_i be the area enclosed by the border at any level i, we can calculate the area of the dragon curve by observing the changes in area from one level to the next. Notice that the starting area, S₀, is equal to 4b².

From Figure 11 it can be seen that as the level of generation increases, the boundary of the dragon curve folds in and out, increasing the area at one point and decreasing at another. Upon closer observation we notice from one level to the next, all these areas cancel with the exception of the areas of P1_i and P2_i. Because P1_i increases the area of the dragon curve and P2_i decreases it, the total area increases by P1_i-P2_i from level i to level i+1. Since P1_i=b²/2ⁱ and P2_i=b²/2ⁱ+1 the relation between S_i+1 and S_i is as follows:

(14)

From this equation we realize that from level i to level i+1, the area enclosed by the curve increases by .

Using (14), we get that the area enclosed by the boundary of the dragon curve is:

(15)

To reconcile this answer for the area with our first solution in equation (13), recall that the first solution uses the length a as shown in Figure 12. From the Pythagorean Theorem we know that a²=9b²+b² so that b²=a²/10. From here it becomes apparent that the two solutions from equations (13) and (15) are one and the same since S=5b²=a²/2.

In addition we can also calculate the area of each small shape of which the dragon curve is composed. Since it is self-evident that these shapes are similar we can determine the relationship between their size as shown in Figure 13.

Using the relationship between their linear dimension, we can determine the relationship between their areas and we find that .

From Figure 13 it is apparent that

(16)

Solving for T₀, we get T₀=0.4S.

Conclusion

Although at this point in time the dragon curve and its border seem no more than quaint examples of fractals, self-sirnilar structures creating order from chaos, there may come a time when the results from this little mathematical investigation prove to be useful in other areas of science as well. Fractals and chaos are after all, the footprints of nature, appearing here and everywhere and what is science but the quest for knowledge, about nature, this universe that we live in.

1. Mandelbrot, B. B., The Fractal Geometry of Nature, W. H. Freeman and Co., New York 1982.

2. Bansley, M., Fractals Everywhere, Academic Press, San Diego, 1988.

3. Peitgen, H.-O., Jurgens, H., Saupe, D., Chaos and Fractals (New Frontiers of Science ), Springer-Verlag, New York, 1992.

4. Crilly, A. J., Earnshaw, R. A., Jones, H., Fractals and Chaos, Springer-Verlag, New York, 1991.

5.Hutchinson, J., Fractal and Self-Similarity, Indiana University Journal of Mathematics 30 , 1981.