Self-similar sets with overlap

Mark McClure

UNC - Asheville

Needs["FractalGeometry`IteratedFunctionSystems`"];
A = (({{1/2, 0}, {0, 1/2}}));
finiteTypeIFS= {
{A,{1/4,Sqrt[3]/4}}, 
{A,{0,0}},
{A,{1/4,0}}, 
{A,{1/2,0}}
};
conditionSet = {{0,0},{1,0},{1/2,Sqrt[3]/2}};
GraphicsGrid[{Table[ShowIFS[finiteTypeIFS,k, Initiator -> 
{Opacity[0.3],EdgeForm[Black],Polygon[conditionSet]}],
{k,0,6,2}]}]

The well-known Sierpinksi triangle

Needs["FractalGeometry`IteratedFunctionSystems`"];
A = (({{1/2, 0}, {0, 1/2}}));
finiteTypeIFS= {
{A,{1/4,Sqrt[3]/4}}, 
{A,{0,0}},
{A,{1/2,0}}
};
conditionSet = {{0,0},{1,0},{1/2,Sqrt[3]/2}};
GraphicsGrid[Partition[Table[ShowIFS[finiteTypeIFS,k, Initiator -> 
{Opacity[0.3],EdgeForm[Black],Polygon[conditionSet]}],
{k,0,5}],3]]

The Sierpinski triangle consists of three copies of itself, scaled by the factor 1/2.  It's “dimension” is log(3)/log(2)≈1.58.

A not so well known fractal triangle

Needs["FractalGeometry`IteratedFunctionSystems`"];
A = (({{1/2, 0}, {0, 1/2}}));
finiteTypeIFS= {
{A,{1/4,Sqrt[3]/4}}, 
{A,{0,0}},
{A,{1/4,0}}, 
{A,{1/2,0}}
};
conditionSet = {{0,0},{1,0},{1/2,Sqrt[3]/2}};
GraphicsGrid[Partition[Table[ShowIFS[finiteTypeIFS,k, Initiator -> 
{Opacity[0.3],EdgeForm[Black],Polygon[conditionSet]}],
{k,0,5}],3]]

Dimension = ??

Similarity dimension

A set E is called self-similar if it is composed of smaller copies of itself.

More precisely, there is a finite list of functions {(Subscript[f, 1]),(Subscript[f, 2]),…,(Subscript[f, m])}  mapping (ℝ^2)->(ℝ^2) such that

E = (⋃_(i=1)^m)(Subscript[f, i])(E).

If each function is a simple scaling by the factor r, then the similarity dimension is

((log(m))/(log(1/r))).

This agrees with other notions of dimension, provided there is not significant overlap between the pieces.

But why?

When we say that a formula yields the correct dimension of a set, we mean that (under suitable hypotheses) the formula agrees with a well established and broadly applicable notion of dimension.

The similarity dimension formula is valid when the pieces don't overlap.  
But, we are interested in when the pieces do overlap.

Covering dimension

Suppose we cover a set with sets of smaller size ε (as measured by length across).  
The smaller ε, the more sets required.

Let (Subscript[C, ε])(E) denote the smallest possible number of sets in such a cover.  The rate at which (Subscript[C, ε])(E)->∞ as ε↘0 indicates the dimension of the set.

For example, the number of sets of size ε required to cover a curve of length L grows like L/ε.

pts = {{0.09375`,0.36995967741935487`},{0.11794354838709675`,0.36995967741935487`},{0.12802419354838712`,0.36995967741935487`},{0.1401209677419355`,0.36995967741935487`},{0.15423387096774194`,0.36995967741935487`},{0.17036290322580644`,0.36995967741935487`},{0.18850806451612906`,0.36995967741935487`},{0.20463709677419356`,0.36995967741935487`},{0.23891129032258063`,0.36995967741935487`},{0.26713709677419356`,0.36995967741935487`},{0.3014112903225806`,0.371975806451613`},{0.33770161290322576`,0.3780241935483871`},{0.3618951612903226`,0.3860887096774194`},{0.3921370967741935`,0.39616935483870974`},{0.4183467741935484`,0.4082661290322581`},{0.438508064516129`,0.41633064516129037`},{0.46875`,0.42842741935483875`},{0.47883064516129037`,0.43245967741935487`},{0.49294354838709675`,0.4385080645161291`},{0.5110887096774194`,0.4485887096774194`},{0.5352822580645161`,0.46068548387096775`},{0.5514112903225806`,0.46875`},{0.5655241935483871`,0.47883064516129037`},{0.5756048387096774`,0.4868951612903226`},{0.5836693548387096`,0.49495967741935487`},{0.59375`,0.5050403225806452`},{0.6078629032258065`,0.5211693548387097`},{0.6159274193548387`,0.53125`},{0.6219758064516129`,0.5393145161290323`},{0.6280241935483871`,0.5514112903225807`},{0.6340725806451613`,0.5655241935483871`},{0.6360887096774194`,0.5735887096774194`},{0.6360887096774194`,0.5816532258064517`},{0.6360887096774194`,0.589717741935484`},{0.6340725806451613`,0.5977822580645162`},{0.6300403225806451`,0.6058467741935485`},{0.626008064516129`,0.6139112903225807`},{0.6199596774193549`,0.6199596774193549`},{0.6098790322580645`,0.626008064516129`},{0.5977822580645161`,0.6340725806451613`},{0.5856854838709677`,0.6381048387096775`},{0.5715725806451613`,0.6421370967741935`},{0.5473790322580645`,0.6461693548387097`},{0.5252016129032258`,0.6461693548387097`},{0.5070564516129032`,0.6481854838709677`},{0.49495967741935487`,0.6481854838709677`},{0.4808467741935484`,0.6481854838709677`},{0.46875`,0.6481854838709677`},{0.45866935483870963`,0.6481854838709677`},{0.4506048387096774`,0.6481854838709677`},{0.44455645161290325`,0.6441532258064517`},{0.438508064516129`,0.6401209677419355`},{0.43245967741935487`,0.6340725806451613`},{0.42842741935483875`,0.6280241935483871`},{0.4264112903225806`,0.621975806451613`},{0.4223790322580645`,0.6139112903225807`},{0.4203629032258065`,0.6058467741935485`},{0.41633064516129037`,0.5957661290322581`},{0.41431451612903225`,0.5836693548387097`},{0.41431451612903225`,0.5715725806451613`},{0.41431451612903225`,0.559475806451613`},{0.41431451612903225`,0.5453629032258065`},{0.4183467741935484`,0.53125`},{0.4243951612903226`,0.5131048387096775`},{0.43245967741935487`,0.496975806451613`},{0.4405241935483871`,0.4828629032258065`},{0.4546370967741935`,0.466733870967742`},{0.4808467741935484`,0.44254032258064524`},{0.5151209677419355`,0.4183467741935485`},{0.5473790322580645`,0.4022177419354839`},{0.5997983870967741`,0.38407258064516137`},{0.6381048387096774`,0.3760080645161291`},{0.6804435483870968`,0.371975806451613`},{0.7288306451612903`,0.36995967741935487`},{0.7651209677419355`,0.373991935483871`},{0.7913306451612903`,0.373991935483871`},{0.8336693548387096`,0.3780241935483871`},{0.8578629032258064`,0.38205645161290325`},{0.8820564516129031`,0.3860887096774194`},{0.9002016129032259`,0.3921370967741936`},{0.9122983870967741`,0.40020161290322587`},{0.9203629032258064`,0.40625`},{0.9385080645161291`,0.4183467741935485`},{0.9506048387096774`,0.42842741935483875`},{0.9627016129032259`,0.4385080645161291`},{0.9727822580645161`,0.4526209677419355`},{0.9768145161290321`,0.4566532258064516`},{0.9848790322580644`,0.46875`},{0.9889112903225806`,0.47883064516129037`},{0.9929435483870966`,0.4868951612903226`},{0.9969758064516129`,0.49294354838709686`},{0.9969758064516129`,0.49495967741935487`},{0.9989919354838709`,0.496975806451613`},{0.9989919354838709`,0.498991935483871`},{0.9989919354838709`,0.5010080645161291`}};
tol = 0.005;
divide[{p1_,p2_}] := {p1,(p1+p2)/2} /; Norm[p1-p2] >tol;
divide[{p1_,p2_}] := {p1} /; Norm[p1-p2]≤tol;
step[points_] := Partition[Flatten[Join[divide /@ 
Partition[points,2,1],Last[points]]],2]
pts = FixedPoint[step,pts];
stepSize= 1/(Length[pts]-1);
funcPoints = Table[{(i-1)*stepSize,pts[[i]]},{i,1,Length[pts]}];
xfunc = Interpolation[{#[[1]],#[[2,1]]}& /@ funcPoints];
yfunc = Interpolation[{#[[1]],#[[2,2]]}& /@ funcPoints];
Graphics[{
{GrayLevel[0.5], EdgeForm[Black],
Table[Disk[{xfunc[t],yfunc[t]},0.012],{t,0,1,0.01}]},
Line[pts]}]

Similarly the number of sets required to cover a two dimensional set with area A grows like A/(ε^2).

Setting (Subscript[C, ε])∼1/(ε^dim) we see the dimension ought to be

(lim_(ε->(SuperPlus[0])))((log (Subscript[C, ε])(E))/(log (1/ε))).

Sierpinski dimension

The Sierpinski triangle naturally decomposes into (3^n) pieces of size 1/(2^n).

Needs["FractalGeometry`IteratedFunctionSystems`"];
A = (({{1/2, 0}, {0, 1/2}}));
finiteTypeIFS= {
{A,{1/4,Sqrt[3]/4}}, 
{A,{0,0}},
{A,{1/2,0}}
};
conditionSet = {{0,0},{1,0},{1/2,Sqrt[3]/2}};
GraphicsRow[Table[Labeled[ShowIFS[finiteTypeIFS,k, Initiator -> 
{Opacity[0.3],EdgeForm[Black],Polygon[conditionSet]}],
Style[StringReplace["(Subscript[C, (2^(-k))]) = ","k" -> ToString[k]] <> ToString[3^k],Larger]],
{k,0,2}]]

Thus

dim(S) = (lim_(n->∞))((log((3^n)))/(log((2^n))))=((log(3))/(log(2))).

More generally, given a self-similar set without overlap and with m pieces scaled by the factor r, we can compute the dimension via

(lim_(n->∞))((log (m^n))/(log (1/(r^n)))) = ((log(m))/(log(1/r))).

An example with overlap

The difficulty in this example is the overlap.

Needs["FractalGeometry`IteratedFunctionSystems`"];
A = (({{1/2, 0}, {0, 1/2}}));
finiteTypeIFS= {
{A,{1/4,Sqrt[3]/4}}, 
{A,{0,0}},
{A,{1/4,0}}, 
{A,{1/2,0}}
};
conditionSet = {{0,0},{1,0},{1/2,Sqrt[3]/2}};
GraphicsGrid[Partition[Table[ShowIFS[finiteTypeIFS,k, Initiator -> 
{Opacity[0.3],EdgeForm[Black],Polygon[conditionSet]}],
{k,0,2}],3]]

Note that we have 4 pieces scaled by the factor 1/2.  The dimension cannot exceed log(4)/log(2)=2.

The analysis - decomposition

Needs["FractalGeometry`IteratedFunctionSystems`"];
A = (({{1/2, 0}, {0, 1/2}}));
finiteTypeIFS= {
{A,{1/4,Sqrt[3]/4}}, 
{A,{0,0}},
{A,{1/4,0}}, 
{A,{1/2,0}}
};
conditionSet = {{0,0},{1,0},{1/2,Sqrt[3]/2}};
GraphicsGrid[Partition[Table[ShowIFS[finiteTypeIFS,k, Initiator -> 
{Opacity[0.3],EdgeForm[Black],Polygon[conditionSet]}],
{k,0,2}],3]]

We need to count the rate of growth of the number sets required to cover the set.  We'll use four types of sets in our cover.
  • (Subscript[𝒯, 1]): A triangle without overlap
  • (Subscript[𝒯, 2]): A triangle overlapping another to the right
  • (Subscript[𝒯, 3]): A triangle overlapping another to the left
  • (Subscript[𝒯, 4]): A triangle overlapping two triangles on either side.

We can see that

(Subscript[𝒯, 1])->(Subscript[𝒯, 1])+(Subscript[𝒯, 2])+(Subscript[𝒯, 3])+(Subscript[𝒯, 4]).

It's somewhat harder to figure out the decompositions of the other types.
Nonetheless, it can be shown that (if we count the pieces correctly),

(Subscript[𝒯, 2])->(Subscript[𝒯, 1])+(Subscript[𝒯, 2])+(Subscript[𝒯, 3])         
(Subscript[𝒯, 3])->(Subscript[𝒯, 1])+      2(Subscript[𝒯, 3])         
(Subscript[𝒯, 4])->(Subscript[𝒯, 1])+      2(Subscript[𝒯, 3])+(Subscript[𝒯, 4])

Note that the overlap between a (Subscript[𝒯, 2]) and a (Subscript[𝒯, 3]) is always a new (Subscript[𝒯, 3]).  We always choose this new (Subscript[𝒯, 3]) to belong to the old (Subscript[𝒯, 3]).

A similar choice must be made for the (Subscript[𝒯, 3]) / (Subscript[𝒯, 4]) overlap.

The analysis - growth rate

The decomposition relationships from the previous slide can be represented by the following matrix.

M = (({{1, 1, 1, 1}, {1, 1, 1, 0}, {1, 0, 2, 0}, {1, 0, 2, 1}}));

Let (Subscript[N, k]) denote the total number of sets at level k.  Then (Subscript[N, k]) is the sum of the terms in (M^(k-1)).  Asymptotically, (Subscript[N, k])∼(λ^k), where λ is the spectral radius of the matrix.

Max[Abs[Eigenvalues[M]]]

The size of the sets used in the covering at level k is on the order (3^(-k)).  Thus, the dimension is

Log[2+(Sqrt[2])]/Log[2] // N

A Mathematica package

Define the IFS and condition set.
The condition set C must satisfy

C⊃ (⋃_(i=1)^m)(Subscript[f, i])(C).

A = {{1/2,0},{0,1/2}};
finiteTypeIFS= { 
{A,{0,0}}, {A,{1/2,0}},{A,{1/4,Sqrt[3]/4}},{A,{1/4,0}}};
conditionSet = {{0,0},{1,0},{1/2,Sqrt[3]/2}};

Perform the computation.

Needs["FractalGeometry`FiniteTypeIFS`"];
{r, T, V} = FiniteTypeInfo[finiteTypeIFS, conditionSet];
spectralRadius = First[Eigenvalues[T,1]];
dimension = -Log[spectralRadius]/Log[r]

MatrixForm[T]

Investigate the types

GraphicsRow[Show[#,PlotRange -> {{0,1},{0,1}},
Axes -> True]& /@  TypePics[V,conditionSet]]

A harder example

The picture.

Needs["FractalGeometry`IteratedFunctionSystems`"];
A = {{1/2,0},{0,1/2}};
f1 = {A,{0,0}};
f2 = {A,{1/2,0}};
f3 = {A,{1/4,Sqrt[3]/4}};
f4 = {A.RotationMatrix[Pi]/2,{5/8,0}};
finiteTypeIFS = {f1,f2,f3,f4};
conditionSet = {{0,0},{1/2,-Sqrt[3]/4},{1,0},{1/2,Sqrt[3]/2}};
GraphicsRow[{
ShowIFS[finiteTypeIFS, 1, Initiator -> {Opacity[0.5],
EdgeForm[Black],Polygon[conditionSet]},
PlotRange -> {{0,1},{-Sqrt[3]/4,Sqrt[3]/2}},
Epilog -> {Thick,Line[Append[conditionSet, First[conditionSet]]]}],
ShowIFS[finiteTypeIFS, 7, Initiator -> {Opacity[0.5],
EdgeForm[Black],Polygon[conditionSet]}]}]

Here's an upper bound for the dimension.

Last[s/.Solve[3/(2^s)+1/(4^s)==1,s]]

%//N

The finite type techniqe allows us to compute the exact dimension.

Needs["FractalGeometry`FiniteTypeIFS`"];
{r, T, V} = FiniteTypeInfo[finiteTypeIFS, conditionSet]; // Timing
spectralRadius = First[Eigenvalues[T,1]];
dimension = -Log[spectralRadius]/Log[r]

N[dimension]

There are 28 types.

Length[T]

TypePics[V,conditionSet][[2]]

Programming notes

• Program uses a number of mathematical tools
  • Linear algebra
    • Basic iterative computations
    • Exact Eigenvalues
  • Computational geometry
     • Convex intersection
     • Nearest for canonicalization
  • Structural manipulation

• Confidence in detecting intersection is very important.
  (More generally, detecting when two objects are the same.)

• Program uses exact computation by default, but you can plug in approximate numbers.

• In either case, a canonicalization procedure must be used to tell when two numbers are the same.
  Roughly, two numbers are treated the same, if they differ by less than some error tolerance.
  Thanks to Dan Lichtblau for some improvements!

References

Sze - Man Ngai and Yang Wang, "Hausdorff dimension of self-similar sets with overlaps.", J. London Math. Soc. (2) 63 (2001), no. 3, 655 - 672.

Mark McClure, "Finite type iterated function systems: a computational perspective", to be submitted to Fractals.