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)2. |
If the shape is 3-dimensional,
such as the (filled-in) unit cube,
we expect N(r) = (1/r)3. |
|
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) = d⋅Log(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 |
db = limr → 0Log(N(r))/Log(1/r) |
(Note as r → 0 we have 1/r → ∞, so
Log(1/r) → ∞ and Log(k)/Log(1/r) → 0.) |
If the limit exists, it is called the
box-counting dimension, db, of the shape. |
This limit may be slow to converge; an alternate approach is to notice |
Log(N(r)) = d⋅Log(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 db. This is the
log-log approach to finding the box-counting dimension. |