2. B. Box-Counting Dimension

Definition of Box-Counting Dimension

For different side lengths r we count N(r), the smallest number of boxes of side length r needed to cover the shape.

How does N(r) depend on r?

If the shape is 1-dimensional, such as the line segment, we have seen N(r) = 1/r.

If the shape is 2-dimensional, such as the (filled-in) unit square, we have seen N(r) = (1/r)².

If the shape is 3-dimensional, such as the (filled-in) unit cube, we expect N(r) = (1/r)³.

For more complicated shapes, the relation between N(r) and 1/r may not be so clear.

If we suspect that N(r) is approximately k(1/r)^d, a power law relation, how can we find d? Taking Log of both sides of N(r) = k(1/r)^d, we obtain

Log(N(r)) = Log(k) + Log((1/r)^d) = dLog(1/r) + Log(k)

with the expectation that the approximation becomes better for smaller r.

Solving for d and taking the limit as r->0 gives

d_b = lim_r->0Log(N(r))/Log(1/r)

(Note as r->0 we have 1/r ->infinity, so Log(1/r)->infinity and Log(k)/Log(1/r) ->0.)

If the limit exists, it is called the box-counting dimension, d_b, of the shape.

This limit may be slow to converge; an alternate approach is to notice

Log(N(r)) = dLog(1/r) + Log(k)

is the equation of a straight line with slope d and y-intercept Log(k).

So plotting Log(N(r)) vs Log(1/r), the points should lie approximately on a straight line with slope d_b. This is the log-log approach to finding the box-counting dimension.

Return to Box-Counting Dimension.