# Box-Counting Dimension with finite resolution

1. Does the method of determining dimension of a shape via the Box-Counting dimension (Minkowski–Bouligand dimension) have to be performed on fractals (objects that look the same at all scales), or can it be performed on any shape? The coastline example seems to suggest that the method may be used to determine the dimension of any shape (since coastlines are not self-similar at all magnifications), but everything I've seen so far explicitly mentions the box-counting method as a tool for determining the dimensionality of fractals.

2. Must I necessarily send the limit of the size of the small boxes covering the shape to 0? I am interested in determining the (observed) dimension of an object given a finite resolution. (Ex: At low resolution, a ball of yarn will look 3D, but at high resolution, the ball of yarn is intrinsically 1D). My inclination is that if I am limited by a certain resolution, the (observed) dimensionality of the object may be a running quantity, but I can't find anything on the question one way or the other.

For completeness, box-counting dimension of a bounded set $E$ is defined by $$\dim(E) = \lim_{\varepsilon\rightarrow0} \frac{\log(N_{\varepsilon}(E))}{\log(1/\varepsilon)},$$ where $N_{\varepsilon}(E)$ represents the number of $\varepsilon$ mesh boxes (or squares or intervals, depending on the dimension of the ambient space) that intersect $E$.

1. There are a number of variations on the above definition, however. For example, $N_{\varepsilon}(E)$ might be defined as the minimum number of balls of radius $\varepsilon$ required to cover $E$ or the maximum number of disjoint balls of radius $\varepsilon$ with centers in $E$. There are other alternatives but they are all within a multiplicative factor of one another and, using the properties of the logarithm, it's not hard to show that they all yield the same value of the limit, if that limit exists.

However, that limit might not exist. So the correct answer to your first question is that the basic idea of box-counting dimension may be applied to any bounded set but it might or might not yield a result. A generalization is to replace the limit with a limit superior or limit inferior. This yields two new definitions of dimension - the upper box-counting dimension and the lower box-counting dimension. These two are well defined for any bounded set and the (unqualified) box-counting dimension is well defined precisely when the upper and lower dimensions are equal.

2. As you point out, it can be difficult to estimate box-counting dimension in real world examples, as we typically only have the value of $N_{\varepsilon}(E)$ for finitely many values of $\varepsilon$ and we certainly can't compute it for $\varepsilon=0$. Furthermore, when it comes to "real world" examples, as far as we know, the box-counting idea breaks down at the sub-atomic level.

The standard interpretation in the physics literature, as I understand it, is to presume that the relationship between $N_{\varepsilon}(E)$ and $\varepsilon$ should be maintained over a broad range of values. A standard way to compute the box-counting dimension is compute $N_{\varepsilon_k}(E)$ for some terms $\varepsilon_k$ chosen from a sequence that tends geometrically to zero. We then fit a line to the points in a log-log plot of $N_{\varepsilon}(E)$ versus $\varepsilon$. The box-counting dimension should be approximately the negative slope of that line.

• To paraphrase the last paragraph, "the standard interpretation is that you send $\epsilon\rightarrow 0$ and take the slope of Log(N) vs. Log $(1/\epsilon)$." I don't see a reason why dimension can't be a physically meaningful running quantity if you associate $\epsilon$ with a physical quantity (ex. max resolution). This may not exactly be related, but in the physical world definitions become different from their mathematical definitions. For example, the concept of 'infinity' may mean 1cm to a particle physicist, 10 LY to a New Horizons engineer, and the horizon distance to a cosmologist. – Bob Jul 22 '15 at 15:57
• @Bob Right - I'm not sure I see much difference between your statement and mine. I guess the main point that I should really emphasize is that the relationship should hold over many orders of magnitude. Thus, we measure $\log(N_{a^k})$ for some constant $a$ larger than $0$ and (much) less than $1$ as well as for a large number of $k$s. If the relationship between $\log(N_{a^k})$ and $a^k$ holds up over that range, then we see that the fractal object behaves the same on a wide range of scales. This is somewhat like self-similarity. – Mark McClure Jul 22 '15 at 18:56
• The way I understand what you are saying is that dimension is well defined in the limit $\epsilon\rightarrow 0$ (or in physical applications over a wide range of "small enough" $\epsilon$'s. I agree with this. What I want to say is that (for example) at low resolution (large box size), a grid will look 2-D, but at high resolution (small box size), the inherent 1-D nature of the grid is shown. I want to say that dimensionality (or at least some type of 'effective dimensionality') may be a running quantity that can change with resolution. – Bob Jul 22 '15 at 19:27
• @Bob Well, you lost me there. I'd say an $n$-dimensional grid looks, well, $n$-dimensional regardless of the resolution. Now, if you have an image that consists of a large number of line segments, then it might appear to have a fractal dimension at large resolution while, at small scales, the one-dimensional behavior of those segments might dominate. Is that the point you're trying to make? Regardless, we certainly don't expect $\log(N_{\varepsilon})/\log(1/\varepsilon)$ to be constant. If it's close to constant over a wide range, then that constant could be called the fractal dimension. – Mark McClure Jul 22 '15 at 19:42
• If my grid is the the squares on graph paper (say they are 1x1 in size), but my best resolution is 100x100, I'll see just a 2D sheet. The 1D (intrinsic) detail of the lines is washed out due to poor resolution. Now imagine that (through the magic of modern technology) I can improve my resolution to 0.01x0.01. I would say that the dimensionality that I observe changes due to the improved resolution. In a way this is the opposite of string theory, where a fundamentally 1D object can curl and wind back on itself to form a higher dimensional object at large scales. – Bob Jul 22 '15 at 19:59
1. You can compute the box-counting dimension for any bounded subset of $\mathbb{R}^n$ (for unbounded sets, e.g., a line, it does not work as well). For non-fractal sets the result agrees with other concepts of dimension (dimension of a vector space, dimension of a manifold). E.g., a line segment has dimension $1$ because it's covered by $\lceil \epsilon^{-1}\rceil$ intervals of length $\epsilon$.

2. It is worthwhile to consider the behavior of sets on finite scale, although this gets further away from measure theory and closer to computational geometry. Specifically, if $N(\epsilon)$ is the size of a minimal $\epsilon$-net, one can think of $d(\epsilon) = -\log N(\epsilon)/\log \epsilon$ as "dimension at scale $\epsilon$". See $\epsilon$-net article on Wikipedia for a starting point; a search for this term brings up a few relevant articles. A natural question is: what should one do with this "scale-dependent dimension" other than pointing at it?

• Thanks for the reply. In response to your answers: 1a. Am I not allowed to compute box-counting dimension on an infinite set due to the fact that the number of boxes N will diverge? 1b. What about shapes like the Sierpinksi triangle? [I'm not a maths person, but as far as I know....] This is an infinitely large object. Do we have to take a section of it and assume that the dimensionality of the section that we calculate with this method is identical to the dimensionality of the infinitely large sierpinski triangle? – Bob Jul 18 '15 at 22:58
• "Bounded" means "contained in a sufficiently large ball". The Sierpiński triangle is bounded, so you can compute the dimension in the usual way. The problem with unbounded objects such as a line is that they cannot be covered by finitely many boxes. – user147263 Jul 18 '15 at 23:00