450px, Estimating the box-counting dimension of the coast of Great Britain
In
fractal geometry, the Minkowski–Bouligand dimension, also known as Minkowski dimension or box-counting dimension, is a way of determining the
fractal dimension
In mathematics, a fractal dimension is a term invoked in the science of geometry to provide a rational statistical index of complexity detail in a pattern. A fractal pattern changes with the Scaling (geometry), scale at which it is measured.
It ...
of a bounded
set
Set, The Set, SET or SETS may refer to:
Science, technology, and mathematics Mathematics
*Set (mathematics), a collection of elements
*Category of sets, the category whose objects and morphisms are sets and total functions, respectively
Electro ...
in a
Euclidean space
Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, in Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics there are ''Euclidean spaces ...
, or more generally in a
metric space
In mathematics, a metric space is a Set (mathematics), set together with a notion of ''distance'' between its Element (mathematics), elements, usually called point (geometry), points. The distance is measured by a function (mathematics), functi ...
. It is named after the
Polish mathematician
A mathematician is someone who uses an extensive knowledge of mathematics in their work, typically to solve mathematical problems. Mathematicians are concerned with numbers, data, quantity, mathematical structure, structure, space, Mathematica ...
Hermann Minkowski
Hermann Minkowski (22 June 1864 – 12 January 1909) was a mathematician and professor at the University of Königsberg, the University of Zürich, and the University of Göttingen, described variously as German, Polish, Lithuanian-German, o ...
and the
French mathematician
Georges Bouligand.
To calculate this dimension for a fractal
, 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 by applying a
box-counting algorithm.
Suppose that
is the number of boxes of side length
required to cover the set. Then the box-counting dimension is defined as
Roughly speaking, this means that the dimension is the exponent
such that
, which is what one would expect in the trivial case where
is a smooth space (a
manifold
In mathematics, a manifold is a topological space that locally resembles Euclidean space near each point. More precisely, an n-dimensional manifold, or ''n-manifold'' for short, is a topological space with the property that each point has a N ...
) of integer dimension
.
If the above
limit does not exist, one may still take the
limit superior and limit inferior, which respectively define the upper box dimension and lower box dimension. The upper box dimension is sometimes called the entropy dimension, Kolmogorov dimension, Kolmogorov capacity, limit 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
In mathematics, Hausdorff dimension is a measure of ''roughness'', or more specifically, fractal dimension, that was introduced in 1918 by mathematician Felix Hausdorff. For instance, the Hausdorff dimension of a single point is zero, of a line ...
. Only in very special applications is it important to distinguish between the three (see
below). Yet another measure of fractal dimension is the
correlation dimension In chaos theory, the correlation dimension (denoted by ''ν'') 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.
For example, if we have a set of random points on t ...
.
Alternative definitions
upright=1.5, Examples of ball packing, ball covering, and box covering
It is possible to define the box dimensions using balls, with either the
covering number or the packing number. The covering number
is the ''minimal'' number of
open ball
In mathematics, a ball is the solid figure bounded by a ''sphere''; it is also called a solid sphere. It may be a closed ball (including the boundary points that constitute the sphere) or an open ball (excluding them).
These concepts are defin ...
s 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 in the set ''S''. The packing number
is the ''maximal'' number of
disjoint open balls of radius
one can situate such that their centers would be in the fractal. While
,
,
and
are not exactly identical, they are closely related to each other and give rise to identical definitions of the upper and lower box dimensions. This is easy to show once the following inequalities are proven:
These, in turn, follow either by definition or with little effort from the
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.
This statement permits the inclusion of Degeneracy (mathematics)#T ...
.
The advantage of using balls rather than squares is that this definition generalizes to any
metric space
In mathematics, a metric space is a Set (mathematics), set together with a notion of ''distance'' between its Element (mathematics), elements, usually called point (geometry), points. The distance is measured by a function (mathematics), functi ...
. In other words, the box definition is
extrinsic – one assumes the fractal space ''S'' is contained in a
Euclidean space
Euclidean space is the fundamental space of geometry, intended to represent physical space. Originally, in Euclid's ''Elements'', it was the three-dimensional space of Euclidean geometry, but in modern mathematics there are ''Euclidean spaces ...
, and defines boxes according to the external geometry of the containing space. However, the dimension of ''S'' should be
intrinsic, independent of the environment into which ''S'' is placed, and the ball definition can be formulated intrinsically. One defines an internal ball as all points of ''S'' within a certain distance of a chosen center, and one counts such balls to get the dimension. (More precisely, the ''N''
covering definition is extrinsic, but the other two are intrinsic.)
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
In mathematics, the logarithm of a number is the exponent by which another fixed value, the base, must be raised to produce that number. For example, the logarithm of to base is , because is to the rd power: . More generally, if , the ...
of the packing and covering numbers are sometimes referred to as ''entropy numbers'' and are somewhat analogous 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 or digits one would need to specify a point of the space to accuracy ''ε''.
Another equivalent (extrinsic) definition for the box-counting dimension 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
that are at distance less than ''r'' from ''S'' (or equivalently,
is the union of all the open balls of radius ''r'' which have a center that is a member of ''S'').
Properties
The upper box dimension is finitely stable, i.e. if is a finite collection of sets, then
However, it is not
countably stable, 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
In mathematics, a rational number is a number that can be expressed as the quotient or fraction of two integers, a numerator and a non-zero denominator . For example, is a rational number, as is every integer (for example,
The set of all ...
s in the interval
, 1has dimension 1. The
Hausdorff dimension
In mathematics, Hausdorff dimension is a measure of ''roughness'', or more specifically, fractal dimension, that was introduced in 1918 by mathematician Felix Hausdorff. For instance, the Hausdorff dimension of a single point is zero, of a line ...
by comparison, is countably stable. The lower box dimension, on the other hand, is not even finitely stable.
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 pairs 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; in particular, these dimensions coincide whenever the fractal satisfies the
open set condition (OSC).
For example, the
Hausdorff dimension
In mathematics, Hausdorff dimension is a measure of ''roughness'', or more specifically, fractal dimension, that was introduced in 1918 by mathematician Felix Hausdorff. For instance, the Hausdorff dimension of a single point is zero, of a line ...
, 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 set of numbers in the interval
, 1satisfying the condition
The digits in the "odd place-intervals", i.e. between digits 2
2''n''+1 and 2
2''n''+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 behave differently for ''n'' even and odd.
Another example: the set of rational numbers
, a countable set with
, has
because its closure,
, has dimension 1. In fact,
These examples show that adding a countable set can change box dimension, demonstrating a kind of instability of this dimension.
See also
*
Correlation dimension In chaos theory, the correlation dimension (denoted by ''ν'') 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.
For example, if we have a set of random points on t ...
*
Packing dimension
*
Uncertainty exponent
*
Weyl–Berry conjecture
*
Lacunarity
References
*
*
External links
FrakOut!: an OSS application for calculating the fractal dimension of a shape using the box counting method(Does not automatically place the boxes for you).
* FracLac: online user guide and softwar
{{DEFAULTSORT:Minkowski-Bouligand dimension
Fractals
Dimension theory
Hermann Minkowski