Thursday, July 28, 2005

Measuring a Curve's Hausdorff Dimension

Suppose that you wanted to calculate the dimension of a particular fractal curve. Specifically, suppose that you wanted to calculate its Hausdorff dimension, a standard measure of fractal curves. Why would you want to do that? I know why I'd want to. For now, though, let's assume that calculating a fractal curve's Hausdorff dimension proves interesting in its own right. It does, after all, have its charms.

In the likely event that you've never dabbled in fractal geometry, you might want to start with explanation of the Hausdorff dimension (sometimes also called the "fractal dimension"). I'll offer a very quick explanation here. You can find a great many alternative explanations, with helpful illustrations, by way of Google.

In contrast to such things as lines and planes, fractal curves have non-integer, fractional dimensions. A line has one dimension. A plane has two. The Koch curve, a well-known fractal, falls in the dimension between a line and a plane. The Koch curve's infinitely recursive bends give it more dimensionality than a mere line, though they fall short of completely filling a plane. The Koch curve has a Hausdorff dimension of roughly 1.26.

How do we know the Hausdorff dimension of a fractal like the Koch curve? To calculate the Hausdorff dimension of a curve calls for measuring the arc length of the initiating curve that serves as the seed of the fractal one. Call that P. You also need to figure out the length, p, of the smaller units that replace the larger one and how many units, N, fit within arc length P.

For a curve of length P, made up of smaller copies itself of size p, the number of units, N, that fit within P is equal to the size ratio (P/p) raised to the power of the curve's Hausdorff dimension. By convention, we call that dimension, "d." In other words,

N = (P/p)

Solving for d by logarithmic conversion we get:

d = log N

Using the change of base formula for logarithmic functions,

d = log N/log (P/p)

(Per the usual convention, "log" without an indicated base means "log in base ten.")

Consider a few applications of the formula for d. Start with a simple, straight line 1 unit long. We can replace it with 3 copies of unit length 1/3. For a line, then,

d = log 3/log [1/(1/3)] = log 3/log 3 = 1

Now consider a plane. We can replace a square with side 1 unit long with 4 copies, each having sides 1/2 unit lengths long. For a square, then,

d = log 4/log [1/(1/2)] = log 4/log 2 = 2

You might wonder why we base p on the unit lengths of the square's sides rather than the area of the mini-squares. In brief, when we calculate the ratio of P/p, we are figuring out how many copies of P will fit within it if we reduce its linear size by a particular, identical amount in each of its Euclidean dimensions (not simply, "if we reduce its size by a particular amount.") You might think of P/p as a "magnification factor" that tells us how an object scales in terms of self-similarity. We don't want to read dimensionality into that factor by basing it on area, volume, etc. Rather, we use P/p in the formula "d = log N/log (P/p)" to measure an object's dimension.

In the above example, we've reduced a square measuring P units wide by P units tall by 1/2 in each of the two dimensions occupied by the square. That gives us four mini-squares, each 1/2 units wide by 1/2 units tall. We would get the same measure, d, of the square's dimensionality if we reduced the square by 1/3 in each of its two dimensions. That would give us nine mini-squares, each 1/3 unit wide by 1/3 unit tall. The formula would then look like this:

d = log 9/ log[1/(1/3)] = log 9/log 3 = 2

Now let's try calculating d for a fractal curve. In the case of a Koch curve, we begin with an initiator of length 1 and replace it with four copies, each 1/3 long. For a Koch curve, then,

d = log 4/log [1/(1/3)] = log 4/log 3 = 1.26 . . .

We now know how to approach the problem at hand: calculating d for a fractal curve. I'll return later with a description of the specific fractal curve that interests me and describe my attempts to calculate its Hausdorff dimension. Why bother? Because it amuses me to solve these problems and because it might amuse you to correct me if I unwittingly fail.


dgm said...

ouch. my head hurts.

Tom W. Bell said...

Sorry. I left of the warning header: