In the realm of fractals there is an algorithm sometimes called the chaos game1,2 that is a somewhat surprising way to produce the image above. The figure above is the familiar Sierpinski gasket and the "game" that generates it is really not a game, but rather a very simple algorithm. Start with an equilateral triangle and pick a point, any point, inside it or not. Next pick one of the vertices of the triangle at random. The at random part is important. Make a mark halfway from the initial point to the chosen vertex. Now treat this mark like the initial point: pick a vertex at random and make a new mark halfway from the first mark to the new vertex. Repeat this many times and voilà: you get the image above of the classic Sierpinski gasket.
This is pretty cool when you first see it. There are several ways to generate the Sierpinski gasket but a way that involves half way hopping to randomly chosen corners of a triangle is perhaps a little hard to understand at first.
Probably because of its surprising nature this so-called game has been written about a fair amount, both in books and on the web. Typically, after demonstrating the result of the "half way" algorithm, the authors show the mess of points that occurs if you play around just a bit with the algorithm. For example, you can change the hop, or cut fraction, to a value other than 0.5, or try starting with a different polygon instead of a triangle, or both. Generally this results in a fuzzy blob with varying hints of structure. In the case of the square with the cut fraction still at one half you get a completely filled in square with no apparent fractal structure.
At this point most discussions of the chaos game either end or segue into generalizations of the algorithm that generate beautiful figures resembling organic structures such as fern leaves. These algorithms collectively are called iterated function systems (IFS) and they are very interesting and useful for computer generation of images, among other things.
But the question that interested me when I first encountered the chaos game was the narrower generalization from triangle to any regular polygon, on which everything I read was silent. Since I couldn't resist trying to figure it out for myself, this page is an account of my own process of solving this problem.
In addition to the lack of a generalization to other polygons, the particular value of 0.5 as the triangle cut fraction never seemed to get explained geometrically. And when the fuzzy blobs are presented for other polygons the obvious question seems to be: is it possible that a different value of the cut fraction would give a crisp fractal? In particular, is there a formula based only on the order of the polygon that would yield the cut fraction as a function of the polygon's order? I assumed there was and I wanted to find that formula and understand the cut fraction from a geometric perspective, not just an algorithmic one.
If you experiment with such a program enough you'll find that, except for the square (more on that later), there is always a unique value of the cutting fraction kn for each regular polygon that gives rise to a sharp fractal structure with the symmetry of that polygon, as seen below for the pentagon and hexagon.
One of the first surprises while I played was that another sharp fractal for the equilateral triangle can be generated by using a cutting fraction of 1.5 instead of 0.5. The value 1.5 generates a wispy snowflake-like fractal that is like a strange inverse of the Sierpinski gasket. It turns out there are always two such cut fractions for any regular polygon and they are very simply related.
I call the proper cut fraction for an n sided regular polygon the "kissing" number, or kn. We have already seen that for n = 3, kn = 0.5. It turns out that the other cut fraction is always just 2 - kn. I'll call these the interior and exterior kissing numbers, or kn and kn'.
Although I stumbled across the secondary kissing numbers from just playing around, what I really wanted to find was a formula that would give the correct kissing numbers for any regular polygon from just the number of sides. It turns out the kissing number has a very simple and beautiful geometric meaning. And that meaning will make obvious the reason for calling it the kissing number in the first place. The general formula for the interior kissing number for an n-sided polygon is:
where α = π/n, β = 2α (vk - 0.5), vk = ceiling(n/4) and γ = β - π/2. This formula gives the proper cut fraction for making a fractal gasket from any regular polygon using the chaos game algorithm. The derivation of this formula is shown in the sidebar at the right. Because I'm a very visual thinker, I also explore the geometric meaning of the kissing numbers in a more directly visual way in the next section.
If you're going to follow this discussion further I suggest you play along using the demonstration app. The easiest way to do that is to open the link in another browser window (not a tab) so you can have the demonstration app and this explanation visible simultaneously.
Sticking with the n = 3 case for the moment, if you gradually ramp the cutting fraction from 0 to 2 you will see a progression from fuzzy blobs to crisp fractals at the two values 0.5 and 1.5. If you do the same for n = 5 you will see a similar thing but at cutting fractions of 0.618 and 1.382. You can see that at the first cutting fraction that works in the sense of sharpness, there are n children of the parent polygon and that each of these first generation child polygons share two vertices, one with each of their neighbors.
You can also think of these subpolygons as having arisen as a result of n exact copies of the parent polygon, with each child uniquely anchored at one parent vertex, all uniformly shrinking until they no longer overlap but instead just kiss their two neighbor's shared vertices. Or think of each parent vertex spawning a child polygon that grows until it just touches its two neighbors.
It turns out the kissing number is the ratio of the radius of the circle that passes through the centers of the kissing subpolygons - the first level children - to the radius of a circle that circumscribes the parent polygon. This ratio of the centroid circle to the circle circumscribing the parent is the value that determines how far to hop towards a randomly chosen vertex if you want to generate a crisp fractal figure.
When the cut fraction is different from kn or kn' the marked locations can and frequently will fall outside the kissing subpolygons (at whatever level) even though they are still respecting the n-fold symmetry of the parent. The overlap seen at the highest level of the subpolygons is of course present fractally in the fuzzy cloud. Away from either kissing number the fractal nature gets smeared out by this overlapping. This is illustrated below.
The derivation of the general kissing number formula is shown in the sidebar. Although there's nothing better than a general formula, there is a purely graphical way to understand the interior kissing number values. It has to do with how the edges of the first level subpolygons line up along any edge of the parent polygon. Each parent edge will contain one edge from each of two first level child polygons. There may or may not be a gap between the two child edges. For both the triangle and square there is no gap. For all other polygons there is always a gap. The image below illustrates how the interior kissing number is related to this situation.
If you think about each mark that is placed, you realize each one has a history of which vertices were targeted that eventually led to it. In the image below, the marks are colored according to their vertex targeting history. On the left, the coloring is based on the very last vertex targeted before marking, corresponding to a targeting history depth, h, of 1. In the center we color based on the vertex two steps before marking and on the right four steps before marking. Each vertex has an implied unique color and we color the mark based on that and the history depth we are displaying.
The coloring is certainly convenient for seeing the history but it's not necessary. It's really all about location. A mark's exact location within the figure tells the history of vertex targeting that preceded its placement. So in the center image, all the marks in the circled green sub-triangle have a final history of GR (i.e., the final vertex targeted was R, and just before that it was vertex G) while all marks in the circled sub-triangle on the right have a final history of BBGR. You can literally read the history from the location. Pretty cool.
Now on to the mystery of the square. The apparent lack of structure in the square version of the chaos game is something only coloring history can dispel. The kissing number formula gives kn = 0.5, just like for the triangle. If we move away from 0.5 for the square we suddenly see some structure but this is really the equivalent of the "blurring" we see with other polygons when we are off kn. You can see this for yourself on the chaos game demo page by setting the order to 4 and the cut fraction to something slightly off 0.5.
In the image above we finally see the self-similar structure of the square case via the history. We see that there is a squares-within-squares geometry all the way down, but no open space, which really isn't surprising since dividing the parent square's sides in half leaves no open space, unlike the case for any other polygon. Another way of thinking about the square is that first level child squares (h = 1) kiss on edges rather than vertices, and all non-perimeter edges are kissing. That's the only reason there's no apparent structure without history coloring.
It's also instructive to use history to see the way structure gets fuzzed out by going off the kissing numbers for a polygon. We can see that the structure is still there but is either going ever more out of focus or shrinking away.
Finally, it turns out there is a kind of liar's paradox going on with the algorithm that makes the figures. They really are very strange, almost spooky in a way, and here's why.
First think of making such figures in another way. Consider a triangle of black paper. Make an interior triangle from the midpoints of each edge and remove it. Repeat with the three smaller child triangles. You are heading directly towards the same figure, to all appearances.
Our way here is very different. To repeat, it doesn't matter where you pick the first point. It can be inside the parent or even very far outside it. The algorithm ensures it will come into the parent very quickly and from there on you might as well have started inside. So let's just say we start at (0,0) and let's say the parent figure is the triangle. The figure below shows what happens.
In addition to the marks all being in white space, the most important thing to notice is that there is only one point placed for each size of white space triangle and this happens in descending size order. That is, each mark ends up in a next smaller white space triangle compared to the previous mark. The figure is self-similar all the way down and that's true for whatever order of polygonal fractal gasket, so in principal there are always ever-smaller white space bits to land in. As with any order, the child white space triangles are getting smaller exponentially fast.
In this particular case we have 1/4 to the power of the number of steps, which is fantastically fast shrinking. This means that every visible white space triangle is actually being outlined by the marks falling in ever tinier white space triangles - the number of which grow by a factor of 3 at each level. The white space almost instantly becomes finer than the display medium could ever show or the human eye could ever see. But if we did zoom way in on the millionth mark placed, it too would be in the middle of a white triangle. I think the word trippy definitely applies.
I wanted to explore the chaos game from a bit of a different angle than most other treatments. I believe experimenting via code is one of the best ways to explore topics like this. The demonstration app page is an extremely simplified version of the software I used to play with these ideas, but it is sufficient to get a good feel for what's going on in the regular polygon chaos game.
1. Barnsley, Michael. Fractals Everywhere. 1993.
2. Peitgen, Heinz-Otto, & Saupe, Dietmar, eds., The Science of Fractal Images. 1988.