Category Archives: fractals

Late to the recursion game.

Ok, confession time: every once in a while, you find out something that apparently everyone except for you knows about (I’m looking at you, pronunciation-of-rendezvous).  This time, I totally missed out on recursion in the course of teaching myself how to program.  For those in the same boat as me, this means you can call a function inside the same function.  So long as you specify a base case (and make sure you reach this base case), you can get a reasonable answer.

In the course of rectifying this, I’ve written two toy programs.  The first is very un-mathy, but essentially solves the game “TextTwist“. First I use recursion to find all possible substrings of a collection of letters, then I import an English dictionary (thank you, Python!), and check these substrings against the dictionary to come up with a list of English-language words.  See below for the print-out.

The dictionary I am using is a little bit generous with what it allows as a word, but I'd rather err on the side of being thorough in this case.

The second program I wrote was in MATLAB, and the code is a little cleaner, so I can in fact post it here.  It uses recursion to again generate the Sierpinski gasket from the flurry of fractal posts I had earlier, though this is a deterministic approach.  What it does is takes a column of points determining the vertices of a triangle (or any other shape), then for each point, returns a column determining the points of a triangle whose vertices are halfway to the previous vertex, and halfway to the next vertex.  The code may be easier to read, noticing especially that I call gasket on the third to last line:


function [A,B] = gasket(X,Y,N)
%returns the coordinates of the vertices for a Sierpinski gasket with N
%iterations
m = size(X,1)-1;
A = [];
B = [];
for k = 1:m-1
A = [A,[X(cmod(k,m),:);(X(cmod(k+1,m),:)+X(cmod(k,m),:))/2;(X(cmod(k-1,m),:)+X(cmod(k,m),:))/2;X(cmod(k,m),:)]];
B = [B,[Y(cmod(k,m),:);(Y(cmod(k+1,m),:)+Y(cmod(k,m),:))/2;(Y(cmod(k-1,m),:)+Y(cmod(k,m),:))/2;Y(cmod(k,m),:)]];
end
if N~=1
[A,B] = gasket(A,B,N-1);
end
end

The function “cmod” just changes the “mod” function so that “cmod(m,m) = m” instead of the usual behavior where “mod(m,m) = 1″.  Running this code with N = 8, we get the following image:

Noticeably cleaner than at least some of the randomly generated fractals from earlier, and at the very least faster.  After 8 iterations, there are 3^8 = 6561 triangles, and for each we store 4 pairs of numbers to generate a triangle (I am calling the “line” command, which means I need to specify that the start and end points are the same), so the total number of numbers I store is 52,488, compared to 100,000 for this much lower resolution version from earlier.  Also, I can start with any set of points I want with this program, so here is a belated Valentine for everyone:

It is somewhat hard to find interesting, mostly convex parametric curves, ok?

Hausdorff dimension II

I left off yesterday asking how to measure a surface (something sort of 2-dimensional) in 3-space, and noting that Lebesgue measure would give this set 0 area.  This is where Hausdorff measure comes in.  There is in fact a continuum of Hausdorff measures, one for each real number.  First it is helpful to define the diameter of a set, which is just the farthest distance apart of two points in the set.  For a circle, the diameter is the usual definition.  Also, we’ll denote the diameter of a set U by |U|.

The construction of the measure is typically described in two steps: Suppose we are trying to find the m-dimensional Hausdorff measure of a set U.  Then in the first step, we cover U by sets no larger than some number, d, and look at the sum of the diameters of these sets raised to the mth power. The smallest (well, infimum) of these coverings will be the number we associate with the parameter d.  In the second step, we let d go to zero.  The Hausdorff measure is the limit, if it exists.  In symbols,

Two sets with (approximately) the same diameter, indicated with the red line.

H^m_d(U) = inf \sum_{k = 1}^{\infty} |U_k|^m, where |U_k| < d for each k.  Then H^m(U) = \lim_{d \to 0} H^m_d(U).  There is an easy result (see, for example, Falconer’s “Geometry of Fractal Sets“) that says that for any set U, there is a unique value, called the Hausdorff dimension of U so that H^m(U) = \infty \text{ if } 0 \leq d < \dim U and H^d(E) = 0 \text{ if } \dim U< s < \infty.  Note that the Hausdorff measure might be 0 or infinite, but this number will still exist.

We should also note that:

  1. Nowhere in the definition did I use anything but distance, making all these concepts valid in metric spaces, as well as in Euclidean (vector) spaces.
  2. Nowhere in the definition did I require the Hausdorff dimension to be an integer.

Expanding on this second point brings us into discussing fractals, which I have discussed a bit in the past week, but have not defined.  One reason for this is that I have not seen a great definition.  Self similarity is important, as is having a Hausdorff dimension different from its topological dimension.  At the very least, any self similar set whose Hausdorff dimension is not an integer would be given “fractal” status, though this would miss many good examples.  In any case, for any self similar set, the Hausdorff dimension is log(m)/log(s), where m is the number of copies at each step, and s is the (linear) scaling factor.

So if you view the real plane as a self similar set taken by starting with a square, then dividing it into four squares, and then each of those into four squares, and so on, then the number of copies is 4 and the scaling factor is 2 (Remember, it is the linear scaling factor! Each side is half the length it used to be.), so the Hausdorff dimension is log(4)/log(2), which is precisely 2, since \log{4}/\log{2} = \log{2^2}/\log{2} = 2\log{2}/\log{2}.

I have printed below two more examples of fractals and their dimensions.  Thanks to Leonid Kovalev for pointing out how to generate the Sierpinski carpet.  Also see this great wikipedia post for a much more complete list of fractals and their dimensions.

Dimension log(3)/log(2).
Has dimension log(8)/log(3) = 3*log(2)/log(3).

Fractal followup followup

Again, after yesterday’s post (which was a response to the post of two days ago), I found a few more cool things with this method of generating fractals.  In particular, we take our point x and a random vertex v, then move our point to ax + bv.  To get the Sierpinski carpet, we have a = 2, b = 2.  To get the sets from yesterday, I used a = 1/(n-1), b = (n-2)/(n-1), where n was the number of vertices.  Today, I share some pictures using a = k/(n-1), b = (n-k-1)/(n-1).  I am not sure whether each of these is a fractal (though I suspect they are), but there is something going on (note- Leonid Kovalev pointed out yesterday that Jeremy Tyson and Jang-Mei Wu have a paper (pdf link) investigating sets generated like this):

5 vertices, with k = 2. Used 500,000 points for this one, I think most of the pentagon is meant to be in the set...

6 vertices, with k = 2.

7 vertices, with k = 2. Looks a little like the chainring on my bike...

16 vertices, k = 1

 

16 vertices, k = 2

16 vertices, k = 3

16 vertices, k = 4

Randomness Followup

Starting with four vertices.

In yesterday’s post a fractal was made by repeatedly moving a point halfway to a randomly selected vertex of a triangle, and I noted that the same magic does not happen with four vertices.  How young and foolish I was then!

Playing with the code a bit, I found that you may instead

1. Start with a point x inside a regular n-gon.

2. Choose a random vertex v.

3. Move your point to the point (x+(n-2)v)/(n-1)).

4. Repeat.

Notice that if n was 3, we get the recipe for the Sierpinski triangle (aka carpet, aka gasket) from yesterday.  Also, if n is 2, then you get a single point (which, ok, is a fractal in that it is self similar, but sort of sucks).  I haven’t checked, but it looks like the Hausdorff dimension of the fractal produced starting with n vertices is something like ln(n)/ln(n-1).  More on calculating that later.

Anyways, here is the MATLAB code for creating these fractals, and pictures of a few of them.


function gasketn(rad,n,d,sides)
%creates a fractal with radius rad, n points, each point of size d, and
%"sides" sides. gasketn(1,100000,1,3) creates a Sierpinski gasket.
t = linspace(0,2*pi,sides+1);
x = [rad*cos(t),rad];
y = [rad*sin(t),0];
point = zeros(n,2);
vert = randi(sides,n,1);

for j = 2:n
point(j,:) = point(j-1,:)/(sides-1) + (sides-2)*[x(vert(j)),y(vert(j))]/(sides-1);
end
scatter(point(:,1),point(:,2),d,'k','filled')
axis off
end

Starting with five vertices.

 

Six vertices!

 

Twelve vertices! And now this is getting silly...