A Computer Algorithm for Determining the Hausdorff Dimension of Certain Fractals

Author(s): Lucy Garnett

Source: Mathematics of Computation, Vol. 51, No. 183 (Jul., 1988), pp. 291-300
Published by: American Mathematical Society
Stable URL: http://www.jstor.org/stable/2008592
Accessed: 08-10-2017 04:06 UTC

REFERENCES
Linked references are available on JSTOR for this article:
http://www.jstor.org/stable/2008592?seq=1&cid=pdf-reference#references_tab_contents
You may need to log in to JSTOR to access the linked references.

JSTOR is a not-for-profit service that helps scholars, researchers, and students discover, use, and build upon a wide
range of content in a trusted digital archive. We use information technology and tools to increase productivity and
facilitate new forms of scholarship. For more information about JSTOR, please contact support@jstor.org.

Your use of the JSTOR archive indicates your acceptance of the Terms & Conditions of Use, available at
http://about.jstor.org/terms

American Mathematical Society is collaborating with JSTOR to digitize, preserve and extend
access to Mathematics of Computation

This content downloaded from 201.131.90.36 on Sun, 08 Oct 2017 04:06:06 UTC
All use subject to http://about.jstor.org/terms
MATHEMATICS OF COMPUTATION
VOLUME 51, NUMBER 183
JULY 1988, PAGES 291-300

A Computer Algorithm for Determining

the Hausdorff Dimension of Certain Fractals

By Lucy Garnett

Abstract. A fractal is a set which has nonintegral Hausdorff dimension. Computation

of the dimension directly from the definition would be very time-consuming on a com-
puter. However, the dimension can be computed using Newton's method if there exists
a self-expanding map on the set. This technique is applied to compute the dimension of
the Julia set of the quadratic mapping z -z2 + c for small real values of c.

1. Fractals and Hausdorff Dimension. B. Mandelbrot [4] introduced the

word fractal as "a set for which the Hausdorff-Besicovitch dimension strictly exceeds
the topological dimension.' Whereas the topological dimension of any subset of the
plane is either one or two, the Hausdorff dimension may be nonintegral. Physicists
[7] use the word "strange" in this context.
Informally, the Hausdorff dimension of a subset X of a metric space can be
pictured by overlaying an n by n gridwork of boxes on X for arbitrarily large
values of n. In this manner, X is covered by n2 boxes. If X is linear, then only
n of the boxes intersect X, and X has Hausdorff dimension one. If X covers most
of the plane then approximately n2 of the boxes intersect X, and X has Hausdorff
dimension two. If X falls between the first and second case, then X intersects nd
boxes for some value of d between one and two, and X is a fractal with Hausdorff
dimension d. In other words, if X has dimension d, then approximately nd boxes
of size 1/n are needed to cover X. This might be of interest when drawing X on
some coarse device such as a graphics terminal, where a point on the device is in
reality a ball of size 1/n. Strictly speaking, the "gridwork picture" describes the
Minkowski dimension. It is equal to the Hausdorff dimension in all "nice" cases
which includes all the sets discussed in this paper. More formally:
Definition. Let C(e) be a covering on X by countably many balls {Bj(ri)}iEI
of radius ri < e. For each real number af > 0 form the sum >iI ri. Take the
infimum of the sum over all coverings C(e). Define a function Ha by taking the
limit of the infimums as e approaches zero. Notationally, this says

H, (X) = lim inf (Erg.

e-O~)kzEI/

This is a way of measuring the area needed to cover X by small balls, with the
convention that a ball of radius r has area ra. If af is too small, then H, (X) is
infinite. If af is too large, then H, (X) is zero. There is a unique value where
Received September 17, 1985; revised July 31, 1987.
1980 Mathematics Subject Classification (1985 Revision). Primary 58F21, 30D05.

?1988 American Mathematical Society

0025-5718/88 $1.00 + $.25 per page

291

This content downloaded from 201.131.90.36 on Sun, 08 Oct 2017 04:06:06 UTC
All use subject to http://about.jstor.org/terms
 292 LUCY GARNETT

this function passes from infinite to finite. This critical number 6 is the Hausdorff
dimension of X, and H<,(X) is the Hausdorff measure of X in v.
In some sense the Hausdorff dimension gives the number of linear dimensions.
See Rogers' book [8] for a fuller discussion. It is expensive and difficult to implement
this definition on a computer. However, if X has a self-expanding map, there is
another approach derived from theorems proven by R. Bowen [1] and D. Sullivan
[10].

THEOREM. Let f: X -+ X be an expanding complex analytic map. Then there

exists a unique probability measure m on X and a unique real number 6 such that
f expands m by a factor of If'16. Furthermore, the Hausdorff dimension of X is 6
and m represents Hausdorff measure. That is, for any measurable subset A of X
the following equation holds:

(*) m(f(A)) = A If'(z)18m(dz). z EA

Let us use this theorem to calculate the Hausdorff dimension of two well-known
sets.
Example 1. Let X be the entire 2-dimensional plane. Set f equal to the doubling
map. Namely, f(x, y) = (2x, 2y) and f satisfies the hypotheses of the theorem
above. Let m be the usual Lebesgue measure. If A is a subset of X, say a ball of
radius r, then m(A) = 7rr2 and m(f(A)) = 7r(2r)2 = 47rr2. Since f'(z) = 2 for all
values of z, we see that Eq. (*) is satisfied for a value of 6 equal to two. Uniqueness
of the solution implies that the plane has Hausdorff dimension two. Although this
result is by no means startling nor new, it is reassuring.
Example 2. Let X be the middle-third Cantor set. If we represent the points
in the unit internal [0,1] as sequences of zeros, ones and twos, then the Cantor set
consists of all those sequences which contain only zeros and twos. The expanding
self-map f is obtained by stretching the Cantor set by a factor of 3 and then laying
it over itself. More precisely, if z is between 0 and 1/3, then f (z) = 3z. Otherwise,
f (z) = 3z - 2. This is a double covering with derivative constantly equal to 3.
Let m be the Lebesgue measure. If A is a subset of X, then m(f(A)) = 2m(A).
Equation (*) is satisfied if 36 = 2. Solving for 6, we find that the Hausdorff measure
of the middle-third Cantor set is log 2/ log 3.
The Hausdorff dimensions of both these examples have been known for a long
time. The remainder of this paper is devoted to finding the Hausdorff dimension
of the Julia set of a quadratic map. There have been no previous numerical ap-
proximations to these dimensions. Indeed, they have only recently been found to
be nonintegral [10].

2. Julia Sets. Julia sets arise naturally in the study of the dynamical systems
formed by iterating complex analytic maps from the plane to itself. The study of
these systems was initiated in the early 1900's by P. Fatou and G. Julia. We shall
restrict our attention to quadratic maps of the form f (z) = z2 + c. A major concern
in the study of dynamical systems is the classification of orbits. The orbit of the
point z is the sequence of points z, f (z), f (f (z)), f (f (f (z))), ad infinitum. A main
question is: When does the orbit of a point converge to a fixed or periodic point, and
when does it have no such stability but instead moves around erratically? Consider

This content downloaded from 201.131.90.36 on Sun, 08 Oct 2017 04:06:06 UTC
All use subject to http://about.jstor.org/terms
 HAUJSDORFF DIMENSION OF CERTAIN FRACTALS 293

the example f(z) = Z2. Points inside the unit circle have orbits converging to the
origin. Points outside the unit circle converge to infinity. Points on the unit circle
itself (for the most part) move around the unit circle in a complicated manner.
Thus the complex plane is split into two different sets. The stable points are those
for which points nearby stay nearby under the action of f. In the above example
this corresponds to those points whose magnitude is not equal to one. The unstable
points are those for which nearby points spread apart. The latter set is called the
Julia set of the mapping f. It follows that f is a self-expanding map on the Julia
set.
The Julia set in the above example is the unit circle. However, if the map f
is perturbed just slightly by adding a small constant c to the z2 term, then the
Julia set becomes infinitely complicated. The first investigations of the morphol-
ogy of Julia sets go back to B. Mandelbrot [5]. The set of complex values c for
which the Julia set is connected is called the Mandelbrot set and is represented in
Figure 1 by the black set. This set is generated by using the following theorem [1]:
The Julia set of the function f(z) = z2 + c is connected if and only if the sequence
of sums c, c2 +c, (c2+C)2+C,. .. does not become infinite. Figures 2 and 3 represent

FIGURE 1

The Mandelbrot set is the dark area. The figure has symmetry about the real axis. The real part
of the main cartoid varies from -.75 to .25. The entire figure is contained within a box of length
4 centered at the origin. The leftmost point hits the edge of this box at (-2, 0). The algorithm
for computing the Hausdorff dimension works only for real values of c lying in the main cartoid.

This content downloaded from 201.131.90.36 on Sun, 08 Oct 2017 04:06:06 UTC
All use subject to http://about.jstor.org/terms
 294 LUCY GARNETT

FIGURE 2

The boundary of the dark region is the Julia set for a real value of c, approximately -.6, located

near the leftmost boundary of the main cartoid of the Mandelbrot set.

FIGURE 3

The boundary of the dark region is the Julia set for a real value of c, approximately .2, located

near the rightmost boundary of the main cartoid of the Mandelbrot set.

This content downloaded from 201.131.90.36 on Sun, 08 Oct 2017 04:06:06 UTC
All use subject to http://about.jstor.org/terms
 HAUSDORFF DIMENSION OF CERTAIN FRACTALS 295

_..

FIGURE 4

The boundary of the dark region is the Julia set for a complex value of c az~(-.6, .1). The algori
presented in this paper does not apply to this case.

the Julia sets for two real values of c occurring near the left and right boundaries of
the main cartoid-like body of the Mandelbrot set. They were generated by starting
with an unstable fixed point of f and performing a backwards iteration. This
algorithm works because the inverse orbit of any point in the Julia set is dense
in the Julia set [10]. Since f is expanding on the Julia set, f -1 is contracting on
the Julia set, and therefore backwards iteration is a stable procedure. Two sources
of detailed color pictures are Mandelbrot's book [4] and the August 1985 issue of
Scientific American. Figures 1, 2, 3 and 4 in this paper are courtesy of Dr. Alan
Norton, IBM Thomas J. Watson Research Center.
The question that we investigate is: How does the Hausdorff dimension of the
Julia set of z2 + c depend upon the value of c? Attention is now restricted to those
values of c lying inside the main body of the Mandelbrot set. D. Ruelle [9] proved
that the Hausdorff dimension is an analytic function of c. For c equal to zero we
have seen that the Julia set is the unit circle and therefore has Hausdorff dimension
equal to one. D. Sullivan [10] proved that for c greater than zero the Hausdorff
dimension is greater than one. For the remainder of the paper we consider only real

This content downloaded from 201.131.90.36 on Sun, 08 Oct 2017 04:06:06 UTC
All use subject to http://about.jstor.org/terms
 296 LUCY GARNETT

values of c in the main body. Hence from now on c is a real value lying between
-.75 and +.25. Since f is a self-expanding map on the Julia set, our algorithm
searches for a solution to Eq. (*). It uses Newton's method to do this. The idea
for the procedure is due to W. P. Thurston.

3. The Algorithm.

Step 1. Finite Approximation

We want to partition the Julia set of f(z) = z2 + C into many very small sets in
order to approximate the integral in Eq. (*) by finite sums. Choose an integer n.
We will generate a binary tree of depth n whose nodes are points on the Julia set
and partition the set into 2n pieces. First find the unique expanding fixed point of
f. This is achieved by solving the equation z2 _ z + c = 0. In general there are two
solutions, but the larger one is the expanding one. If we denote this solution by w,
then -w is the root of the binary tree. The rest of the tree is filled in by iterating f
backwards n times as described in the previous section. The children of a node are
the inverse image of their parent. The inverse image with smallest imaginary part
is the left child. This convention arranges the points at any given level in circular
order. The nth level will have 2n points z1, . . ., Z2r and determines a partition of
the Julia set into 2n subsets {Ai}1<i<2- centered about the points zi.

Step 2. Setting up Eq. (*)

Since the Ai are in circular order and f is a double covering on the Julia set, we
have
f(Ai) = A2i-1 U A2i
and
m(f(Ai)) = m(A2i-1) + m(A2i).
Ai is a small set with center zi, and we approximate the derivative function f'(z)
on Ai by f'(zi). Hence, a finite approximation of Eq. (*) is

m(A2i_1) + m(A2i) If'(zi) 1m(Ai) for all i.

Rewriting this equation, we get

(**) (m(A2i-1) + m(A2i))/If'(zi)18 m(Ai).

Equation (**) only holds when 6 is the Hausdorff dimension. If we view the left-
hand side of this equation as a transformation on measures, then we can restate
the problem as one of searching for a fixed point. More precisely, for any u > 0
define T, to be a linear operator on measures as follows:

Ta (m(Ai)) = (m(A2i-1) + m(A2i))/jf'(Zi)j'1

The problem then becomes to find a combination of 6 and m such that m is a fixed
point of T6. That is, T6 (m(Ai)) = m(Ai) for all i. This 6 will approximate the
Hausdorff dimension of X.

Step 3. Initial Conditions

Start the procedure with a guess of a = 1 and the uniform measure m(Ai) = 1/2n
for every i.

This content downloaded from 201.131.90.36 on Sun, 08 Oct 2017 04:06:06 UTC
All use subject to http://about.jstor.org/terms
 HAUSDORFF DIMENSION OF CERTAIN FRACTALS 297

Cs

InI I 6 I I

-0.8 -0 6 -04 -02 0.0 0.2 -0.10 -0.05 0.0 0.05 0.10

(a) (b)

co

c c

COi

(a) (
(d)

This content downloaded from 201.131.90.36 on Sun, 08 Oct 2017 04:06:06 UTC
All use subject to http://about.jstor.org/terms
 298 LUCY GARNETT

-0 006 -0 004 -0 002 0 0 0 002 0 004 0 006

(e)

FIGURES 5a-e

H(c) is the Hausdorff dimension of the Julia set generated by the mapping z z z2 + C. Since
Julia set generated by z -* z2 is the circle with dimension one, the graphs plot H (c) - 1 vs c
5a contains all the values calculated with c ranging from - .73 to .23. Figures 5b-5e represent
successive magnifications about the origin.

Step 4. Transformation of the Measure

Given a and m, iterate the transformation T, on the set of measures until an
eigenvector m, is found having eigenvalue K(u). This means that T,(m~,(Ai)) =
K u)m,(Ai). T, is a linear transformation, and the iteration will converge to
the largest eigenvector. Renormalization of the transformed measure after each
application of T, prevents the norm from approaching infinity. If the eigenvalue
equals one, then m, is a fixed point for T, and 6 = a is the Hausdorff dimension.
In that case, the algorithm terminates. Otherwise, we must change the value of a.

Step 5. Newton's Method Determines a New Choice of a

If we view the eigenvalue K(u) found in Step 4 as a function of a, then we are
looking for a satisfying K(a) = 1. This is equivalent to finding the point where the
function K(a) - 1 equals zero. Use Newton's method for finding roots of functions
to get
Unew = U +(1-K )/K()

Choose a small number E and use Step 4 to compute K(a + E). The derivative
K'(a) can then be approximated as

K'(a) ; (K(a + E) - K(a))/E.

This content downloaded from 201.131.90.36 on Sun, 08 Oct 2017 04:06:06 UTC
All use subject to http://about.jstor.org/terms
 HAUSDORFF DIMENSION OF CERTAIN FRACTALS 299

Step 6. Reset the Measure and Dimension

Let m now be the eigenvector mr and a be the unew found in Step 5. Go back
to Step 4. The loop terminates when Step 4 results in an eigenvalue of 1.

4. Discussion of the Results. This algorithm was implemented in the C

programming language on a VAX computer. The output is from a laser printer.
Figures 5a-e illustrate the results. Since the Hausdorff dimension is always at least
one, the graph is of H(c) - 1 where H(c) is the Hausdorff dimension of the Julia
set ofthe z -z2 +c.
This method works for any hyperbolic polynomial with connected Julia set; how-
ever, the algorithm requires the points on the Julia set to be kept in circular order.
This is easy to do when c has no imaginary part. We are currently working on a
program to extend this technique to complex values of c using analytic continua-
tion. The Julia sets for complex value of c look even more convoluted than for real
values, as is illustrated in Figure 4.
Although the program produces a beautiful curve, there remain some parts of the
theory not yet demonstrated. H(c) depends upon the number of iterations n used
to form the partition. There are severe space limitations on how large n can be,
since the number of points is an exponential function of n. A computer experiment
can be made to check how the Hausdorff dimension varies with the number of points
in the Julia set. It is done as follows. Compute the Hausdorff dimension for a fixed
number of iterations and then increase the number of iterations by one. Modify the
algorithm in Step 3 by initializing the process using the Hausdorff dimension just
computed for the smaller n and its corresponding eigenmeasure. If this is done,
then the process converges more rapidly, indicating that the previously computed
measure and dimension for the smaller value of n were already good approximations
to the correct solutions. The dimension appears to converge rather rapidly for small
values of c and more slowly for large values. But we do not have a proof that this
does converge, much less a handle on what the rate of convergence would be.

Acknowledgments. The author would like to thank Harvard University and

the University of Colorado at Boulder for providing computing time for this project.

Department of Statistics and Computer Information Systems

Baruch College
New York, New York 10038

1. R. BOWEN, "Hausdorff dimension of quasi-circles," Inst. Hautes Etudes Sci. Publ. Math., No.
50, 1979, pp. 11-25.
2. P. BLANCHARD, "Complex analytic dynamics on the Riemann sphere," Bull. Amer. Math.
Soc. (N.S.), v. 11, 1984, pp. 85-141.
3. A. DOUADY & J. HUBBARD, "Iteration des polynomes quadratiques complexes," C.R. Acad.
Sci. Paris Ser. I Math., v. 294, 1982, pp. 123-126.
4. B. MANDELBROT, The Fractal Geometry of Nature, Freeman, San Francisco, Calif., 1983.
5. B. MANDELBROT, "Fractal aspects of the iteration of z -* Az(1 - z) for complex A and z,"
Nonlinear Dynamics (Internat. Conf., New York, 1979), Ann. New York Acad. Sci., vol. 357, New
York Acad. Sci., New York, 1980, pp. 249-259.

This content downloaded from 201.131.90.36 on Sun, 08 Oct 2017 04:06:06 UTC
All use subject to http://about.jstor.org/terms
 300 LUCY GARNETT

6. V. A. NORTON, "Generation and display of geometric fractals in 3-D," Computer Graphics,

v. 16, 1982, pp. 61-67.
7. E. OTT, "Strange attractors and chaotic motions of dynamical systems," Rev. Modern Phys.,
v. 53, 1981, pp. 655-671.
8. C. A. ROGERS, Hausdorff Measures, Cambridge University Press, Oxford, 1970.
9. D. RUELLE, "Repellers for real analytic maps," Ergodic Theory Dynamical Systems, v. 2,
1982, pp. 99-108.
10. D. SULLIVAN, Seminar on Conformal and Hyperbolic Geometry, Inst. Hautes Etudes Sci. Sem-
inar notes, 1982, pp. 1-92.

This content downloaded from 201.131.90.36 on Sun, 08 Oct 2017 04:06:06 UTC
All use subject to http://about.jstor.org/terms