Minkowski-Bouligand dimension
Encyclopedia
In fractal geometry, the Minkowski–Bouligand dimension, also known as Minkowski dimension or box-counting dimension, is a way of determining the fractal dimension
of a set S in a Euclidean space
Rn, or more generally in a metric space
(X, d).
To calculate this dimension for a fractal S, imagine this fractal lying on an evenly-spaced grid, and count how many boxes are required to cover
the set. The box-counting dimension is calculated by seeing how this number changes as we make the grid finer.
Suppose that N(ε) is the number of boxes of side length ε required to cover the set. Then the box-counting dimension is defined as:
If the limit
does not exist then one must talk about the upper box dimension and the lower box dimension which correspond to the upper limit
and lower limit respectively in the expression above. In other words, the box-counting dimension is well defined only if the upper and lower box dimensions are equal. The upper box dimension is sometimes called the entropy dimension, Kolmogorov dimension, Kolmogorov capacity or upper Minkowski dimension, while the lower box dimension is also called the lower Minkowski dimension.
The upper and lower box dimensions are strongly related to the more popular Hausdorff dimension
. Only in very specialized applications is it important to distinguish between the three. See below for more details. Also, another measure of fractal dimension is the correlation dimension
.
. The covering number
is the minimal number of open balls of radius ε required to cover
the fractal, or in other words, such that their union contains the fractal. We can also
consider the intrinsic covering number
, which is defined the same way but with the additional requirement that the centers of the open balls lie inside the set S. The packing number 
is the maximal number of disjoint balls of radius ε one can situate such that their centers would be inside the fractal. While N, Ncovering, Ncovering and Npacking are not exactly identical, they are closely related, and give rise to identical definitions of the upper and lower box dimensions. This is easy to prove once the following inequalities are proven:
These, in turn follow with a little effort from the triangle inequality
.
The advantage of using balls rather than squares is that this definition generalizes to any metric space
. In other words, the box definition is "external" — one needs to assume the fractal is contained in a Euclidean space
, and define boxes according to the external structure "imposed" by the containing space. The ball definition is "internal". One can imagine the fractal disconnected from its environment, define balls using the distance between points on the fractal and calculate the dimension (to be more precise, the Ncovering definition is also external, but the other two are internal).
The advantage of using boxes is that in many cases N(ε) may be easily calculated explicitly, and that for boxes the covering and packing numbers (defined in an equivalent way) are equal.
The logarithm
of the packing and covering numbers are sometimes referred to as entropy numbers, and are somewhat analogous (though not identical) to the concepts of thermodynamic entropy
and information-theoretic entropy, in that they measure the amount of "disorder" in the metric space or fractal at scale
, and also measure how many "bits" one would need to describe an element of the metric space or
fractal to accuracy
.
Another equivalent definition for the box counting dimension, which is again "external", is given by the formula
where for each r > 0, the set
is defined to be the r-neighborhood of S, i.e. the set of all points in 
which are at distance less than r from S (or equivalently, 
is the union of all the open balls of radius r which are centered at a point in S).
However, they are not countably
additive, i.e. this equality does not hold for an infinite sequence of sets. For example, the box dimension of a single point is 0, but the box dimension of the collection of rational number
s in the interval [0, 1] has dimension 1. The Hausdorff dimension
by comparison, is countably additive.
An interesting property of the upper box dimension not shared with either the lower box dimension or the Hausdorff dimension is the connection to set addition. If A and B are two sets in a Euclidean space then A + B is formed by taking all the couples of points a,b where a is from A and b is from B and adding a+b. One has
, lower box dimension, and upper box dimension of the Cantor set
are all equal to log(2)/log(3). However, the definitions are not equivalent.
The box dimensions and the Hausdorff dimension are related by the inequality
In general both inequalities may be strict. The upper box dimension may be bigger than the lower box dimension if the fractal has different behaviour in different scales. For example, examine the interval
[0, 1], and examine the set of numbers satisfying the condition
The digits in the "odd places", i.e. between 22n+1 and 22n+2 − 1 are not restricted and may take any value. This fractal has upper box dimension 2/3 and lower box dimension 1/3, a fact which may be easily verified by calculating N(ε) for
and noting that their values behaves differently for n even and odd. To see that the Hausdorff dimension may be smaller than the lower box dimension, return to the example of the rational numbers in [0, 1] discussed above. The Hausdorff dimension of this set is 0.
Another example: The set of rational numbers
, a countable set with 
, has 
because its closure, 
, has dimension 1.
Box counting dimension also lacks certain stability properties one would expect of a dimension. For instance, one might expect that adding a countable set would have no effect on the dimension of a set. This property fails for box dimension. In fact
Fractal dimension
In fractal geometry, the fractal dimension, D, is a statistical quantity that gives an indication of how completely a fractal appears to fill space, as one zooms down to finer and finer scales. There are many specific definitions of fractal dimension. The most important theoretical fractal...
of a set S in a Euclidean space
Euclidean space
In mathematics, Euclidean space is the Euclidean plane and three-dimensional space of Euclidean geometry, as well as the generalizations of these notions to higher dimensions...
Rn, or more generally in a metric space
Metric space
In mathematics, a metric space is a set where a notion of distance between elements of the set is defined.The metric space which most closely corresponds to our intuitive understanding of space is the 3-dimensional Euclidean space...
(X, d).
To calculate this dimension for a fractal S, imagine this fractal lying on an evenly-spaced grid, and count how many boxes are required to cover
Cover (topology)
In mathematics, a cover of a set X is a collection of sets whose union contains X as a subset. Formally, ifC = \lbrace U_\alpha: \alpha \in A\rbrace...
the set. The box-counting dimension is calculated by seeing how this number changes as we make the grid finer.
Suppose that N(ε) is the number of boxes of side length ε required to cover the set. Then the box-counting dimension is defined as:
If the limit
Limit of a function
In mathematics, the limit of a function is a fundamental concept in calculus and analysis concerning the behavior of that function near a particular input....
does not exist then one must talk about the upper box dimension and the lower box dimension which correspond to the upper limit
Limit superior and limit inferior
In mathematics, the limit inferior and limit superior of a sequence can be thought of as limiting bounds on the sequence...
and lower limit respectively in the expression above. In other words, the box-counting dimension is well defined only if the upper and lower box dimensions are equal. The upper box dimension is sometimes called the entropy dimension, Kolmogorov dimension, Kolmogorov capacity or upper Minkowski dimension, while the lower box dimension is also called the lower Minkowski dimension.
The upper and lower box dimensions are strongly related to the more popular Hausdorff dimension
Hausdorff dimension
thumb|450px|Estimating the Hausdorff dimension of the coast of Great BritainIn mathematics, the Hausdorff dimension is an extended non-negative real number associated with any metric space. The Hausdorff dimension generalizes the notion of the dimension of a real vector space...
. Only in very specialized applications is it important to distinguish between the three. See below for more details. Also, another measure of fractal dimension is the correlation dimension
Correlation dimension
In chaos theory, the correlation dimension is a measure of the dimensionality of the space occupied by a set of random points, often referred to as a type of fractal dimension....
.
Alternative definitions
It is possible to define the box dimensions using balls, with either the covering number or the packing numberSphere packing
In geometry, a sphere packing is an arrangement of non-overlapping spheres within a containing space. The spheres considered are usually all of identical size, and the space is usually three-dimensional Euclidean space...
. The covering number
is the minimal number of open balls of radius ε required to coverCover (topology)
In mathematics, a cover of a set X is a collection of sets whose union contains X as a subset. Formally, ifC = \lbrace U_\alpha: \alpha \in A\rbrace...
the fractal, or in other words, such that their union contains the fractal. We can also
consider the intrinsic covering number
, which is defined the same way but with the additional requirement that the centers of the open balls lie inside the set S. The packing number is the maximal number of disjoint balls of radius ε one can situate such that their centers would be inside the fractal. While N, Ncovering, Ncovering and Npacking are not exactly identical, they are closely related, and give rise to identical definitions of the upper and lower box dimensions. This is easy to prove once the following inequalities are proven:These, in turn follow with a little effort from the triangle inequality
Triangle inequality
In mathematics, the triangle inequality states that for any triangle, the sum of the lengths of any two sides must be greater than or equal to the length of the remaining side ....
.
The advantage of using balls rather than squares is that this definition generalizes to any metric space
Metric space
In mathematics, a metric space is a set where a notion of distance between elements of the set is defined.The metric space which most closely corresponds to our intuitive understanding of space is the 3-dimensional Euclidean space...
. In other words, the box definition is "external" — one needs to assume the fractal is contained in a Euclidean space
Euclidean space
In mathematics, Euclidean space is the Euclidean plane and three-dimensional space of Euclidean geometry, as well as the generalizations of these notions to higher dimensions...
, and define boxes according to the external structure "imposed" by the containing space. The ball definition is "internal". One can imagine the fractal disconnected from its environment, define balls using the distance between points on the fractal and calculate the dimension (to be more precise, the Ncovering definition is also external, but the other two are internal).
The advantage of using boxes is that in many cases N(ε) may be easily calculated explicitly, and that for boxes the covering and packing numbers (defined in an equivalent way) are equal.
The logarithm
Logarithm
The logarithm of a number is the exponent by which another fixed value, the base, has to be raised to produce that number. For example, the logarithm of 1000 to base 10 is 3, because 1000 is 10 to the power 3: More generally, if x = by, then y is the logarithm of x to base b, and is written...
of the packing and covering numbers are sometimes referred to as entropy numbers, and are somewhat analogous (though not identical) to the concepts of thermodynamic entropy
Entropy
Entropy is a thermodynamic property that can be used to determine the energy available for useful work in a thermodynamic process, such as in energy conversion devices, engines, or machines. Such devices can only be driven by convertible energy, and have a theoretical maximum efficiency when...
and information-theoretic entropy, in that they measure the amount of "disorder" in the metric space or fractal at scale
, and also measure how many "bits" one would need to describe an element of the metric space orfractal to accuracy
.Another equivalent definition for the box counting dimension, which is again "external", is given by the formula
where for each r > 0, the set
is defined to be the r-neighborhood of S, i.e. the set of all points in which are at distance less than r from S (or equivalently, is the union of all the open balls of radius r which are centered at a point in S).Properties
Both box dimensions are finitely additive, i.e. if { A1, .... An } is a finite collection of sets thenHowever, they are not countably
Countable set
In mathematics, a countable set is a set with the same cardinality as some subset of the set of natural numbers. A set that is not countable is called uncountable. The term was originated by Georg Cantor...
additive, i.e. this equality does not hold for an infinite sequence of sets. For example, the box dimension of a single point is 0, but the box dimension of the collection of rational number
Rational number
In mathematics, a rational number is any number that can be expressed as the quotient or fraction a/b of two integers, with the denominator b not equal to zero. Since b may be equal to 1, every integer is a rational number...
s in the interval [0, 1] has dimension 1. The Hausdorff dimension
Hausdorff dimension
thumb|450px|Estimating the Hausdorff dimension of the coast of Great BritainIn mathematics, the Hausdorff dimension is an extended non-negative real number associated with any metric space. The Hausdorff dimension generalizes the notion of the dimension of a real vector space...
by comparison, is countably additive.
An interesting property of the upper box dimension not shared with either the lower box dimension or the Hausdorff dimension is the connection to set addition. If A and B are two sets in a Euclidean space then A + B is formed by taking all the couples of points a,b where a is from A and b is from B and adding a+b. One has
Relations to the Hausdorff dimension
The box-counting dimension is one of a number of definitions for dimension that can be applied to fractals. For many well behaved fractals all these dimensions are equal. For example, the Hausdorff dimensionHausdorff dimension
thumb|450px|Estimating the Hausdorff dimension of the coast of Great BritainIn mathematics, the Hausdorff dimension is an extended non-negative real number associated with any metric space. The Hausdorff dimension generalizes the notion of the dimension of a real vector space...
, lower box dimension, and upper box dimension of the Cantor set
Cantor set
In mathematics, the Cantor set is a set of points lying on a single line segment that has a number of remarkable and deep properties. It was discovered in 1875 by Henry John Stephen Smith and introduced by German mathematician Georg Cantor in 1883....
are all equal to log(2)/log(3). However, the definitions are not equivalent.
The box dimensions and the Hausdorff dimension are related by the inequality
In general both inequalities may be strict. The upper box dimension may be bigger than the lower box dimension if the fractal has different behaviour in different scales. For example, examine the interval
Interval (mathematics)
In mathematics, a interval is a set of real numbers with the property that any number that lies between two numbers in the set is also included in the set. For example, the set of all numbers satisfying is an interval which contains and , as well as all numbers between them...
[0, 1], and examine the set of numbers satisfying the condition
- for any n, all the digits between the 22n-th digit and the (22n+1 − 1)th digit are zero
The digits in the "odd places", i.e. between 22n+1 and 22n+2 − 1 are not restricted and may take any value. This fractal has upper box dimension 2/3 and lower box dimension 1/3, a fact which may be easily verified by calculating N(ε) for
and noting that their values behaves differently for n even and odd. To see that the Hausdorff dimension may be smaller than the lower box dimension, return to the example of the rational numbers in [0, 1] discussed above. The Hausdorff dimension of this set is 0.Another example: The set of rational numbers
, a countable set with , has because its closure, , has dimension 1.Box counting dimension also lacks certain stability properties one would expect of a dimension. For instance, one might expect that adding a countable set would have no effect on the dimension of a set. This property fails for box dimension. In fact