The Sierpinski triangle is a fascinating mathematical structure that exhibits a property known as self-similarity. It begins with a simple equilateral triangle. Within this triangle, a smaller, inverted triangle is removed from the center, leaving behind three smaller triangles arranged in a triangular pattern. Each of these smaller triangles then undergoes the same process recursively.

The process to construct the Sierpinski triangle can be visualized step by step. First, you start by drawing a large equilateral triangle. Next, you identify the center of this triangle and remove a smaller, inverted triangle of exactly half the scale. This action results in three smaller equilateral triangles surrounding the removed space. The process is repeated for each of the three remaining triangles. At each iteration, a smaller inverted triangle is removed from the center of every triangle left in the structure. This process continues infinitely, generating a complex pattern with an increasing number of smaller triangles.

The result of this iterative process is the Sierpinski triangle, a fractal that contains infinitely many self-similar triangles, meaning that any part of the structure looks like the whole when magnified. The fractal's recursive nature demonstrates the concept of infinite detail and is a classic example of how simple rules can create complex patterns. This structure has applications in various fields, including computer science, art, and nature, due to its visual appeal and mathematical properties.

• How do you build the triangle by cutting ?
• How does the chaos game draw the same triangle ?
• What happens when the vertices change ?
• How big is the Sierpinski triangle ?

How do you build the triangle by cutting ?

Let's start with the construction you can do by hand, because every later section refers back to it. The rule has only one step, and you apply that step again and again. What makes the result interesting is the repetition, not the step itself.

Don't worry if you don't understand this explanation. It is hard to explain this only in words. Let me try to explain this in step by step illustration.

Simpliy put, if you iterate the following steps over and over with a triangular paper and scissors, you would have the shape as shown in the plot at the end of this page.

Figure 1. Construction by cutting. Each step removes the middle quarter of every triangle, so one triangle becomes three half-size copies of itself.

• Step 1 starts from one filled triangle : the whole area is shaded, and nothing has been removed yet.
• Step 2 removes the middle triangle : its corners are the midpoints of the three edges. It is upside down, and its sides are half as long as the original sides.
• Three half-size triangles remain : the blue outlines in Step 2 mark them. Each one has the same shape as the triangle of Step 1.
• Step 3 applies the same cut to each copy : three small holes appear, one in each copy, next to the large hole from Step 2.

You can count what is left after each step. One step turns every triangle into three triangles with half the side length. So after n steps you have 3ⁿ triangles, each with a side of 1/2ⁿ of the original side. The middle triangle always has one quarter of the area of its parent. The remaining area is therefore (3/4)ⁿ of the original area. After 10 steps, 59049 small triangles remain, and together they cover only about 5.6% of the starting area.

• One rule, repeated : the whole construction is one cut, applied to every triangle that is still there.
• The count grows as 3ⁿ : each step triples the number of triangles and halves their size.
• The area shrinks as (3/4)ⁿ : every step removes one quarter of what was left, so the filled area goes to zero as n grows.

How does the chaos game draw the same triangle ?

Cutting paper is slow, and a computer does not need to cut anything. It only needs a rule that produces points on the triangle. The rule below is called the chaos game. It uses random choices, yet the picture it draws is always the same.

Instead of using paper and scissors, you can draw the same shape in mathematical way as illustrated below. If you iterate the following steps over and over, and mark all the position that you have gone through, you will get the shape shown at the end of the page.

Figure 2. One round of the chaos game. The point picks a random vertex and moves half of the way towards it, then repeats from the new position.

• Steps 1 to 3 make one move : the initial point is picked, the vertex v1 is picked at random, and the point moves to the midpoint between the two.
• Steps 4 to 6 make the next move : the moved point becomes the current position, v0 is picked this time, and the point moves half of the way towards v0.
• The old positions are kept : the black dot in Steps 4 to 6 is the earlier position. Marking every position that the point visits is what builds the picture.

Why do the random moves draw the triangle of Figure 1 ? Each move is a map f_i(p) = (p + v_i)/2. This map shrinks the whole plane by one half towards the vertex v_i. If you apply f_i to the whole Sierpinski triangle S, you get the half-size copy of S at the corner v_i. The three copies together make up S again, which is exactly the picture of Step 2 in Figure 1. So a point on S always stays on S, whichever vertex is picked.

A point that starts off S also comes to S quickly. Each move halves the distance between the point and the triangle. After 10 moves, the distance is less than 1/1000 of the starting distance, which is smaller than one pixel of the plot. After that, the random choices only decide which part of S the point visits next. Over many moves, the point visits every part, and the marked positions fill in the fractal.

This is the image (a fractal shape) that can be obtained from the iteration of the procedure illustrated above.

Figure 3. Output of the chaos game with 20000 moves. The points fill the same pattern of holes that the cutting construction of Figure 1 produces.

Following is the Octave/Matlab code that implements the procedure explained above and produce the above image.

v = [0,0;0.5,0.7;1,0];

Nv = 20000;

x1 = 0.0;

y1 = 0.5;

 

vList = [x1,y1];

 

for i = 1:Nv

    vidx = randi([1 3]);

    vsel = v(vidx,:);

    x2 = vsel(1);

    y2 = vsel(2);

    x = (x2+x1)/2.0;

    y = (y2+y1)/2.0;

    vList = [vList;x y];

    x1 = x;

    y1 = y;

end;

 

plot(vList(:,1),vList(:,2),'bo','MarkerSize',1);

Let's read the code line by line against Figure 2. The matrix v holds the three vertices, one row per vertex. Row 1 is (0,0) at the bottom left, row 2 is (0.5,0.7) at the top, and row 3 is (1,0) at the bottom right. So row 1 plays the role of v1 in Figure 2, and row 2 plays the role of v0. In the loop, randi([1 3]) picks a row at random. The next two lines then take the midpoint between the current point (x1,y1) and that vertex. Every new point is appended to vList, and the plot command draws all 20001 points as small circles.

This triangle is not equilateral. The base is 1, the two slanted sides are about 0.86, and an equilateral triangle with a base of 1 would have a height of about 0.866 instead of 0.7. The chaos game does not need an equilateral triangle, as the next section shows.

The code also starts from (x1,y1) = (0.0, 0.5). This point lies outside the triangle, because the left edge passes x = 0.357 at the height y = 0.5. The start point itself is in vList too, so it is plotted. The first few moves therefore land away from the fractal. For example, two moves towards row 1 at (0,0) give (0, 0.25) and then (0, 0.125). Figure 3 shows two isolated dots on the left axis at about these heights, and two more inside the holes near x = 0.5. After roughly ten moves, the points stay on the fractal. A common fix is to drop the first 10 to 20 points before plotting.

• Each move is a half-size map towards one vertex : f_i(p) = (p + v_i)/2, and the three maps together rebuild the triangle from its three copies.
• The start point does not matter : the distance to the fractal halves on every move, so only the first few points can land off the pattern.
• The random choice decides the order, not the shape : a different random sequence visits the parts of S in a different order and draws the same picture.
• Stray early points are expected : the code starts outside the triangle, and a few of its first points show up as isolated dots in Figure 3.

What happens when the vertices change ?

Nothing in the chaos game uses the angles or the side lengths of the triangle. The rule only takes midpoints between the current point and a vertex. So we can move the vertices anywhere, as long as they do not lie on one line, and ask what the new picture looks like.

If you change the shape of the first triable by changing the vertices of the triangle and repeat the same procedure explained above, you would get the fractal image as shown below.

Figure 4. Chaos game on two other triangles. A scalene triangle and a right triangle both give the same fractal, stretched and sheared to fit the new vertices.

In the left plot, the top vertex sits to the right of the middle, so the triangle has three different sides. In the right plot, the triangle has a right angle at the bottom left. Both plots still show one large hole, three medium holes and so on. Each hole is again the triangle whose corners are the midpoints of the edges around it.

The reason is that midpoints survive any affine map. An affine map A(p) = Mp + b stretches, shears, rotates and shifts the plane, and it can take any triangle to any other triangle. For such a map, A((p + v)/2) = (A(p) + A(v))/2. So running the chaos game on the vertices A(v_i) gives exactly the points A(p) of the original game. The new picture is the old Sierpinski triangle, drawn through the map A.

• Any three non-collinear vertices work : the chaos game only takes midpoints, so it needs no special shape.
• All triangles give the same fractal up to an affine map : the holes stretch and shear with the triangle, and their pattern stays the same.
• The quarter-area rule still holds : the midpoint triangle always has one quarter of the parent area, so the (3/4)ⁿ rule of Figure 1 holds for every shape.

How big is the Sierpinski triangle ?

The cutting count gave a strange result: the area goes to zero, yet the pattern keeps every edge of every triangle it ever had. So the Sierpinski triangle is more than a curve and less than a filled area. A fractal dimension puts a number on that in-between size.

Let's compare three shapes that each split into copies at half scale. A line segment splits into 2 copies of half length, and 2 = 2¹. A filled triangle splits into 4 copies of half size, and 4 = 2². In each case, the exponent is the ordinary dimension. The Sierpinski triangle keeps only 3 of the 4 copies. So its dimension D satisfies 3 = 2^D, which gives D = log 3 / log 2 = 1.585.

You can check this number with the chaos game output. Cover the plot with a grid of square boxes and count the boxes that hold at least one point. When the box size halves, a filled area would need 4 times as many boxes, and a line would need 2 times as many. For the Sierpinski triangle the count grows about 3 times, because each box that holds part of the pattern splits into 3 boxes that still hold part of it. A count of 400000 chaos game points gives this ratio of about 3 at every step from 8 x 8 to 256 x 256 boxes.

The boundary tells the same story from the other side. After n steps, the 3ⁿ triangles each have 1/2ⁿ of the original perimeter. So the total edge length grows as (3/2)ⁿ and has no limit, while the area goes to zero. The Sierpinski triangle also appears in Pascal's triangle. If you mark the odd entries of the first 2ⁿ rows, the marks form the Sierpinski pattern after n cutting steps.

• The dimension is log 3 / log 2 : three copies at half scale give D = 1.585, between a line and an area.
• Area goes to zero and edge length has no limit : (3/4)ⁿ and (3/2)ⁿ are two views of the same in-between size.
• Box counting checks the number : halving the box size multiplies the count of occupied boxes by about 3 for chaos game output.
• The dimension does not depend on the triangle shape : an affine map keeps the three-copies-at-half-scale structure, so Figure 4 has the same D.