13

Fractals & Statistical Growth

13.1 Fractional Dimension (Math)

Benoit Mandelbrot, who first studied fractional-dimension figures with supercomputers at IBM Research, gave them the name fractals [Mand 82]. Some geometric objects, such as Koch curves, are exact fractals with the same dimension for all their parts. Other objects, such as bifurcation curves, are statistical fractals in which elements of randomness occur and the dimension can be defined only locally or on the average.

Consider an abstract object such as the density of charge within an atom. There are an infinite number of ways to measure the “size” of this object. For example, each moment (rn) is a measure of the size, and there is an infinite number of moments. Likewise, when we deal with complicated objects, there are different definitions of dimension and each may give a somewhat different value. In addition, the fractal dimension is often defined by using a measuring box whose size approaches zero, which is not practical for realistic applications.

Our first definition of the fractional dimension df (or Hausdorff-Besicovitch dimension) is based on our knowledge that a line has dimension 1, a triangle has dimension 2, and a cube has dimension 3. It seems perfectly reasonable to ask if there is some mathematical formula that agrees with our experience with regular objects yet can also be used for determining fractional dimensions. For simplicity, let us consider objects that have the same length L on each side, as do equilateral triangles and squares, and that have uniform density. We postulate that the dimension of an object is determined by the dependence of its total mass upon its length:

where the power df is the fractal dimension. As you may verify, this rule works with the 1-D, 2-D, and 3-D regular figures in our experience, so it is a reasonable definition. When we apply (13.1)to fractal objects,we end up with fractional values for df. Actually, we will find it easier to determine the fractal dimension not from an object’s mass, which is extensive (depends on size), but rather from its density, which is intensive. The density is defined as mass/length for a linear object, as mass/area for a planar object, and as mass/volume for a solid object. That being the case, for a planar object we hypothesize that

13.2 The Sierpiski Gasket (Problem 1)

To generate our first fractal (Figure 13.1), we play a game of chance in which we place dots at points picked randomly within a triangle. Here are the rules (which you should try out in the margins now).

Mathematically, the coordinates of successive points are given by the formulas

where ri is a random number between 0 and 1 and where the integer function outputs the closest integer smaller than or equal to the argument. After 15,000 points, you should obtain a collection of dots like those on the left in Figure 13.1.

Figure 13.1 Left: A Sierpin´ski gasket containing 10,000 points constructed as a statistical fractal. Each filled part of this figure is self-similar. Right: A Sierpin´ski gasket constructed by successively connecting the midpoints of the sides of each equilateral triangle. (A–C) The first three steps in the process.

13.2.1 Sierpiski Implementation

Write a program to produce a Sierpin´ski gasket. Determine empirically the fractal dimension of your figure. Assume that each dot has mass 1 and that ρ = CLα. (You can have the computer do the counting by defining an array box of all 0 values and then change a 0 to a 1 when a dot is placed there.)

13.2.2 Assessing Fractal Dimension

The topology in Figure 13.1 was first analyzed by the Polish mathematician Sierpin´ski. Observe that there is the same structure in a small region as there is in the entire figure. In other words, if the figure had infinite resolution, any part of the figure could be scaled up in size and would be similar to the whole. This property is called self-similarity.

We construct a regular form of the Sierpin´ski gasket by removing an inverted equilateral triangle from the center of all filled equilateral triangles to create the next figure (Figure 13.1 right). We then repeat the process ad infinitum, scaling up the trianglesso each one has side r = 1 after each step. To see what is unusual about this type of object, we look at how its density (mass/area) changes with size and then apply (13.2) to determine its fractal dimension. Assume that each triangle has mass m and assign unit density to the single triangle:

Next, for the equilateral triangle with side L = 2, the density

We see that the extra white space in Figure 13.1B leads to a density that is ³₄ that of the previous stage. For the structure in Figure 13.1C, we obtain

We see that as we continue the construction process, the density of each new structure is ³₄ that of the previous one. Interesting. Yet in (13.2) we derived that

Equation (13.4) implies that a plot of the logarithm of the density ρ versus the logarithm of the length L for successive structures yields a straight line of slope

As is evident in Figure 13.1, as the gasket grows larger (and consequently more massive), it contains more open space. So even though its mass approaches infinity as L —>• oo, its density approaches zero! And since a 2-D figure like a solid triangle has a constant density as its length increases, a 2-D figure has a slope equal to 0. Since the Sierpiński gasket has a slope d f - 2 ~ -0.41504, it fills space to a lesser extent than a 2-D object but more than a 1-D object does; it is a fractal with dimension <1.6.

13.3 Beautiful Plants (Problem 2)

It seems paradoxical that natural processes subject to chance can produce objects of high regularity and symmetry. For example, it is hard to believe that something as beautiful and graceful as a fern (Figure 13.2 left) has random elements in it. Nonetheless, there is a clue here in that much of the fern’s beauty arises from the similarity of each part to the whole (self-similarity), with different ferns similar but not identical to each other. These are characteristics of fractals. Your problem is to discover if a simple algorithm including some randomness can draw regular ferns.

Figure 13.2 Left: A fern after 30,000 iterations of the algorithm (13.10). If you enlarge this, you will see that each frond has a similar structure. Right: A fractal tree created with the simple algorithm (13.13)

If the algorithm produces objects that resemble ferns, then presumably you have uncovered mathematics similar to that responsible for the shapes of ferns.

13.3.1 Self-affine Connection (Theory)

In (13.3), which defines mathematically how a Sierpiński gasket is constructed, a scaling factor of is part of the relation of one point to the next. A more general transformation of a point P = (x, y) into another point P’ = (x, y’) via scaling is

If the scale factor s > 0, anamplification occurs, whereas if s < 0,a reduction occurs. In our definition (13.3) of the Sierpin´ski gasket, we also added in a constant an. This is a translation operation, which has the general form

Another operation, not used in the Sierpin´ski gasket, is a rotation by angle θ:

The entire set of transformations, scalings, rotations, and translations defines an affine transformation (affine denotes a close relation between successive points). The transformation is still considered affine even if it is a more general linear transformation with the coefficients not all related by a single θ (in that case, we can have contractions and reflections). What is important is that the object created with these rules turns out to be self-similar; each step leads to new parts of the object that bear the same relation to the ancestor parts as the ancestors did to theirs. This is what makes the object look similar at all scales.

13.3.2 Barnsley’s Fern Implementation

We obtain a Barnsley’s fern [Barns 93] by extending the dots game to one in which new points are selected using an affine connection with some elements of chance mixed in:

To select a transformation with probability P, we select a uniform random number 0 ≤ r ≤ 1 and perform the transformation if r is in a range proportional to P:

The rules (13.10) and (13.11) can be combined into one:

Although (13.10) makes the basic idea clearer, (13.12) is easier to program.

The starting point in Barnsley’s fern (Figure 13.2) is (x₁, y₁) = (0.5, 0.0), and the points are generated by repeated iterations. An important property of this fern is that it is not completely self-similar, as you can see by noting how different the stems and the fronds are. Nevertheless, the stem can be viewed as a compressed copy of a frond, and the fractal obtained with (13.10) is still self-affine, yet with a dimension that varies in different parts of the figure.

13.3.3 Self-affinity in Trees Implementation

Now that you know how to grow ferns, look around and notice the regularity in trees (such as in Figure 13.2 right). Can it be that this also arises from a self-affine structure? Write a program, similar to the one for the fern, starting at (x₁, y₁) = (0.5, 0.0) and iterating the following self-affine transformation:

13.4 Ballistic Deposition (Problem 3)

There are a number of physical and manufacturing processes in which particles are deposited on a surface and form a film. Because the particles are evaporated from a hot filament, there is randomness in the emission process yet the produced films turn out to have well-defined, regular structures. Again we suspect fractals. Your problem is to develop a model that simulates this growth process and compare your produced structures to those observed.

13.4.1 Random Deposition Algorithm

The idea of simulating random depositions was first reported in [Vold 59], which includes tables of random numbers used to simulate the sedimentation of moist spheres in hydrocarbons. We shall examine a method of simulation [Fam 85] that results in the deposition shown in Figure 13.3. Consider particles falling onto and sticking to a horizontal line of length L composed of 200 deposition sites. All particles start from the same height, but to simulate their different velocities, we assume they start at random distances from the left side of the line. The simulation consists of generating uniform random sites between 0 and L and having a particle stick to the site on which it lands. Because a realistic situation may have columns of aggregates of different heights, the particle may be stopped before it makes it to the line, or it may bounce around until it falls into a hole. We therefore assume that if the column height at which the particle lands is greater than that of both its neighbors, it will add to that height. If the particle lands in a hole, or if there is an adjacent hole, it will fill up the hole. We speed up the simulation by setting the height of the hole equal to the maximum of its neighbors:

Figure 13.3 A simulation of the ballistic deposition of 20,000 particles on a substrate of length 200. The vertical height increases with the length of deposition time so that the top is the final surface.

Our sample simulation is Fractals/Film.java on the CD (available online: http://press.princeton.edu/landau_survey/) (FilmDim.java on the instructor’s CD), with the essential loop:

There sult soft his type of simulation show several empty regions scattered through-out the line (Figure 13.3), which is an indication of the statistical nature of the process while the film is growing. Simulations by Fereydoon reproduced the experimental observation that the average height increases linearly with time and produced fractal surfaces. (You will be asked to determine the fractal dimension of a similar surface as an exercise.)

13.5 Length of the British Coastline (Problem 4)

In 1967 Mandelbrot [Mand 67] asked a classic question, “How long is the coast of Britain?” If Britain had the shape of Colorado or Wyoming, both of which have straight-line boundaries, its perimeter would be a curve of dimension 1 with finite length. However, coastlines are geographic not geometric curves, with each portion of the coast often statistically self-similarto the entire coast yeton a reduced scale. In the latter cases the perimeter may be modeled as a fractal, in which case the length is either infinite or meaningless. Mandelbrot deduced the dimension of the west coast of Great Britain to be df = 1.25. In your problem we ask you to determine the dimension of the perimeter of one of our fractal simulations.

13.5.1 Coastlines as Fractals (Model)

The length of the coastline of an island is the perimeter of that island. While the concept of perimeter is clear for regular geometric figures, some thought is required to give it meaning for an object that may be infinitely self-similar. Let us assume that a map maker has a ruler of length r. If she walks along the coastline and counts the number of times N that she must place the ruler down in order to cover the coastline, she will obtain a value for the length L of the coast as Nr. Imagine now that the map maker keeps repeating her walk with smaller and smaller rulers. If the coast was a geometric figure or a rectifiable curve, at some point the length L would become essentially independent of r and would approach a constant. Nonetheless, as discovered empirically by Richardson [Rich 61] for natural coastlines, such as those of South Africa and Britain, the perimeter appears to be a function of r:

where M and df are empirical constants. For a geometric figure or for Colorado, df = 1 and the length approaches a constant as r → 0. Yet for a fractal with df > 1, the perimeter L → ∞ as r → 0. This means that as a consequence of self-similarity, fractals may be of finite size but have infinite perimeters. Physically, at some point there may be no more details to discern as r → 0 (say, at the quantum or Compton size limit), and so the limit may not be meaningful.

13.5.2 Box Counting Algorithm

Consider a line of length L broken up into segments of length r (Figure 13.4 left). The number of segments or “boxes” needed to cover the line is related to the size r of the box by

where C isaconstant.Aproposed definitionof fractional dimension is the power of r in this expression as r → 0. In our example, it tells us that the line has dimension df = 1. If we now ask how many little circles of radius r it would take to cover or fill a circle of area A (Figure 13.4 middle), we will find that

as expected. Likewise, counting the number of little spheres or cubes that can be packed within alarge sphere tells us thata sphere has dimension df = 3. In general, if it takes N little spheres or cubes of side r → 0 to cover some object, then the fractal dimension df can be deduced as

Figure 13.4 Examples of the use of box counting to determine fractal dimension. On the left the perimeter is being covered,in the middle an entire figure is being covered,and on the right a “coastline” is being covered by boxes of two different sizes (scales).

Here s ∝ 1/r is called the scale in geography, so r → 0 corresponds to an infinite scale. To illustrate, you may be familiar with the low scale on a map being 10,000 m to a centimeter, while the high scale is 100 m to a centimeter. If we want the map to show small details (sizes), we need a map of high scale.

We will use box counting to determine the dimension of a perimeter, not of an entire figure. Once we have a value for df, we can determine a value for the length of the perimeter via (13.15). (If you cannot wait to see box counting in action, on the CD (available online: http://press.princeton.edu/landau_survey/) you will find an applet Jfracdim that goes through all the steps of box counting before your eyes and even plots the results.)

13.5.3 Coastline Implementation and Exercise

Rather than ruin our eyes using a geographic map, we use a mathematical one. Specifically, with a little imagination you will see that the top portion of Figure 13.3

Figure 13.5 Dimensions of a line,box, and coastline determined by box counting.

looks likea natural coastline. Determine df by covering this figure, or one you have generated, with a semitransparent piece of graph paper¹, and counting the number of boxes containing any part of the coastline (Figures 13.4 and 13.5).

13.6 Correlated Growth, Forests, and Films (Problem 5)

It is an empirical fact that in nature there is increased likelihood that a plant will grow if there is another one nearby (Figure 13.6 left). This correlation is also valid for the “growing” of surface films, as in the previous algorithm. Your problem is to include correlations in the surface simulation.

13.6.1 Correlated Ballistic Deposition Algorithm

A variation of the ballistic deposition algorithm, known as the correlated ballistic deposition algorithm, simulates mineral deposition onto substrates on which den-drites form [Tait 90]. We extend the previous algorithm to include the likelihood that a freshly deposited particle will attract another particle. We assume that the probability of sticking P depends on the distance d that the added particle is from the last one (Figure 13.6 right):

Here η is a parameter and c is a constant that sets the probability scale.² For our implementation we choose η = -2, which means that there is an inverse square attraction between the particles (decreased probability as they get farther apart).

Figure 13.6 Left: A view that might be seen in the undergrowth of a forest or a correlated ballistic deposition. Right: The probability of particle i+1 sticking in some column depends on the distance d from the previously deposited particle i.

As in our study of uncorrelated deposition, a uniform random number in the interval [0,L] determines the column in which the particle will be deposited. We use the same rules about the heights as before, but now a second random number is used in conjunction with (13.23) to decide if the particle will stick. For instance, if the computed probability is 0.6 and if r < 0.6, the particle will be accepted (sticks); if r > 0.6, the particle will be rejected.

13.7 Globular Cluster (Problem 6)

Consider a bunch of grapes on an overhead vine. Your problem is to determine how its tantalizing shape arises. In a flash of divine insight, you realize that these shapes, as well as others such as those of dendrites, colloids, and thin-film structure, appear to arise from an aggregation process that is limited by diffusion.

13.7.1 Diffusion-Limited Aggregation Algorithm

A model of diffusion-limited aggregation (DLA) has successfully explained the relation between a cluster’s perimeter and mass [W&S 83]. We start with a 2-D lattice containing a seed particle in the middle, draw a circle around the particle, and place another particle on the circumference of the circle at some random angle. We then release the second particle and have it execute a random walk, much like the one we studied in Chapter 5, “Monte Carlo Simulations,” but restricted to vertical or horizontal jumps between lattice sites. This is a type of Brownian motion that simulates diffusion. To make the model more realistic, we let the length of each step vary according to a random Gaussian distribution. If at some point during its random walk, the particle encounters another particle within one lattice spacing, they stick together and the walk terminates. If the particle passes outside the circle from which it was released, it is lost forever. The process is repeated as often as desired and results in clusters (Figure 13.7 and applet dla).

Listing 13.1 Column.java simulates correlated ballistic deposition of minerals onto substrates on which dendrites form.

Because many particles are lost, you may need to generate hundreds of thousands of particles to form a cluster of several hundred particles.

13.7.2 Fractal Analysis of a DLA (or Pollock) Graph; Assessment

A cluster generated with the DLA technique is shown in Figure 13.7. We wish to analyze it to see if the structure is a fractal and, if so, to determine its dimension. (As an alternative, you may analyze the fractal nature of the Pollock painting in Figure 13.8, a technique used to determine the authenticity of this sort of art.) As a control, simultaneously analyze a geometric figure, such as a square or circle, whose dimension is known. The analysis is a variation of the one used to determine the length of the coastline of Britain.

The graph we generated had a slope of -0.36, which corresponds to a fractal dimension of 1.66. Because random numbers are involved, the graph you generate will be different, but the fractal dimension should be similar. (Actually, the structure is multifractal, and so the dimension varies with position.)

13.8 Fractal Structures in a Bifurcation Graph (Problem 7)

Recollect the project involving the logistics map where we plotted the values of the stable population numbers versus the growth parameter µ. Take one of the bifurcation graphs you produced and determine the fractal dimension of different parts of the graph by using the same technique that was applied to the coastline of Britain.

13.9 Fractals from Cellular Automata

We have already indicated in places how statistical models may lead to fractals. There is a class of statistical models known as cellular automata that produce complex behaviors from very simple systems. Here we study some.

Cellular automata were developed by von Neumann and Ulam in the early 1940s (von Neumann was also working on the theory behind modern computers then). Though very simple, cellular automata have found applications in many branches of science [Peit 94, Sipp 96]. Their classic definition is [Barns 93]:

The program CellAut.java given on the CD (available online: http://press.princeton.edu/landau_survey/) creates a simple 1-D cellular automaton that grows on your screen. A cellular automaton in two dimensions consists of a number of square cells that grow upon each other. A famous one, invented by

Conway in the 1970s, is Conway’s Game of Life. In this, cells with value 1 are alive, while cells with value 0 are dead. Cells grow according to the following rules:

A variation on the Game of Life is to include a “rule one out of eight” that a cell will be alive if exactly one of its neighbors is alive, otherwise the cell will remain unchanged. The program OutofEight.java (Listing 13.2) starts with one live cell at the center of the 3-D array cell[34][34][2] and grows on your screen from there.

Listing 13.2 OutofEight.java is an extension of Conway’s Game of Life in which cells always revive if one out of eight neighbors is alive.

Figure 13.9 The rules for two versions of the Game of Life, given graphically on the top row, create the gaskets below. (Output of this sort is obtained from the applet JCellAut on the CD (available online: http://press.princeton.edu/landau_survey/).)

In 1983 Wolfram developed the statistical mechanics of cellular automata and indicated how one can be used to generate a Sierpiński gasket [Wolf 83]. Since we have already seen that a Sierpiński gasket exhibits fractal geometry (§13.2), this represents a microscopic model of how fractals may occur in nature. This model uses eight rules, given graphically at the top of Figure 13.9, to generate new cells from old. We see all possible configurations for three cells in the top row, and the begetted next generation in the row below. At the bottom of Figure 13.9 is a Sierpiński gasket of the type created by the applet JCellAut on the CD (under Applets). This plays the game and lets you watch and control the growth of the gasket.

13.10 Perlin Noise Adds Realism

We have already seen in this chapter how statistical fractals are able to generate objects with a striking resemblance to those in nature. This appearance of realism may be further enhanced by including a type of coherent randomness known as Perlin noise. The resulting textures so resemble those of clouds, smoke, and fire that one cannot help but wonder if a similar mechanism might also be occurring in nature. The technique we are about to discuss was developed by Ken Perlin of New York University, who won an Academy Award (an Oscar) in 1997 for it and has continued to improve it [Perlin]. This type of coherent noise has found use in important physics simulations of stochastic media [Tick 04], as well as in video games and motion pictures (Tron).

Figure 13.10 Left: The rectangular grid used to locate a square in space and a corresponding point within the square. As shown with the arrows, unit vectors gi with random orientation are assigned at each grid point. Right: A point within each square is located by drawing the four pi. The gi vectors are the same as on the left.

The inclusion of Perlin noise in a simulation adds both randomness and a type of coherence among points in space that tends to make dense regions denser and sparse regions sparser. This is similar to our correlated ballistic deposition simulations (§13.6.1) and related to chaos in its long-range randomness and short-range correlations. We start with some known function of x and y and add noise to it. For this purpose Perlin used the mapping or ease function (Figure 13.11 right)

As a consequence of its S shape, this mapping makes regions close to 0 even closer to 0, while making regions close to 1 even closer (in other words, it increases the tendency to clump, which shows up as higher contrast). We then break space up into a uniform rectangular grid of points (Figure 13.10 left) and consider a point (x, y) within a square with vertices (x₀, y₀), (x₁, y₀), (x₀, y₁), and (x₁, y₁). We next assign unit gradients vectors g₀–g₃ with random orientation at each grid point. A point within each square is located by drawing the four pi vectors (Figure13.10 right):

Next the scalar products of the p’s and the g’s are formed:

As shown on the left in Figure 13.11, the numbers s, t, u, and v are assigned to the four vertices of the square and represented there by lines perpendicular to the square with lengths proportional to the values of s, t, u, and v (which can be positive or negative).

Figure 13.11 Left: The numbers s,t,u,and v are represented by perpendiculars to the four vertices, with lengths proportional to their values. Right: The function 3p² - 2p³ is used as a map of the noise at a point like (x,y) to others close by.

The actual mapping proceeds via a number of steps (Figure 13.12):

Perlin’s original C code to accomplish this mapping (along with other goodies) is found in [Perlin]. It takes as input the plot of random points (r₂i, r₂i₊₁) on the left in Figure 13.13 (which is the same as Figure 5.1) and by adding coherent noise produces the image on the right in Figure 13.13. The changes we made from the original program are (1) including an int before the variables p[], start, i, and j, and (2) adding # include <time.h> and the line srand(time(NULL)); at the beginning of method init () in order to obtain different random numbers each time the program runs. The main method of the C program we used is below. The program outputs a data file that we visualized with OpenDX to produce the image montania.tiff on the right in Figure 13.13.

13.10.1 Including Ray Tracing

Ray tracing is a technique that renders an image of a scene by simulating the way rays of light actually travel [Pov-Ray]. To avoid tracing rays that do not contribute to the final image, ray-tracing programs start at the viewer, trace rays backward onto the scene, and then back again onto the light sources.You can vary the location of the viewer and light sources and the properties of the objects being viewed, as well as atmospheric conditions such as fog, haze, and fire.

As an example of what can be done, on the left in Figure 13.14 we show the output from the ray-tracing program Pov-Ray [Pov-Ray], using as input the coherent random noise on the right in Figure 13.13. The program options we used are given in Listing 13.3 and are seen to include commands to color the islands, to include waves, and to give textures to the sky and the sea. Pov-Ray also allows the possibility of using Perlin noise to give textures to the objects to be created. For example, the stone cup on the right in Figure 13.14 has a marblelike texture produced by Perlin noise.

Figure 13.14 Left: The output from the Pov-Ray ray-tracing program that took as input the 2-D coherent random noise plot in Figure 13.13 and added height and fog. Right: An image of a surface of revolution produced by Pov-Ray in which the marblelike texture is created by Perlin noise.

Listing 13.3 Islands.pov in the Codes/Animations/Fractals/ directory gives the Pov-Ray ray-tracing commands needed to convert the coherent noise random plot of Figure 13.13 into the mountainlike image on the left in Figure 13.14.

13.11 Quiz

1 Yes, we are suggesting a painfully analog technique based on the theory that trauma leaves a lasting impression. If you prefer, you can store your output as a matrix of 1 and 0 values and let the computer do the counting, but this will take more of your time!

2 The absolute probability, of course, must be less than one, but it is nice to choose c so that the relative probabilities produce a graph with easily seen variations.

3 We indicated how to do this in §6.8.1.