© Springer Nature Switzerland AG 2020
E. RosenbergFractal Dimensions of Networkshttps://doi.org/10.1007/978-3-030-43169-3_5

5. Hausdorff, Similarity, and Packing Dimensions

Eric Rosenberg1 
(1)
AT&T Labs, Middletown, NJ, USA
 

There is a fifth dimension, beyond that which is known to man. It is a dimension as vast as space and as timeless as infinity. It is the middle ground between light and shadow, between science and superstition.

Rod Sterling (1924–1975), American screenwriter, playwright, television producer, and narrator, best known for his television series “The Twilight Zone”, which ran from 1959 to 1964

In this chapter we consider three fractal dimensions of a geometric object $${\varOmega } \subset {\mathbb {R}}^E$$ :

the Hausdorff dimension, a generalization of the box counting dimension, which has enormous theoretical importance, even though it has been rarely used for computational purposes,

the similarity dimension, which provides a very useful way to calculate the box counting dimension without actually performing box counting, and

the packing dimension, which provides a “dual” way of looking at dimension.

This chapter lays the foundation for our study of the similarity dimension of a network (Chap. 13) and our study of the Hausdorff dimension of a network (Chap. 18).

5.1 Hausdorff Dimension

In this section we study the Hausdorff dimension of a bounded set $$\varOmega \subset {\mathbb {R}}^E$$ . Recall first that Definition 4.6 of d B (Sect. 4.​2) allows us to assume that each box in the covering of Ω has the same size s, where s → 0. Therefore, d B, which assigns the same “weight” to each non-empty box in the covering of Ω, “may be thought of as indicating the efficiency with which a set may be covered by small sets of equal size” [Falconer 03]. In contrast, the Hausdorff dimension assumes a covering of Ω by sets of size at most s, where s → 0, and assigns a weight to each set that depends on the size of the set. The Hausdorff dimension was introduced in 1919 by Felix Hausdorff [Hausdorff 19], and historically preceded the box counting dimension.1 Our presentation is based on [Farmer 83, Schleicher 07, Theiler 90]. Let $$\big ({\mathcal {X}}, {\mathit {dist}}( \cdot , \cdot ) \big )$$ be a metric space and let Ω be a bounded subset of $${\mathcal {X}}$$ .

Definition 5.1 For s > 0, an s-covering of Ω is a finite collection of J sets {X 1, X 2, ⋯ , X J} that cover Ω (i.e., $$\varOmega \subseteq \cup _{j=1}^J X_j$$ ) such that for each j we have diam(X j) ≤ s. □

In Definition 5.1, we follow [Falconer 03] and require diam(X j) ≤ s; we could alternatively have followed [Schleicher 07] and required diam(X j) < s, so strict inequality holds. A definition using strict inequality will be useful in our presentation in Chap. 7 of the network box counting dimension. Let $${\mathcal {C}}(s)$$ be the set of all s-coverings of Ω. For s > 0 and for d ≥ 0, define
../images/487758_1_En_5_Chapter/487758_1_En_5_Equ1_HTML.png
(5.1)
where the infimum is over all s-coverings $${\mathcal {C}}(s)$$ of Ω. We take the infimum since the goal is to cover Ω with small sets X j as efficiently as possible.
We can think of v(Ω, s, d) as the d-dimensional volume of Ω. For all values of d other than one critical value, the limit lims→0v(Ω, s, d) is either 0 or ∞. For example, suppose we cover the unit square [0, 1] × [0, 1] by small squares of side length s. We need 1∕s 2 small squares, the diameter of each square is $$\sqrt {2} s$$ , and $$v(\varOmega , s, d) = (1/s^2)(\sqrt {2} s)^d = \sqrt {2}^{\, d} s^{d-2}$$ . We have
$$\displaystyle \begin{aligned} \lim_{s \rightarrow 0} s^{d-2} = \left\{ \begin{array}{ll} \infty &amp; \mbox{if } d&lt;2 \\ 1 &amp; \mbox{if } d=2 \\ 0 &amp; \mbox{if } d&gt;2. \end{array} \right. \end{aligned}$$
Thus, for example, if d = 3, then the unit square [0, 1] × [0, 1] has zero volume; if d = 1, then the unit square has infinite length.
For a given d, as s decreases, the set of available s-coverings of Ω shrinks, so v(Ω, s, d) increases as s decreases. Thus
$$\displaystyle \begin{aligned} \begin{array}{rcl} v^{\star}(\varOmega,d) \equiv \lim_{s \rightarrow 0} v(\varOmega, s, d) {} \end{array} \end{aligned} $$
(5.2)
always exists in [0, ∞) ∪{∞}; that is, v ⋆(Ω, d) might be ∞. The value v ⋆(Ω, d) is called the d-dimensional Hausdorff measure of Ω. For the case where $${\mathcal {X}} = {\mathbb {R}}^E$$ and the distance metric dist(⋅, ⋅) is the Euclidean distance and d is a positive integer, v ⋆(Ω, d) is within a constant scaling factor of the Lebesgue measure of Ω. 2 If Ω is countable, then v ⋆(Ω, d) = 0.
Since for each fixed s < 1 the function v(Ω, s, d) is non-increasing with d, then v ⋆(Ω, d) is also non-increasing with d [Falconer 03]. For d ≥ 0 and d ′≥ 0, definition (5.2) implies [Schleicher 07]
$$\displaystyle \begin{aligned} \begin{array}{rcl} \mbox{If } v^{\star}(\varOmega,d) &lt; \infty \mbox{ and } d^{\prime} &gt; d, \mbox{then } v^{\star}(\varOmega,d^{\prime}) = 0 . \\ \mbox{If } v^{\star}(\varOmega,d) &gt; 0 \mbox{ and } d^{\prime} &lt; d, \mbox{then } v^{\star}(\varOmega,d^{\prime}) = \infty . \end{array} \end{aligned} $$
These two assertions imply the existence of a unique value of d, called the Hausdorff dimension of Ω and denoted by d H(Ω), such that v ⋆(Ω, d) = ∞ for d < d H(Ω) and v ⋆(Ω, d) = 0 for d > d H(Ω). If there is no ambiguity about the set Ω, for brevity we write d H rather than d H(Ω). The following alternative succinct definition of d H was provided in [Falconer 03].
Definition 5.2
$$\displaystyle \begin{aligned} \begin{array}{rcl} d_{{H}} \equiv \inf \{ d \geq 0 \, \vert \, v^{\star}(\varOmega,d) = 0 \} . {} \end{array} \end{aligned} $$
(5.3)
□
In [Mandelbrot 83b] (p. 15), the term “fractal dimension” is used to refer to the Hausdorff dimension; we will use the term “fractal dimension” only in a generic manner, to refer to any fractal dimension. The Hausdorff dimension d H might be zero, positive, or ∞. A set $$\varOmega \subset {\mathbb {R}}^E$$ with d H < 1 is totally disconnected [Falconer 03]. (A set Ω is totally disconnected if for x ∈ Ω, the largest connected component of Ω containing x is x itself.) If $$\varOmega \subset {\mathbb {R}}^E$$ is an open set, then d H = E. If Ω is countable, then d H = 0. A function $$f: \varOmega \rightarrow {\mathbb {R}}^E$$ is bi-Lipschitz if for some positive numbers α and β and for each x, y ∈ Ω, we have
$$\displaystyle \begin{aligned} \begin{array}{rcl} \alpha \, \vert\vert x - y \vert\vert \leq \vert f(x)-f(y) \vert \leq \beta \, \vert\vert x-y \vert\vert . \end{array} \end{aligned} $$
If f : Ω → Ω is bi-Lipschitz, then $$d_{{H}} \bigl (f({\varOmega }) \bigr ) = d_{{H}}({\varOmega } )$$ ; that is, the Hausdorff dimension of Ω is unchanged by a bi-Lipschitz transformation. In particular, the Hausdorff dimension of a set is unchanged by rotation or translation.
If $$\widetilde {\varOmega }$$ is a measurable subset of Ω, then we can similarly form $$v^{\star }({\widetilde {\varOmega }},d)$$ , and in particular, choosing d = d H(Ω) we can form $$v^{\star } \big ({\widetilde {\varOmega }},d_{{H}}(\varOmega ) \big )$$ . The function
$$\displaystyle \begin{aligned} v^{\star} \big( \cdot \;,d_{{H}}(\varOmega) \big) , {} \end{aligned}$$
which assigns a value to measurable subsets of Ω, is a measure concentrated on Ω; this measure is called the Hausdorff measure [Grassberger 85].

For ordinary geometric objects, the Hausdorff and box counting dimensions are equal: d H = d B. However, in general we only have d H ≤ d B, and there are many examples where this inequality is strict [Falconer 03]. To prove this inequality, we will use Definition 4.6 of d B with B(s) defined as the minimal number of boxes of size s needed to cover Ω. Recall that the lower box counting dimension $$ \underline {{d_{{B}}}}$$ is defined by (4.​2) and if d B exists then $$ \underline {{d_{{B}}}} = d_{{B}}$$ .

Theorem 5.1 $$d_{{H}} \leq \underline {{d_{{B}}}}$$ .

Proof [ Falconer 03] Suppose Ω can be covered by B(s) boxes of diameter s. By (5.1), for d ≥ 0 we have v(Ω, s, d) ≤ B(s)s d. Since v ⋆(Ω, d) = ∞ for d < d H, then for d < d H we have v ⋆(Ω, d) =lims→0v(Ω, s, d) > 1. Hence for d < d H and s sufficiently small, B(s)s d ≥ v(Ω, s, d) > 1, which implies $$\log B(s) + d \log s &gt; 0$$ . Rewriting this as $$d &lt; \log B(s)/\log (1/s)$$ , it follows that $$d \leq \liminf _{s \rightarrow 0} \log B(s)/\log (1/s) = \underline {{d_{{B}}}}$$ . Since this holds for d < d H, then $$d_{{H}} \leq \underline {{d_{{B}}}}$$ . □

Example 5.1 Let Ω be the unit square in $${\mathbb {R}}^2$$ . Cover Ω with J 2 squares, each with side length s = 1∕J. Using the L 1 metric (i.e., ||x|| =maxi=1,2 |x i|), the diameter of each box is 1∕J. We have $$v^{\star }(\varOmega ,d) \leq \sum _{j=1}^{J^2} (1/J)^d = J^2 (1/J)^d = J^{2-d}$$ , and limJ→∞J 2−d = ∞ for d < 2 and limJ→∞J 2−d = 0 for d > 2. Since v ⋆(Ω, d) = 0 for d > 2, then by Definition 5.2 we have d H ≤ 2. □

Example 5.2 [ Schleicher 07] If Ω is an E-dimensional hypercube, then the number B(s) of boxes of size s needed to cover Ω satisfies B(s) ≤ c(1∕s)E for some constant c, so
$$\displaystyle \begin{aligned} v({\varOmega}, s, d) \leq B(s) s^d \leq c (1/s)^E s^d = c s^{d-E} . \end{aligned}$$
We have lims→0cs d−E = 0 if d > E, so v ⋆(Ω, d) = 0 if d > E. Thus d H ≤ E. □
Self-similar sets provide an upper bound on d H [Schleicher 07]. For suppose Ω is the union of K pairwise disjoint subsets, each of which is obtained from Ω by scaling with the factor α < 1, followed by translation and/or rotation. In turn, suppose each instance of αΩ is decomposed into K objects, where each sub-object is a translation and possible rotation of the set α 2Ω, and this construction continues infinitely many times. Let Δ = diam(Ω). Then Ω can be covered by one box of size Δ, so v ⋆(Ω, d) ≤ Δ d. Or Ω can be covered by K boxes of size αΔ, so v ⋆(Ω, d) ≤ K(αΔ)d. Or Ω can be covered by K 2 boxes of size α 2Δ, so v ⋆(Ω, d) ≤ K 2(α 2Δ)d. In general, Ω can be covered by K t boxes of size α tΔ, so v ⋆(Ω, d) ≤ K t(α tΔ)d. For any d we have
$$\displaystyle \begin{aligned} v^{\star}(\varOmega,d) \leq \lim_{t \rightarrow \infty} K^t (\alpha^t \varDelta)^d = \lim_{t \rightarrow \infty} (K \alpha^d)^t \varDelta^d \end{aligned}$$
and limt→∞(Kα d)tΔ d = 0 if Kα d < 1. We rewrite this last inequality as $$d &gt; \log K / \log (1/\alpha )$$ . Thus $${d_{{H}}} \leq \log K / \log (1/\alpha )$$ . However, this argument provides no information about a lower bound for d H. For example, if the self-similar set Ω is countable, then its Hausdorff dimension is 0. The above examples illustrate that it is easier to obtain an upper bound on d H than a lower bound. Obtaining a lower bound on d H requires estimating all possible coverings of Ω. Interestingly, there is a way to compute a lower bound on the box counting dimension of a network (Sect. 8.​8).
In [Manin 06] it was observed that “the general existence of d H is a remarkable mathematical phenomenon, akin to those that appear in the description of phase transitions and critical exponents in physics.” (We will encounter phase transitions and critical exponents in Chap. 21.) Manin also provided a slightly different definition of the Hausdorff dimension of a set $$\varOmega \subset {\mathbb {R}}^E$$ . Given that the volume V E(r) of a ball with radius r in E-dimensional Euclidean space is3
$$\displaystyle \begin{aligned} V_E(r) = \frac{ \big( \varGamma(1/2) \big)^E }{ \varGamma \big(1 + (E/2) \big) } \, r^E, \end{aligned}$$
where Γ is the Gamma function (Sect. 23.​2), we declare that, for any real number d, the volume V d(r) of the d-dimensional ball with radius r is
$$\displaystyle \begin{aligned} V_d(r) = \frac{ \big( \varGamma(1/2) \big)^d }{ \varGamma \big(1 + (d/2) \big) } \, r^d . \end{aligned}$$
We cover Ω by a finite collection {X 1, X 2, ⋯ , X J} of J balls, where the radius of ball X j is r j. Define
$$\displaystyle \begin{aligned} V(d) = \lim_{r \rightarrow 0} \, \inf_{{r_{{j}}} &lt; r} \, \sum_{j=1}^J V_d({r_{{j}}}) . \end{aligned}$$
Then d H is the unique value of d for which V (d) = 0 for d > d H and V (d) = ∞ for d < d H. This definition of d H is equivalent to Definition 5.2.

In [Bez 11] it was observed that d H is a local, not global, property of Ω, since it is defined in terms of a limit as s → 0. That is, even though d H is defined in terms of a cover of Ω by sets of diameter at most s, since s → 0 then d H is still a local property of Ω. The term “roughness” was used in [Bez 11] to denote that characteristic of Ω which is quantified by d H. Also, [Bez 11] cautioned that the fact that, while fractal sets are popular mainly for their self-similar properties, computing a fractal dimension of Ω does not imply that Ω is self-similar. In applications of fractal analysis to ecology, there are many systems which exhibit roughness but not self-similarity, but the systems of strong interest exhibit either self-similarity or they exhibit self-similarity and roughness. However, assessing self-similarity is a challenging if not impossible task without an a priori reason to believe that the data comes from a model exhibiting self-similarity (e.g. fractionary Brownian processes). The notion that the ability to compute a fractal dimension does not automatically imply self-similarity holds not only for a geometric object, but also for a network (Chaps. 18 and 21).

The Hausdorff dimension is the basis for some differing definitions of a fractal. For example, [Manin 06] mentioned a definition of Mandelbrot that a set is a fractal if its Hausdorff dimension is not an integer. Another definition proposed by Mandelbrot is that a set is a fractal if its Hausdorff dimension exceeds its topological dimension; this is the definition preferred in [Schleicher 07]. Interestingly, Mandelbrot observed that this definition, while rigorous, is tentative. He wrote [Mandelbrot 85] “the Hausdorff-Besicovitch dimension is a very nonintuitive notion; it can be of no use in empirical work, and is unduly complicated in theoretical work, except in the case of self-similar fractals.” In his landmark paper [Mandelbrot 67] on the length of the coast of Britain, Mandelbrot warned that

The concept of “dimension” is elusive and very complex, and is far from exhausted by [these simple considerations]. Different definitions frequently yield different results, and the field abounds in paradoxes. However, the Hausdorff-Besicovitch dimension and the capacity dimension, when computed for random self-similar figures, have so far yielded the same value as the similarity dimension.4

In [Jelinek 06] it was observed that although the Hausdorff dimension is not usable in practice, it is important to be aware of the shortcomings of methods, such as box counting, for estimating the Hausdorff dimension. In studying quantum gravity, [Ambjorn 92] wrote that the Hausdorff dimension is a very rough measure of geometrical properties, which may not provide much information about the geometry.5 The distinction between d H and d B is somewhat academic, since very few experimenters are concerned with the Hausdorff dimension. Similarly, [Badii 85] observed that, even though there are examples where d H ≠ d B, “it is still not clear whether there is any relevant difference in physical systems.”6 In practice the Hausdorff dimension of a geometric object has been rarely used, while the box counting dimension has been widely used, since it is rather easy to compute.
So far, we have studied two fractal dimensions: the box counting dimension and the Hausdorff dimension. Although we have yet to introduce other important fractal dimensions (e.g., the similarity, correlation, and information dimensions), it is useful to now examine the list in [Falconer 03] of properties that should be satisfied by any definition of dimension. Consider the function dim(⋅) which assigns a nonnegative number to each $$\varOmega \subseteq {\mathbb {R}}^E$$ . To be called a dimension function, dim(⋅) should satisfy the following for any subsets $${\mathcal {X}}$$ and $${\mathcal {Y}}$$ of Ω:

monotonicity: If $${\mathcal {X}} \subset {\mathcal {Y}}$$ then $$\mathit {dim}({\mathcal {X}}) \leq \mathit {dim}({\mathcal {Y}})$$ .

stability: If $${\mathcal {X}}$$ and $${\mathcal {Y}}$$ are subsets then $$\mathit {dim}({\mathcal {X}} \cup {\mathcal {Y}}) = \max \bigl ( \mathit {dim}({\mathcal {X}}),\mathit {dim}({\mathcal {Y}} ) \bigr )$$ .

countable stability: If $$\{ {\mathcal {X}}_i \}_{i=1}^\infty $$ is an infinite collection of subsets then $$\mathit {dim}( \bigcup _{i=1}^\infty {\mathcal {X}}_i) = \sup _i \mathit {dim}({\mathcal {X}}_i)$$ .

countable sets: If $${\mathcal {X}}$$ is finite or countably infinite then $$\mathit {dim}({\mathcal {X}})\,{=}\,0$$ .

open sets: If $${\mathcal {X}}$$ is an open subset of $${\mathbb {R}}^E$$ then $$\mathit {dim}({\mathcal {X}}) = E$$ .

smooth manifolds: If $${\mathcal {X}}$$ is a smooth (i.e., continuously differentiable) E-dimensional manifold (curve, surface, etc.) then $$\mathit {dim}({\mathcal {X}}) = E$$ .

Falconer observed that all definitions of dimension are monotonic, most are stable, but some common definitions do not exhibit countable stability and may have countable sets of positive dimension. The open sets and smooth manifolds conditions ensure that the classical definition of dimension is preserved. The monotonicity condition was used in [Rosenberg 16b] to study the correlation dimension of a rectilinear grid network (Sect. 11.​4). All the above properties are satisfied by the Hausdorff dimension d H. As to whether these properties are satisfied by the box counting dimension, we have [Falconer 03] (i) the lower and upper box counting dimensions are monotonic; (ii) the upper box counting dimension is finitely stable, i.e., $$\overline {{d_{{B}}}}(\varOmega _1 \cup \varOmega _2) = \max \{ \overline {{d_{{B}}}}(\varOmega _1), \overline {{d_{{B}}}}(\varOmega _2) \}$$ ; (iii) the box counting dimension of a smooth E-dimensional manifold in $${\mathbb {R}}^E$$ is E; also, the lower and upper box counting dimensions are bi-Lipschitz invariant.

5.2 Similarity Dimension

The next definition of dimension we study is the similarity dimension [Mandelbrot 83b], applicable to an object which looks the same when examined at any scale. We have already encountered, in the beginning of Chap. 3, the idea of self-similarity when we considered the Cantor set. For self-similar fractals, the similarity dimension is a way to compute a fractal dimension without computing the slope of the $$\log B(s)$$ versus $$\log s$$ curve.

In [Mandelbrot 67], Mandelbrot studied geometric figures that can be decomposed into K parts such that each part is similar to the whole by the ratio α. For example, consider Fig. 5.1, taken from [Mandelbrot 67]. Start with the segment [0, 1] and from it create a figure with K = 8 line segments, each of which is one-fourth the length of the original segment, so α = 1∕4. In iteration t, use the same process to replace each segment of length 1∕4t with K = 8 segments, each of length 1∕4t+1. In the limit, the curve has dimension $$d = - \log K / \log \alpha = \log 8 / \log 4$$ .
../images/487758_1_En_5_Chapter/487758_1_En_5_Fig1_HTML.png
Figure 5.1

Self-similarity with K = 8 and α = 1∕4

Generalizing this notion from a line to any geometric object, suppose Ω can be decomposed into K pairwise disjoint, or “just touching”, identical sub-objects, each of which is a reduced version of Ω. By “just touching” sub-objects we mean that any two sub-objects intersect only at a set of measure zero (e.g., they intersect only at a point or at a line). By a reduced version of Ω we mean a translation and possibly rotation of the set αΩ, for some α satisfying 0 < α < 1. In turn each instance of αΩ is decomposed into K objects, where each sub-object is a translation and possible rotation of the set α 2Ω. This generic construction is illustrated in Fig. 5.2. This construction corresponds to an iterated function system (Sect. 3.​3) for which each of the K functions $${f_{{k}}}: {\mathcal {H}}({\mathcal {X}}) \rightarrow {\mathcal {H}}({\mathcal {X}})$$ uses the same contraction factor α, and the functions f k differ only in the amount of rotation or translation they apply to a point in $${\mathcal {H}}({\mathcal {X}})$$ (recall that a point in $${\mathcal {H}}({\mathcal {X}})$$ is a non-empty compact subset of a metric space $$\mathcal {X}$$ ). The IFS theory guarantees the existence of an attractor Ω of the IFS. The heuristic argument (not a formal proof) leading to the similarity dimension is as follows. Let B(s) be the minimal number of boxes of size s needed to cover Ω.
../images/487758_1_En_5_Chapter/487758_1_En_5_Fig2_HTML.png
Figure 5.2

Three generations of a self-similar fractal

Assumption 5.1 For some positive number d B, some c, and all sufficiently small positive s, we have
$$\displaystyle \begin{aligned} \begin{array}{rcl} B(s) = c s^{-{d_{{B}}}} . {} \end{array} \end{aligned} $$
(5.4)
□
Let B α(s) be the minimal number of boxes of size s needed to cover αΩ. Since Ω can be decomposed into K instances of αΩ, then for small s we have
$$\displaystyle \begin{aligned} \begin{array}{rcl} B(s) = K B_{\alpha}(s) . {} \end{array} \end{aligned} $$
(5.5)
Since αΩ is a scaled down copy of Ω, the minimal number of boxes of size s needed to cover αΩ is equal to the the minimal number of boxes of size s∕α needed to cover Ω, that is,
$$\displaystyle \begin{aligned} \begin{array}{rcl} B_{\alpha}(s) = B(s/\alpha) . {} \end{array} \end{aligned} $$
(5.6)
To illustrate (5.6), let Ω be a square with side length L. If we cover αΩ with boxes of size s, the minimal number of boxes required is $$\bigl ( (\alpha L)^2 \bigr )/{s^2} = \alpha ^2 (L/s)^2 $$ . If we cover Ω with boxes of size s∕α, the minimal number of boxes required is $${L^2}/\bigl ( (s/\alpha )^2 \bigr ) = \alpha ^2 (L/s)^2$$ .
Since (5.4) is assumed to hold as an equality, from (5.4), (5.5), and (5.6), we have
$$\displaystyle \begin{aligned} B(s) = c s^{-{d_{{B}}}} = K B_{\alpha}(s) = K B(s/\alpha) = K c \, (s/\alpha)^{-{d_{{B}}}} \end{aligned}$$
so $$c s^{-{d_{{B}}}} = Kc \, (s/\alpha )^{-{d_{{B}}}}$$ , and this equality can be written as
$$\displaystyle \begin{aligned} \begin{array}{rcl} {d_{{B}}} = \frac{\log K}{\log (1/\alpha) } . {} \end{array} \end{aligned} $$
(5.7)
The ratio (5.7) uses only K, the number of copies of Ω, and α, the scaling factor; it has no explicit dependence on s or B(s). For this reason, the ratio deserves its own name and symbol.
Definition 5.3 For a self-similar fractal Ω constructed by taking K pairwise disjoint or “just touching” instances of Ω, each scaled by the factor α < 1, the similarity dimension d S is defined by
$$\displaystyle \begin{aligned} \begin{array}{rcl} {d_{{S}}} \equiv \frac{\log K}{\log (1/\alpha) } . {} \end{array} \end{aligned} $$
(5.8)
□

Example 5.3 Consider the Sierpiński triangle of Fig. 3.​3. In each iteration we shrink the object by the factor α = 1∕2, and take K = 3 copies of the reduced figure. From (5.8) we have $${d_{{S}}} = { \log 3}/{\log 2}$$ . □

Example 5.4 Consider the Sierpiński carpet of Fig. 4.​10. In each iteration we shrink the object by the factor α = 1∕3, and take K = 8 copies of the reduced figure. Thus $${d_{{S}}} = { \log 8}/{\log 3}$$ . □

Example 5.5 Consider the Cantor set of Fig. 3.​2. In each iteration we shrink the object by the factor α = 1∕3, and take K = 2 copies of the reduced figure. Thus $${d_{{S}}} = { \log 2}/{\log 3}$$ . □

Example 5.6 We can generalize the Cantor set construction, as described in [Schleicher 07]. We start with the unit interval, and rather than remove the middle third, we remove a segment of length 1 − 2x from the middle, where x ∈ (0, 1∕2). This leaves two segments, each of length x. In subsequent iterations, we remove from each segment an interval in the middle with the same fraction of length. Let C t be the pre-fractal set obtained after t iterations of this construction. From (5.8) we have $${d_{{S}}} = { \log 2}/{\log (1/x)}$$ . Since d S → 1 as x → 1∕2 and d S → 0 as x → 0, the similarity dimension can assume any value in the open interval (0, 1). □

Example 5.7 Consider the Cantor dust of Fig. 4.​12. This figure can be described as the Cartesian product $${\mathcal {C}} \times {\mathcal {C}}$$ of the Cantor set $$\mathcal {C}$$ with itself. We construct Cantor dust by taking, in generation t, the Cartesian product $${\mathcal {C}}_t \times {\mathcal {C}}_t$$ , where $${\mathcal {C}}_t$$ is defined in Example 5.6 above. The similarity dimension of the generalized Cantor dust is $${d_{{S}}} = { \log (2^2)}/{\log (1/x)}$$ , where x ∈ (0, 1). Since d S → 2 as x → 1∕2 and d S → 0 as x → 0, the similarity dimension can assume any value in the open interval (0, 2). □

Example 5.8 Two-dimensional Cantor dust can be generalized further [Schleicher 07]. We can take the E-fold Cartesian product
$$\displaystyle \begin{aligned} \underbrace{ {\mathcal{C}}_t \times {\mathcal{C}}_t \times \ldots \times {\mathcal{C}}_t }_{E \mbox{ times}} \end{aligned}$$
of C h with itself. For this E-dimensional generalized Cantor dust we have $${d_{{S}}} = { \log (2^E)}/{\log (1/x)}$$ , where x ∈ (0, 1). Since d S → E as x → 1∕2 and d S → 0 as x → 0, the similarity dimension can assume any value in the open interval (0, E). This example demonstrates why defining a fractal to be a set with a non-integer dimension may not be a particularly good definition. It seems unreasonable to consider E-dimensional generalized Cantor dust to be a fractal only if $${ \log (2^E)}/{\log (1/x)}$$ is not an integer. □
Example 5.9 Wool fiber (from sheep) has remarkable properties, and it is difficult to synthesize a material like wool fiber that has perspiration and moisture absorption and warmth retention. The structure of wool fiber is rather complex, with several hierarchical levels. At the lowest hierarchy level (call it level 0), three α-helix protein macromolecules are compactly twisted together to form a level-1 protofibril. Then eleven level-1 protofibrils form a level-2 microfibril. Then multiple level-2 microfibrils form a level-3 macrofibril, multiple level-3 macrofibris form a level-4 cell, and finally multiple level-4 cells form a wool fiber. Using (5.8), the similarity dimension d S was calculated in [Fan 08] for the three lowest levels:
$$\displaystyle \begin{aligned} d_{{S}} = \frac {\log \mbox{(number of lowest level units within the higher level unit)}} {\log \mbox{(ratio of linear size of higher level unit to the lowest level unit)}} . \end{aligned}$$
Considering levels 0 and 1, the ratio of the protofibril diameter to the α-helix diameter is 2.155, and there are 3 α-helix macromolecules per protofibril. Thus the first similarity dimension is $$d^{0 \leftrightarrow 1} = \log 3/\log 2.155 = 1.431$$ . Considering levels 0 and 2, the ratio of the microfibril diameter to the α-helix diameter is 8.619, and there are 33 α-helix macromolecules per microfibril. Thus the next similarity dimension is $$d^{0 \leftrightarrow 2} = \log 33/\log 8.619 = 1.623$$ . Finally, considering levels 0 and 3, the ratio of the macrofibril diameter to the α-helix diameter is 17.842, and there are 99 α-helix macromolecules per microfibril. Thus that similarity dimension is $$d^{0 \leftrightarrow 3} = \log 99/\log 17.842 = 1.595$$ . The authors noted that d 0↔2 and d 0↔3 are close to the “golden mean” value $$(1 + \sqrt {5})/2 \approx 1.618$$ , and conjectured that this is another example of the significant role of the golden mean in natural phenomena. □

The above discussion of self-similar fractals assumed that each of the K instances of Ω is reduced by the same scaling factor α. We can generalize this to the case where Ω is decomposed into K non-identical parts, and the scaling factor α k is applied to the k-th part, where 0 < α k < 1 for 1 ≤ k ≤ K. Some or all of the α k values may be equal; the self-similar case is the special case where all the α k values are equal. The construction for the general case corresponds to an IFS for which each of the K functions $${f_{{k}}}: {\mathcal {H}}({\mathcal {X}}) \rightarrow {\mathcal {H}}({\mathcal {X}})$$ does not necessarily use the same contraction factor, but aside from the possibly different contraction factors, the functions f k differ only in the amount of rotation or translation they apply to a point in $${\mathcal {H}}({\mathcal {X}})$$ . That is, up to a constant scaling factor, the f k differ only in the amount of rotation or translation.

To compute the similarity dimension d S of Ω in this case, assume that any two of the K parts are disjoint, or possibly just touching (as defined above). It was proved in [Hutchinson 81] that d S is the unique value satisfying
$$\displaystyle \begin{aligned} \begin{array}{rcl} \sum_{k=1}^K {{\alpha}_{{k}}}^{{\negthinspace \negthinspace d_{{S}}}} = 1 . {} \end{array} \end{aligned} $$
(5.9)
This equation is known as the Moran equation and dates from 1946. If all the α k values are equal to the common value α, (5.9) simplifies to $$K \alpha ^{{d_{{S}}}} = 1$$ , yielding $${d_{{S}}} = -\log K / \log \alpha $$ , which is precisely (5.8).
An informal proof of (5.9), provided in [Barnsley 12, Tél 88], yields considerable insight. Suppose Ω can be decomposed into the K parts Ω k, 1 ≤ k ≤ K, where part k is obtained by scaling Ω by α k. Assume any two parts are disjoint or just touching. Let B k(s) be the minimal number of boxes of size s needed to cover Ω k. For s ≪ 1 we have
$$\displaystyle \begin{aligned} \begin{array}{rcl} B(s) = \sum_{k=1}^K B_k(s) {} . \end{array} \end{aligned} $$
(5.10)
From the similarity property (5.6) we have
$$\displaystyle \begin{aligned} \begin{array}{rcl} B_k(s) = B(s/{{\alpha}_{{k}}}) = c \, \left( \frac{s}{{{\alpha}_{{k}}}} \right)^{-{d_{{B}}}} , {} \end{array} \end{aligned} $$
(5.11)
where the second equality holds from (5.4) applied to Ω k. From (5.10) and (5.11) we have
$$\displaystyle \begin{aligned} B(s) = c \, s^{-{d_{{B}}}} = \sum_{k=1}^K B(s/{{\alpha}_{{k}}}) = \sum_{k=1}^K c \, \left( \frac{s}{{{\alpha}_{{k}}}} \right)^{-{d_{{B}}}} . \end{aligned}$$
This yields
$$\displaystyle \begin{aligned} c \, s^{-{d_{{B}}}} = \sum_{k=1}^K c \, \left( \frac{s}{{{\alpha}_{{k}}}} \right)^{-{d_{{B}}}} \end{aligned}$$
which simplifies to
$$\displaystyle \begin{aligned} \begin{array}{rcl} \sum_{k=1}^K {{\alpha}_{{k}}}^{{\negthinspace \negthinspace d_{{B}}}} = 1. {} \end{array} \end{aligned} $$
(5.12)
Since the exponent in (5.12) is derived from a similarity argument, we will refer to this exponent as the similarity dimension d S. There is a unique solution d S to the Moran equation (5.9). To see this, define
$$\displaystyle \begin{aligned} f(d) \equiv \sum_{k=1}^K {{\alpha}_{{k}}}^{\negthinspace \negthinspace d} . \end{aligned}$$
Since 0 < α k < 1, then f ′(d) < 0. Hence f is strictly decreasing for d > 0. Since f(0) = K and limd→∞f(d) = 0, there is a unique d satisfying f(d) = 1.

Example 5.10 Suppose the Cantor set construction of Fig. 3.​2 is modified so that we take the first 1∕4 and the last 1∕3 of each interval to generate the next generation intervals. Starting in generation 0 with [0, 1], the generation-1 intervals are $$[0,\frac {1}{4}]$$ and $$[\frac {2}{3}, 1]$$ . The four generation-2 intervals are (i) $$[0,(\frac {1}{4})(\frac {1}{4})]$$ , (ii) $$[\frac {1}{4}-(\frac {1}{3})(\frac {1}{4}), \frac {1}{4}]$$ , (iii) $$[\frac {2}{3}, \frac {2}{3} + (\frac {1}{4})(\frac {1}{3})]$$ , and (iv) $$[1-(\frac {1}{3})(\frac {1}{3}) ,1]$$ . From (5.12), with K = 2, α 1 = 1∕4, and α 2 = 1∕3, we obtain $$(1/4)^{{d_{{B}}}} + (1/3)^{{d_{{B}}}}=1$$ , which yields d S ≈ 0.560; this is smaller than the value $${d_{{S}}} = \log 2/\log 3 \approx 0.631$$ obtained for K = 2 and α 1 = α 2 = 1∕3. □

In general, the similarity dimension of Ω is not equal to the Hausdorff dimension of Ω. However, if the following Open Set Condition holds, then the two dimensions are equal [Glass 11].

Definition 5.4 [ Glass 11] Let $$\big ({\mathcal {X}}, {\mathit {dist}}( \cdot , \cdot ) \big )$$ be a metric space, and let Ω be a non-empty compact subset of $${\mathcal {X}}$$ . Suppose for the IFS $$\{ {f_{{k}}}\}_{k=1}^K$$ with contraction factors $$\{ {{\alpha }_{{k}}}\}_{k=1}^K$$ we have $$\varOmega = \cup _{k=1}^K {f_{{k}}}(\varOmega )$$ . Then the IFS $$\{ {f_{{k}}}\}_{k=1}^K$$ satisfies the Open Set Condition if there exists a non-empty open set $$U \subseteq {\mathbb {R}}^E$$ such that
$$\displaystyle \begin{aligned} \begin{array}{rcl} \bigcup_{k=1}^K {f_{{k}}}(U) \subseteq U \mbox{ and } {f_{{\, i}}}(U) \cap {f_{{\, j}}}(U) = \emptyset \mbox{ for } i \neq j . {} \end{array} \end{aligned} $$
(5.13)
□

In practice, the Open Set Condition can be easy to verify.

Example 5.11 The Cantor Set can be generated by an IFS using two similarities defined on $${\mathbb {R}}$$ . Let $${f_{{\, 1}}}(x) = \frac {x}{3}$$ and $${f_{{\, 2}}}(x) = \frac {x}{3} + \frac {2}{3}$$ . The associated ratio list is $$\{ \frac {1}{3}, \frac {1}{3} \}$$ . The invariant set of this IFS is the Cantor set. The similarity dimension of the Cantor set satisfies $$\left ( \frac {1}{3}\right )^{{d_{{S}}}} + \left (\frac {1}{3}\right )^{{d_{{S}}}} = 1$$ , so $${d_{{S}}} = \log 2/\log 3$$ . To verify the Open Set Condition, choose U = (0, 1). Then $${f_{{\, 1}}}(U) = (0, \frac {1}{3})$$ and $${f_{{\, 2}}}(U) = (\frac {2}{3}, 1)$$ , so f 1(U) ∩ f 2(U) = ∅ and f 1(U) ∪ f 2(U) ⊂ U. Thus the Open Set Condition holds. □

Example 5.12 Figure 5.3, from [Zhao 16], illustrates the Sierpiński triangle, which is obtained by scaling each triangle by α = 1∕2 and taking K = 3 copies. By (5.8) its similarity dimension is $$\log 3/\log 2$$ . Treating $$x \in \mathbb {R}^2$$ as a column vector (i.e., a 2 × 1 matrix), the IFS generating this fractal uses the three similarities
$$\displaystyle \begin{aligned} {f_{{\, 1}}}(x) = Mx, \;\;\;\; {f_{{\, 2}}}(x) = Mx+\left( \begin{array}{c} \frac{1}{2} \\ 0 \end{array} \right), \;\;\;\; {f_{{\, 3}}}(x) = Mx+\left( \begin{array}{c} \frac{1}{4} \\[0.5em] \frac{\sqrt{3}}{4} \end{array} \right) , \end{aligned}$$
where
$$\displaystyle \begin{aligned} M = \left( \begin{array}{cc} \frac{1}{2} &amp; 0 \\ 0 &amp; \frac{1}{2} \end{array} \right) . \end{aligned}$$
To show that this IFS satisfies the Open Set Condition, let U be the open equilateral triangle with corner points (0, 0), $$\bigl (\frac {1}{2}, \frac {\sqrt {3}}{2} \bigr )$$ , and (1, 0). As illustrated in Fig. 5.4, f 1(U) is the open triangle with corner points (0, 0), $$\bigl (\frac {1}{4}, \frac {\sqrt {3}}{4} \bigr )$$ , and $$\left (\frac {1}{2}, 0\right )$$ ; f 2(U) is the open triangle with corner points $$\bigl (\frac {1}{2},0 \bigr )$$ , $$\bigl (\frac {3}{4}, \frac {\sqrt {3}}{4} \bigr )$$ , and (1, 0); and f 3(U) is the open triangle with corner points $$\bigl ( \frac {1}{4}, \frac {\sqrt {3}}{4} \bigr )$$ , $$\bigl (\frac {1}{2}, \frac {\sqrt {3}}{2} \bigr )$$ , and $$\bigl (\frac {3}{4}, \frac {\sqrt {3}}{4} \bigr )$$ . Thus f i(U) ∩ f j(U) = ∅ for i ≠ j and f 1(U) ∪ f 2(U) ∪ f 3(U) ⊂ U, so the condition holds. □
../images/487758_1_En_5_Chapter/487758_1_En_5_Fig3_HTML.png
Figure 5.3

Sierpiński triangle

../images/487758_1_En_5_Chapter/487758_1_En_5_Fig4_HTML.png
Figure 5.4

The Open Set Condition for the Sierpiński gasket

Example 5.13 An example of an IFS and a set U for which (5.13) does not hold was given by McClure.7 Pick $$r \in (\frac {1}{2}, 1)$$ . Define f 1(x) = rx and f 2(x) = rx + (1 − r). Choosing U = (0, 1), we have f 1(U) = (0, r) and f 2(U) = (1 − r, 1). Since $$r \in (\frac {1}{2}, 1)$$ , the union of (0, r) and (1 − r, 1) is (0, 1) and the intersection of (0, r) and (1 − r, 1) is the non-empty set (1 − r, r), so (5.13) does not hold for this U. Note that blindly calculating the similarity dimension with K = 2, we obtain $$d_{{S}} = \log 2 / \log (1/r) &gt; 1$$ , and the box counting dimension of [0, 1] is 1. □

Exercise 5.1 Construct an IFS and a set U in $${\mathbb {R}}^E$$ for which (5.13) does not hold. □

5.3 Fractal Trees and Tilings from an IFS

Mandelbrot [Mandelbrot 83b] first hypothesized that rivers are fractal, and introduced fractal objects similar to river networks. With the goal of unifying different approaches to the computation of the fractal dimension of a river, [Claps 96] described a tree generation method using an IFS (Sect. 3.​3), in which an initiator (usually a unit-length line segment) is replaced by a generator (which is a tree-like structure of M arcs, each of length L). After a replacement, each segment of the generator becomes an initiator and is replaced by the generator; this process continues indefinitely.

In the construction of [Claps 96], each generator is the composition of a sinuosity generator, which turns a straight segment into a jagged segment which emulates the meandering of rivers, and a topology generator which emulates the branching of rivers. An example of a sinuosity generator is the well-known Koch curve, created by Helge von Koch in 1904, and illustrated in Fig. 5.5, where the initiator is the straight segment on the left. In each iteration, the middle third of each segment is replaced by two sides of an equilateral triangle. The dimension of the fractal generated from this sinuosity generator is $$\log 4 / \log 3$$ . Figure 5.6, from [Claps 96], illustrates a topology generator. In this figure, each of the three branches has length one-fourth the length of the initiator on the left. Since the tree on the right has seven equal length segments, then the dimension of this fractal generated from this topology generator is $$\log \, 7 / \log \, 4$$ . Let $${\mathcal {I}}_U$$ denote the above sinuosity generator, and let $${\mathcal {I}}_T$$ denote the above topology generator. Now define $${\mathcal {I}} \equiv {\mathcal {I}}_U \, {\mathcal {I}}_T$$ , which means we first apply $${\mathcal {I}}_T$$ and then apply $${\mathcal {I}}_U$$ . As applied to the straight line initiator, the result of applying $${\mathcal {I}}$$ is illustrated by Fig. 5.7.
../images/487758_1_En_5_Chapter/487758_1_En_5_Fig5_HTML.png
Figure 5.5

Sinuosity generator $${\mathcal {I}}_U$$ based on the Koch fractal

../images/487758_1_En_5_Chapter/487758_1_En_5_Fig6_HTML.png
Figure 5.6

Topology generator $${\mathcal {I}}_T$$

../images/487758_1_En_5_Chapter/487758_1_En_5_Fig7_HTML.png
Figure 5.7

$${\mathcal {I}} \equiv {\mathcal {I}}_U \, {\mathcal {I}}_T$$ applied to a straight line initiator

The effect of $${\mathcal {I}}_S$$ is to make the length of each of the seven line segments created by $${\mathcal {I}}_T$$ equal to 1/3. Since in this figure there are seven segments, each of which is one-third the length of the initiator, then this fractal has similarity dimension $$\log 7 / \log 3$$ . The similarity dimension of $${\mathcal {I}}$$ is equal to the product of the similarity dimensions of $${\mathcal {I}}_U$$ and $${\mathcal {I}}_T$$ ; that is,
$$\displaystyle \begin{aligned} d_{{S}} = \frac {\log 7}{ \log 3} = \left( \frac{\log 4}{ \log 3 } \right) \, \left( \frac{ \log 7 }{ \log 4 } \right) . \end{aligned}$$
This product relationship does not always hold; it does holds if M U, the number of equal length segments in the sinuosity iterator, is equal to 1∕L T, where L T is the length of each segment in the topology iterator [Claps 96]. In the example above, we have M U = 4 and L T = 1∕4. A “clean application” of the composition $${\mathcal {I}}_U \, {\mathcal {I}}_T$$ requires that the initial tree have equal arc lengths, and all angles between arcs be a multiple of π∕2 radians (i.e., all angles must be right angles).

Although the above analysis was presented in [Claps 96] without reference to nodes and arcs, it could have been presented in a network context, by defining an arc to be a segment and a node to be the point where two segments intersect. Suppose M U = 1∕L T, so the similarity dimension of $${\mathcal {I}}$$ is equal to the product of the similarity dimensions of $${\mathcal {I}}_U$$ and $${\mathcal {I}}_T$$ . We express this relationship as $$d_{{S}}({\mathcal {I}}) = d_{{S}}({\mathcal {I}}_U)d_{{S}}({\mathcal {I}}_T)$$ . The scaling factor of the IFS is α = 1∕L T, and $$d_{{S}}({\mathcal {I}})$$ is the fractal dimension of the fractal tree generated by this IFS. For t > 1, the tree network $${\mathbb {G}}_t$$ constructed in generation t by this IFS is a weighted network, since each arc length is less than 1.

Example 5.14 Another example of generating a tree from an IFS is the model of [Gao 09] for the structure of goose down. The top of Fig. 5.8 shows the basic motif, in which a line (i) is replaced by the pattern (ii) of 10 lines, each 1/4 the length of the original line. Then, starting with (iii), we apply the motif, yielding (iv). The next iteration applies the transformation (i) → (ii) to each line segment in (iv). If this construction is repeated indefinitely, the resulting fractal tree has similarly dimension $$d_{{S}} = \log 10 / \log 4 \approx 1.66$$ . □
../images/487758_1_En_5_Chapter/487758_1_En_5_Fig8_HTML.png
Figure 5.8

IFS for goose down

Exercise 5.2 Describe the above goose down construction by an IFS, explicitly specifying the similarities and contraction factors. □

A Penrose tiling [Austin 05] of $$\mathbb {R}^2$$ can be viewed as network that spans all of $$\mathbb {R}^2$$ . These visually stunning tilings can be described using an IFS, as described in [Ramachandrarao 00], which considered a particular tiling based on a rhombus, and observed that quasi crystals have been shown to pack in this manner.8 An interesting feature of this tiling is that the number of node and arcs can be represented using the Fibonacci numbers. Letting N(s) be the number of arcs of length s in the tiling, they defined the fractal dimension of the tiling to be $$\lim _{s \rightarrow 0} \log N(s)/\log (1/s)$$ and called this dimension the “Hausdorff dimension” of the tiling. Since the distance between two atoms in a quasi crystal cannot be zero, when considering the Penrose packing from a crystallographic point of view, a limit has to be placed on the number of iterations of the IFS; for this tiling, the atomic spacing limit was reached in 39 iterations. In [Ramachandrarao 00], a fractal dimension of 1.974 was calculated for the tiling obtained after 39 iterations, and it was observed that the fractal dimension approaches 2 as the number of iterations tends to infinity, implying a “non-fractal space filling structure.” Thus [Ramachandrarao 00] implicitly used the definition that a fractal is an object with a non-integer dimension.

Exercise 5.3 ../images/487758_1_En_5_Chapter/487758_1_En_5_IEq147_HTML.gif Pick a Penrose tiling, and explicitly specify the IFS needed to generate the tiling. □

5.4 Packing Dimension

The Hausdorff dimension (Sect. 5.1) is based upon covering a geometric object Ω by small sets X j in the most efficient manner, where “more efficient” means a smaller value of $$\sum _{j=1}^J \bigl (\mathit {diam} (X_j) \bigr )^d$$ . A “dual” approach to defining the dimension of Ω is to pack Ω with the largest number of pairwise disjoint balls whose centers lie in Ω, and where the radius of each ball does not exceed r. Our presentation of the packing dimension is based on [Edgar 08]. By a ball we mean a set
$$\displaystyle \begin{aligned} X(\widetilde{x}, r) \equiv \{ x \, \vert \, \mathit{dist}(\widetilde{x}, x) \leq r \} \end{aligned}$$
with center $$\widetilde {x}$$ and radius r.

Definition 5.5 Let $$\{ X(x_{{j}},r_{{j}}) \}_{j = 1}^{B_{{P}}(r)}$$ be a finite collection of B P(r) pairwise disjoint balls such that for each ball we have x j ∈ Ω and r j ≤ r.9 We do not require that X(x j, r j) ⊂ Ω. We call such a collection an r-packing of Ω. Let $${\mathcal {P}}(r)$$ denote the set of all r-packings of Ω. □

Example 5.15 Figure 5.9, where Ω is the diamond shaped region, illustrates an r-packing for which B P(r) = 4. Each ball center lies in Ω, but the entire ball is not contained in Ω. □
../images/487758_1_En_5_Chapter/487758_1_En_5_Fig9_HTML.png
Figure 5.9

Packing the diamond region with four balls

For d > 0 and r > 0, our goal, roughly speaking, is to maximize
$$\displaystyle \begin{aligned} \begin{array}{rcl} \sum_{j=1}^{B_{{P}}(r)} \left[ \mathit{diam} \big( X(x_{{j}},r_{{j}}) \big) \right]^d . {} \end{array} \end{aligned} $$
(5.14)
The reason for packing with balls, rather than with arbitrary sets, is illustrated by Fig. 5.10, where Ω is a square in $${\mathbb {R}}^2$$ . By choosing long skinny ovals, for d > 0 we can make the sum (5.14) arbitrarily large. While packing with hypercubes works well for a set $$\varOmega \subset {\mathbb {R}}^E$$ , to have a definition that works in a general metric space, we pack with balls. Since a subset of a metric space may contain no balls at all, we drop the requirement that each ball in the packing be contained in Ω. However, to ensure that the packing provides a measure of Ω, we require the center of each ball in the packing to lie in Ω. The balls in the packing are closed balls, but open balls could also be used.
../images/487758_1_En_5_Chapter/487758_1_En_5_Fig10_HTML.png
Figure 5.10

Packing a square with long skinny rectangles

Maximizing, over all r-packings, the sum (5.14) works well in $${\mathbb {R}}^E$$ , since the diameter of a ball of radius r is 2r. However, there are metric spaces for which this is not true. Thus, rather than maximizing (5.14), we maximize, over all r-packings, the sum
$$\displaystyle \begin{aligned} \begin{array}{rcl} \sum_{j=1}^{B_P(r)} (2 r_{{j}})^d . \end{array} \end{aligned} $$
That is, we are interested in
$$\displaystyle \begin{aligned} \begin{array}{rcl} \sup_{{\mathcal{P}}(r)} \sum_{j=1}^{B_P(r)} (2 r_{{j}})^d , {} \end{array} \end{aligned} $$
(5.15)
where $$\sup _{{\mathcal {P}}(r)}$$ denotes the supremum over all r-packings of Ω. As r decreases to 0, the set $${\mathcal {P}}(r)$$ shrinks, so the supremum in (5.15) decreases. Define
$$\displaystyle \begin{aligned} \begin{array}{rcl} f(\varOmega, d) = \lim_{r \rightarrow 0} \; \sup_{{\mathcal{P}}(r)} \; \sum_{j=1}^{B_P(r)} (2 r_{{j}})^d . {} \end{array} \end{aligned} $$
(5.16)
There is a critical value d 0 ∈ [0, ∞] such that
$$\displaystyle \begin{aligned} f(\varOmega, d) = \left\{ \begin{array}{ll} \infty &amp; \mbox{if } d&lt; d_{{0}} \\ 0 &amp; \mbox{if } d&gt; d_{{0}} . \end{array} \right. \end{aligned}$$
We do not want to call d 0 the packing dimension of Ω since, as the following example shows, it is possible to have the undesirable outcome that d 0 > 0 for a countable set Ω.
Example 5.16 Let Ω = {0, 1, 1∕2, 1∕3, 1∕4, ⋯ }. Let k be odd, choose r = 2−k, and let J = 2(k−1)∕2. Since
$$\displaystyle \begin{aligned} \frac{1}{J-1} - \frac{1}{J} &gt; \frac{1}{J^2} = 2r , \end{aligned}$$
the J balls with centers 1, 1∕2, 1∕3, ⋯, 1∕J and radius r are disjoint. Also, J(2r)1∕2 = 1. Choosing d = 1∕2, we have
$$\displaystyle \begin{aligned} \sup_{{\mathcal{P}}(r)} \; \sum_{j=1}^{B_{{P}}(r)} (2 r_{{j}})^d &gt; J (2r)^{1/2} = 1 . \end{aligned}$$
It follows from (5.16) that f(Ω, d) ≥ 1. □
The details of the resolution of this problem were provided in [Edgar 08]; here we provide only a brief sketch of the resolution. Define
$$\displaystyle \begin{aligned} f^{\star}(\varOmega, d) \equiv \inf_{{\mathcal{C}} } \, \sum_{C \in {\mathcal{C}}} f(C, d) , \end{aligned}$$
where the infimum is over all countable covers $$\mathcal {C}$$ of Ω by closed sets, and where f(C, d) is defined by (5.16). If we restrict Ω to be a measurable set, then f ⋆(Ω, d) is a measure, called the d-dimensional packing measure. Finally, if Ω is a Borel set,10 there is a critical value d P ∈ [0, ∞] such that
$$\displaystyle \begin{aligned} f^{\star}(\varOmega, d) = \left\{ \begin{array}{ll} \infty &amp; \mbox{if } d&lt; d_{{P}} \\ 0 &amp; \mbox{if } d&gt; d_{{P}} . \end{array} \right. \end{aligned}$$
The value d P is called the packing dimension of Ω. The packing dimension has many of the same properties as the Hausdorff dimension. For example, if A and B are Borel sets, then A ⊆ B implies d P(A) ≤ d P(B), and $$d_{{P}}(A \cup B) = \max \{ d_{{P}}(A), d_{{P}}(B) \}$$ . Also, if $$\varOmega \subset {\mathbb {R}}^1$$ then the one-dimensional packing measure coincides with the Lebesgue measure [Edgar 08].

Since d H considers the smallest number of sets that can cover Ω, and d P considers the largest number of sets that can be packed in Ω, one might expect a duality theory to hold, and it does. It can be shown [Edgar 08] that if Ω is a Borel subset of a metric space, then d H ≤ d P. This leads to another suggested definition [Edgar 08] of the term “fractal”: the set $$\varOmega \subset {\mathbb {R}}^E$$ is a fractal if d H = d P; it was mentioned in [Cawley 92] that this definition is due to S.J. Taylor. Under this definition, the real line $${\mathbb {R}}$$ is a fractal, so this definition is not particularly enlightening.

The packing dimension of a fractal Ω generated by an IFS was considered in [Lalley 88].11 A finite subset $$\widetilde {\varOmega }$$ of Ω is said to be r-separated if dist(x, y) ≥ r for all distinct points $$x, y \in {\widetilde {\varOmega }}$$ . In Fig. 5.9, the centers of the four circles are (2r)-separated. Let B P(r) be the maximal cardinality of an r-separated subset of Ω. Then d P satisfies
$$\displaystyle \begin{aligned} d_{{P}} = - \lim_{r \rightarrow 0} \frac {\log B_{{P}}(r)} {\log r} , \end{aligned}$$
provided this limit exists. Recalling that d S is the similarity dimension defined by (5.8), Lalley proved that if a certain Strong Open Set Condition holds then d S = d P = d B. The Strong Open Set Condition is stronger than the Open Set Condition given by Definition 5.4. The Strong Open Set Condition holds for the Cantor set, the Koch snowflake, and the Sierpiński gasket fractals generated by an IFS.

5.5 When Is an Object Fractal?

We have already discussed some suggested definitions of “fractal.” In this section we present, in chronological order, additional commentary on the definition of a “fractal.”

By 1983 [Mandelbrot 83a], Mandelbrot had abandoned the definition of a fractal as a set for which d H > d T, writing

But how should a fractal set be defined? In 1977, various pressures had made me advance the “tentative definition”, that a fractal is “a set whose Hausdorff-Besicovitch dimension strictly exceeds its topological dimension”. But I like this definition less and less, and take it less and less seriously. One reason resides in the increasing importance of the “borderline fractals”, for example of sets which have the topologically “normal” value for the Hausdorff dimension, but have anomalous values for some other metric dimension. I feel - the feeling is not new, as it had already led me to abstain from defining “fractal” in my first book of 1975 - that the notion of fractal is more basic than any particular notion of dimension. A more basic reason for not defining fractals resides in the broadly-held feeling that the key factor to a set’s being fractal is invariance under some class of transforms, but no one has yet pinned this invariance satisfactorily. Anyhow, I feel that leaving the fractal geometry of nature without dogmatic definition cannot conceivably hinder its further development.

An interesting historical perspective on this was provided in [Bez 11], who wrote

Mandelbrot [Mandelbrot 75] himself, the father of the concept, did not provide the scientific community with a clear and unique definition of fractal in his founding literature which was written in French. This was indeed deliberate as stated by Mandelbrot [Mandelbrot 77] himself in the augmented English version published 2 years later: “the French version deliberately avoided advancing a definition” (p. 294). The mathematical definition finally coined in 1977 stated that “an object is said to be fractal if its Hausdorff-Besicovitch dimension d H is greater than its topological dimension d T”.

A convenient working definition of fractals was provided in [Theiler 90]:

Fractals are crinkly objects that defy conventional measures, such as length and area, and are most often characterized by their fractal dimension.

Theiler divided fractals into either solid objects or strange attractors; [Theiler 90] predated the application of fractal methods to networks, with the significant exception of [Nowotny 88], studied in Chap. 12. Examples of solid object fractals are coastlines, electrochemical deposits, porous rocks, spleenwort ferns, and mammalian brain folds.12 Strange attractors, on the other hand, are conceptual fractal objects that exist in the state space of chaotic dynamical systems (Chap. 9).
Mandelbrot’s 1977 definition excluded some self-similar geometric objects which might be deserving of being called fractals. Such an example is the Lévy curve, named after the French mathematician Paul Lévy (1886–1971). The steps for constructing this curve are illustrated in Fig. 5.11. The basic step in the construction is described by (i) each line segment (the dotted line, with length 1) is replaced by an angled pair of lines (the solid lines, each of length $$1/\sqrt {2}$$ ). To generate the Lévy curve using the basic step, start with (ii) and replace each of the three lines by an angled pair of lines, yielding (iii). After 12 iterations, we obtain Fig. 5.12. 13 The similarity dimension is $$d_{{S}} = \log (2) /\log (1/\sqrt {2}) =2$$ , so this curve is “space-filling” in $${\mathbb {R}}^E$$ , and d B = d S. It follows from a theorem in [Falconer 89] that d H = d B. In [Lauwerier 91], it was deemed “a pity” that, under Mandelbrot’s 1977 definition, the Lévy curve does not get to be called a fractal. Lauwerier continued with “Let it be said again: the essential property of a fractal is indefinitely continuing self-similarity. Fractal dimension is just a by-product.” In a later edition of The Fractal Geometry of Nature, Mandelbrot regretted having proposed a strict definition of fractals [Briggs 92]. In 1989, [Mandelbrot 89] observed that fractal geometry “… is not a branch of mathematics like, for example, the theory of measure and integration. It fails to have a clean definition and unified tools, and it fails to be more or less self contained.”
../images/487758_1_En_5_Chapter/487758_1_En_5_Fig11_HTML.png
Figure 5.11

Constructing the Lévy curve

../images/487758_1_En_5_Chapter/487758_1_En_5_Fig12_HTML.png
Figure 5.12

The Lévy curve after 12 iterations

Making no reference to the concept of dimension, fractals were defined in [Shenker 94] “… as objects having infinitely many details within a finite volume of the embedding space. Consequently, fractals have details on arbitrarily small scales, revealed as they are magnified or approached.” Shenker stated that this definition is equivalent to Mandelbrot’s definition of a fractal as an object having a fractal dimension greater than its topological dimension. As we will discuss in Sect. 20.​4, Shenker argued that fractal geometry does not model the natural world; this opinion is most definitely not a common view.

A perspective similar to that of Lauwerier was offered in [Jelinek 98], who noted that not all self-similar objects are fractal. For example, the Pythagoras tree (the tree after 15 generations is shown in Fig. 5.13) is self-similar, has Hausdorff dimension 2, and thus cannot be called a fractal if the defining
../images/487758_1_En_5_Chapter/487758_1_En_5_Fig13_HTML.png
Figure 5.13

Pythagoras tree after 15 iterations

characteristic is a non-integer dimension. The conclusion in [Jelinek 98] was that self-similarity or the fractal dimension are not “absolute indicators” of whether an object is fractal.

It was also observed in [Jelinek 98] that the ability to calculate a fractal dimension of a biological image does not necessarily imply that the image is fractal. Natural objects are not self-similar, but rather are scale invariant over a range, due to slight differences in detail between iteration (i.e., hierarchy) levels. The limited resolution of any computer screen necessarily implies that any biological image studied is pre-fractal. Also, the screen resolution impacts the border roughness of an object and thus causes the computed fractal dimension to deviate from the true dimension. Thus the computed dimension is not very precise or accurate, and is not significant beyond the second decimal place. However, the computed dimension is useful for object classification.

We are cautioned in [Halley 04] that, because fractals are fashionable, there is a natural tendency to see fractals everywhere. Moreover, it was observed in [Halley 04] that the question of deciding whether or not an object is fractal has received little attention. For example, any pattern, whether fractal or not, when analyzed by box counting and linear regression may yield an excellent linear fit, and logarithmic axes tend to obscure deviations from a power-law relationship that might be quite evident using linear scales. In [Halley 04], some sampling and Monte Carlo approaches were proposed to address this question, and it was noted that higher-order Rényi dimensions (Chap. 16) and maximum likelihood schemes can be applied to estimate dimension, but that these methods often utilize knowledge of the process generating the pattern, and hence cannot be used in an “off the shelf” manner as box counting methods can. Indeed, [Mandelbrot 97] observed that fractal geometry “cannot be automated” like analysis of variance or regression, and instead one must always “look at the picture.”