Hausdorff dimension

A way of assigning a number for "dimension" to shapes which are not as nice as a line or sphere, or more generally a manifold. A shape whose Hausdorff dimension is not an integer is a fractal (the term is due to Benoit Mandelbrot, he of the famous set). If you have seen the Koch snowflake, its Hausdorff dimension is log 4/log 3.

In more detail: We work throughout in a fixed Euclidean space Rⁿ. For each real number s ≥ 0, there is a measure H^s defined for subsets of Rⁿ. H^s is called s-dimensional Hausdorff measure (usually it's written with a capital script H). As the name suggests, H^s measures the "s-dimensional volume" of subsets of Rⁿ. The key idea in its construction is to notice that, for integer dimensions s and simple sets A (such as an s-dimensional box or ball), the s-dimensional volume of A is a constant multiple of the s-th power of the diameter of A. The constant for balls is 2^-sα(s), where α(s) is a conventional notation for the s-volume of the unit ball {|x| ≤ 1} in s-space. But there is a simple formula for α(s) in terms of the gamma function, which works for all real s ≥ 0:

α(s) = Γ(1/2)^s / Γ(1 + s/2). (*)

And we can certainly take non-integer powers of the diameter, so the formula

vol^s(A) = 2^-sα(s) diam A

works to define an s-dimensional volume function, at least for balls, which coincides with the ordinary volume when s is an integer. Now we use a procedure known in measure theory as Carathéodory's construction. It amounts to measuring the volume of an arbitrary set A by covering A with a collection of balls, adding up their volume, and then taking the limit as the maximum size of the balls shrinks to nothing. Given a (not necessarily finite) set {B_i} of balls, whose union covers A, define

vol^s(A; {B_i}) = ∑_i vol^s(B_i)     and     vol^s(A; t) = inf vol^s(A; {B_i})

where the infimum is taken over all coverings {B_i} of A by balls of maximum diameter t. Then defining

H^s(A) = lim_t→0 vol^s(A; t)

turns out to yield a measure with all the nice properties one wants in a measure, and which agrees with s-dimensional Lebesgue measure for integer s.

(*) To prove this, compute the integral of exp(-|x|²) in polar coordinates in Rⁿ, using Fubini's theorem and the fact that Γ(1/2) = π^1/2.

[Note also that in a metric space one can find the diameter of any set, not only a ball: diam A = sup {d(x,y) | x, y ∈ A}. Thus one could carry out Carathéodory's construction using coverings by members of a different family from the family of balls. In general one gets a different measure. For details see Federer, Geometric measure theory, 2.10.]

If you play with this definition for a while, what you find out is that for any given set A, there is at most one real number s so that 0 < H^s(A) < ∞. Intuitively, if you take a set and try to measure its volume using too small a dimension, you always get ∞, and if you try to measure its volume using too large a dimension, you always get 0. The unique break point between the ∞ range and the 0 range is called the Hausdorff dimension of A. (It is also possible for the volume at the break point itself to be 0 or ∞; for instance R has Hausdorff dimension 1 and infinite 1-volume.) Hausdorff dimensions are very hard to compute in practice, because none of the available definitions are very constructive. Using the definition above, it is not too hard to get an upper bound on something's Hausdorff dimension: just exhibit a refining sequence of coverings whose vol^s decreases to zero. It is much harder to get a lower bound because you must show that the vol^s of every refining sequence of coverings increases without bound. If the set you're interested in has a simple recursive structure, such as the Koch snowflake JerboaKolinowski describes below, then you can actually figure out the s which will yield a finite positive H^s, and compute that number, which relieves you of having to give bounds. But otherwise, you are more or less stuck.

To learn more about Hausdorff measures and other parts of the rigorous mathematical theory of fractal sets, you might turn to Geometric measure theory: a beginner's guide by Frank Morgan, or The geometry of fractal sets by Kenneth Falconer. For details on Carathéodory's construction and other technical matters, turn to the excellent but dense Geometric measure theory by Herbert Federer.

A complicated technical definition of the Hausdorff dimension is possible, which applies to a large class of metric spaces and objects embedded as sets of points within them. But, with the aid of some of the worst ascii-art you have ever seen, the following, simpler, illustration hopefully gives some idea of what is meant by the term.

Consider the Koch curve - we show here two successive stages in generating it:

            /\
           /  \
    ______/    \______

           _/\_
          |    |
    __/\__/    \__/\__

Well, it may not be obvious from the bad ascii representation, but we generate it by taking each line segment:

    __________________

and adding two additional lines, in the form of a triangular bump:

            /\
           /  \
    ______/    \______

This gives us four lines instead of one, and please note the length of each of these lines is (or should be) exactly one third the length of the original line.

Each of the resulting four lines is then modified the same way in the succeeding generation. This continues forever to produce the full, infinitely wiggly (i.e. fractal) Koch curve.

The idea of a fractal dimension is to provide a measure of this wiggliness - intuitively this will be between 1 and 2, since an infinitely wiggly line can be thought of as "more than a (1D) line, but less than a (2D) plane".

Now, imagine that we have a coin whose diameter is equal to the length of one of these four segments. In order to completely cover the line, we will need to use four such coins:

             ,.
           /\  `
     .-.  /| \ | 
    |___|/  \_\_____
    `._.'    
  

(well, because of the difficulties of ascii, I only show two. Pretend that they are four nice neat equal-sized circles, and the lines they cover are their diameters, please!)

Now, since the lines produced by the next modification are each one third the length of the lines shown above, we can see that if we reduce the size of the coin so that its diameter is one third the size, we will need four times as many coins to cover the resulting object.

This still applies on the completely constructed Koch curve: since the bumpy triangles aren't big enough to stick out over the top of coins whose diameters are the 'parent' lines (the lines that they are 'bumps' in), if we count how many coins of a certain diameter we need to cover the curve, and then how many coins we'd need when we reduce the diameter of the coin to a third of the previous size, we find we always need four times as many coins for each reduction.

And so the 'coin covering dimension' of the Koch curve can be expressed as 4/3 (or, 1.333...) - it's the ratio of the extra coins needed to the reduction of diameter of the coins: four times as many coins per threefold reduction in diameter.

The Hausdorff dimension is simply a generalised version of this idea, which works in a metric space of any integer dimension, with a few logarithms thrown in. Which is why the Hausdorff dimension of the Koch curve is log 4 / log 3, as stated in the above writeup.