# Message Boards

Answer
(Unmark)

GROUPS:

2

# Using entropy to estimate the dimension of the Sierpinski triangle

Posted 2 months ago

Using entropy to estimate the dimension of the Sierpinski triangle It turns out to be about 1.62
Introduction To estimate the dimension of self-similar structures like fractals, we usually use Hausdorff dimension, which basically tells us how quickly the volume of the object increases with size. But what if we use information theory to estimate the dimensions of things? To specify the position of a point in d d d d 1/n H=∑ p i p i p i i d a 3 a 3 n H=3Log[n]+3Log[a] d H=dLog[n]+ d d H=dLog[n]+ d H Log[n] H Log[d] H n H=dLog[n]+ d n In[]:= ClearAll[geomEntropy];geomEntropy[points_, n_] := Block[ npoints, counts, probs, entropy , counts = countPoints[points, n]; npoints = Length[points]; probs = Flatten[counts / npoints]; Total[If[# 0, 0, N[-# Log[#]]]& /@ probs]]; For practical reasons, 2D space was chosen instead of 3D, which is not a big problem because the Sierpinski triangle lives in 2D space. Also, the region is taken to always be 0≤x≤1 0≤y≤1 2 n In[]:= ClearAll[countPoints];countPoints[points_, n_] := Block[ customRound, incr, counts , customRound[x_] := Min[1 + IntegerPart[n x], n]; incr[a_, b_] := counts[[customRound[a], customRound[b]]]++; counts = ConstantArray[0, {n, n}]; Apply[incr, #]& /@ points; counts]; Let us try to determine the dimension of a circle. For that, let us take 2000 equidistant points in that circle: In[]:= circlepoints=N 1 2 1 2 # 2 In[]:= Graphics[Point/@circlepoints,ImageSizeSmall] Out[]= Here, the constant vector {1/2,1/2} 1/2 0≤x≤1 0≤y≤1 2 8 In[]:= {drawGrid[circlepoints,8],ArrayPlot[countPoints[circlepoints,8],ImageSizeSmall]} Out[]= , Here, darker squares have more points in them. Here is the value of “geometrical entropy” that we get: In[]:= geomEntropy[circlepoints,8] Out[]= 3.30534 To estimate the dimension, we would want to plot this. Here is a special function for that: In[]:= plotGeomEntropy[circlepoints, # 2 Out[]= We have just used entropy to estimate the dimension of a circle, and the result came out right! Isn’t that awesome? plotGeomEntropy computes the value of the “geometrical entropy” for various values of n H Log[n] H Log[n] In[]:= solidcirclepoints=FlattenTableIf 2 1 2 2 1 2 2 1 2 1 200 1 200 In[]:= Graphics[Point/@solidcirclepoints,ImageSizeSmall] Out[]= In[]:= plotGeomEntropy[solidcirclepoints, # 2 Out[]= If we cover the circle in uniform square mesh of points, the dependency of H Log[n] In[]:= plotGeomEntropy[{{0,0}}, # 2 Out[]= The entropy is just always zero, so the estimated dimension is zero, as expected. Thus, we see that the concept works, at least for shapes with integer dimension. Let’s now try fractals.
Supplemental code
Estimating the dimension of fractals Let us now get to the “salt” of this essay, the Sierpinski triangle. To estimate its dimension, let us use the 8-th level approximation (the code used to generate the points is given at the end of the section): In[]:= sierpinskipoints=sierpinskiPoints[8]; In[]:= Graphics[{PointSizeSmall,Point[#]}&/@sierpinskipoints] Out[]= Since all the necessary tools have already been presented in the previous section, we can simply use the function plotGeomEntropy: In[]:= plotGeomEntropy[sierpinskipoints, # 2 Out[]= Notice that although the dimension of the Sierpinski triangle is not integer, the dependency of H Log[n] 1.62 11 In[]:= sierpinskipoints11=sierpinskiPoints[11]; In[]:= plotGeomEntropy[sierpinskipoints11, # 2 Out[]= The dimension is again around 1.62 In[]:= kochpoints=kochPoints[6]; In[]:= Graphics[{PointSizeSmall,Point[#]}&/@kochpoints] Out[]= Only one third of the snowflake is used to reduce the computational complexity; obviously, the dimension of one third of the snowflake is equal to the dimension of the original snowflake, so it’s alright to split it. Here is what the plot of the “geometrical entropy” as a function of Log[n] In[]:= plotGeomEntropy[kochpoints, # 2 Out[]= The dependency of H Log[n] 1.30 9 In[]:= kochpoints9=kochPoints[9]; In[]:= plotGeomEntropy[kochpoints9, # 2 Out[]= The new estimate is again approximately 1.30 H d H Log[n] In[]:= {drawGrid[sierpinskiPoints[4],5],drawGrid[sierpinskiPoints[6],5]} Out[]= ,
Supplemental code
“Dimension” of a finite set of points The previous sections showed how we can use entropy to measure the dimension of a geometrical object by approximating it as a finite set of points. What if we just take the tools introduced there and apply them to finite sets of points? What would be the meaning of the results we get, if there is one at all? To find out on the example of 20 points on a semicircle. In[]:= semicirclePoints=Table 1 2 Cos[φ] 2 Sin[φ] 2 In[]:= Graphics[Point/@semicirclePoints,ImageSizeSmall] Out[]= Here is what the plot of “geometrical entropy” as a function of Log[n] In[]:= plotGeomEntropy[semicirclePoints, # 2 Out[]= You can see that the plot starts out linear and then suddenly flattens out and becomes constant. This is because as the number of square subregions grows larger, there are fewer and fewer points in each square. At some point, there are so many squares that each point just has its own personal square, and adding new squares just doesn’t change anything: In[]:= {drawGrid[semicirclePoints,3],drawGrid[semicirclePoints,7],drawGrid[semicirclePoints,13],drawGrid[semicirclePoints,29]} Out[]= , , , Above you can see the set of points, with the grid drawn on top of it, for n=3,7,13,29 n=29 H Log[n] d H n n 1 H |