Sierpinski Curves

Author: Eric Gossett

Abstract

This article has been written as a supplement for a discrete mathematics course. It introduces a family of recursively defined curves called Sierpinski Curves. The article briefly discusses the Sierpinski Curve as an example of a space-filling curve, then focuses on the elegant but non-trivial recursive implementation. Finally, several combinatorial aspects of the recursive implementation are examined.

The reader is assumed to have seen discussions about recursion, recursive functions, and recurrence relations in a standard discrete mathematics text.

This document works best if you make your browser fairly wide.

Table of Contents

• Abstract
• 1. Space-Filling Curves
• 2. Recursive Functions
• 3. The Sierpinski Curve
• 4. Combinatorial Aspects
• 5. Combinatorial Explosion
• 6. Footnotes
• 7. References

1. Space-Filling Curves

During the late 1800's, Georg Cantor was attempting to find an infinite set that was larger than the open interval (0,1) on the real line.[Dunham] The obvious set to look at was the open unit square, having corners at the points (0,0), (0,1), (1,1), and (1,0) in the plane. After extensive effort trying to show that the unit square was indeed larger than the unit interval, Cantor started to suspect that they might be the same size! He eventually proved that they were indeed the same size.

Other mathematicians were able to provide a very elegant kind of proof of this counter-intuitive result. They constructed functions that map the points on the interval [0,1] to points in the closed unit square in such a manner that the function establishes a one-to-one correspondence. However, such functions must be discontinuous [Sagan, chapter 1]. It is possible to construct continuous functions that map the interval [0,1] onto the unit square. (There will be points in the unit square that are mapped onto by multiple points in the unit interval.) Such functions are called space-filling curves. Space-filling curves can be more formally defined by requiring the image of the function to have a non-zero area. See [Sagan, chapter 1] for more details.

One very attractive space-filling curve is the Sierpinski Curve. The curve defined by Waclaw Sierpinski is actually the limit of a sequence of curves. The curves will be defined in more detail in the next section. For now, it is sufficient to consider the first few members of the sequence.

The curves will be labeled S0, S1, S2, S3, S4, S5, ...

Consider the curve S0. We can think of the diamond shape of the curve as depicting a function that successively maps the subintervals [0, .25], [.25, .5], [.5, .75], and [.75, 1] onto the points in the plane that lie on the line segments joining (.5,1) to (1,.5), (1,.5) to (.5,0), (.5,0) to (0,.5), and (0,.5) to (.5,1) in the unit square.

Similarly, we can view S1 as the image of a function that maps [0,1], subdivided into 20 equal length intervals, onto the 20 line segments that constitute the curve S1. (Notice that the horizontal and vertical line segments in S1 are double length and hence count as two segments each.)

As can be seen from S5, the curves in the sequence are sets that are the same size as the interval [0,1] on the real line. In addition, each curve in the sequence contains more of the points in the unit square than do the previous curves. Also, none of the curves cross themselves. It can be shown that as n approaches infinity, Sn uses more and more of the points in the unit square. The limit S of the sequence uses all the points and establishes a one-to-one correspondence between the interval [0,1] and the unit square. The graph of the curve would appear to be a solid black square in the plane, but the function would match each point in [0,1] with exactly one point in the square.

2. Recursive Functions

A recursive function is a function that is defined in terms of itself. For example, the factorial function

f(n) = n!

can be defined by the statements:

f(0) = 1
f(n) = n f(n - 1) for n > 0

Notice that a recursively defined function must have one or more base cases for which the function is defined directly. In the example above, the base case is n = 0.

Usually, recursively defined functions are more efficiently defined in a more direct manner. There are some functions, however, for which a recursive definition is more natural, easier to produce, or more elegant. These issues may cause efficiency to become a secondary issue, at least initially.

The sequence Sn, whose limit is the Sierpinski Curve, can be simply and elegantly defined in terms of four mutually recursive sequences of accessory functions. The accessory sequences will be labeled An, Bn, Cn, and Dn.

The accessory sequences are mutually recursive because, for example, the definition of An depends upon An-1, Bn-1, and Dn-1. The basic recursion to be presented is from [Wirth].

3. The Sierpinski Curve

Schematic diagrams for each sequence of curves are presented below. Each curve is made using line segments of a standard length. The length of the line segments is determined by the value of n for the final curve shown. As n gets larger, the length decreases so that the entire figure will fit inside the unit square. For example, compare the difference in line segment lengths for S0 and S2.

The schematic diagrams contain small arrows. Each arrow represents a line segment (having the standard length) in the direction of the arrow. Some diagrams have two adjacent arrows, indicating the need to draw two line segments in the same direction, creating the double length line segments mentioned earlier.

The schematics also contain symbols for various members of the sequences of curves Sn, An, Bn, Cn, and Dn. This indicates the need to (recursively) draw that curve. The curves A0, B0, C0, and D0 are all defined to be empty (do nothing).

The Schematic Diagrams

Notice that in the base case (n = 0), the only non-empty contributions are from the line segments represented by the arrows.

A0 is empty.

B0 is empty.

C0 is empty.

D0 is empty.

A detailed look at S1

S1 is formed by drawing A1 then a line segment going down and to the right, then drawing B1 followed by a line segment going down and to the left. Next comes a copy of C1 and a line segment going up and to the left followed by D1 and a final line segment going up and to the right.

According to the schematic, S1 is formed by drawing A1 then a line segment goinA1 is formed by drawing A0 (do nothing) then a line segment going down and to the right, followed by B0 (again, do nothing) followed by two line segments going to the right. Next draw D0 (nothing) followed by a line segment going up and to the right and then a final copy of A0.

According to the schematic, S1 is formed by drawing A1 then a line segment goinThe sub-figures B1, C1, and D1 are formed in a similar fashion.

According to the schematic, S1 is formed by drawing A1 then a line segment goinWhen these components are assembled in the manner outlined above, the curve S1 results.

A semi-detailed look at S2

S2 is composed from A2, B2, C2, and D2, which are in turn assembled from A1, B1, C1, and D1. In all cases, the length of the standard line segment depends upon the value of n in the final figure (S2 in this case).

Self-Check

Check to make sure you understand how B3 is created. Then see if you understand how it fits into the construction of S3.

The pattern for S4 and S5 is similar. Hopefully you will see the general pattern as n gets larger and larger.

Additional examples can be explored by using the (776 KB) Mathematic 3.0 Notebook or the (750 KB) Mathematic 2.2 Notebook that accompanies this article. A static, HTML version, of the notebook is available if you do not have access to Mathematica, or you can download a free copy of a passive viewer for Mathematica notebooks called MathReader.

There is also a java implementation of the recursive algorithm written by David Biggar.

4. Combinatorial Aspects

There are several interesting counting problems associated with the Sierpinski Curve.

The Number of Line Segments

As a first example, we can use recursive functions to count the number of line segments in the curve Sn, for n > 0.

The schematic diagram indicates that Sn should have as many line segments as there are in the sub-curves An, Bn, Cn, and Dn, plus 4 more line segments for the arrow segments. It won't take long to convince yourself that the sub-curves each have the same number of line segments. Let the number of line segments in An be given by g(n), where the function g(n) is still undetermined. We do know that g(0) = 0. If we let the function f(n) represent the number of line segments in Sn, then:

f(n) = 4 g(n) + 4
f(0) = 4

Looking at the schematic diagram for An, it should now be clear that

g(n) = 4 g(n - 1) + 4
g(0) = 0

It is easy to recognize the equations above as a linear recurrence relation with constant coefficients. If it were a linear homogeneous recurrence relation with constant coefficients, it would be easily solved using standard techniques [Rosen].

For this recurrence relation, a series of substitutions will lead to a solution:

Since

it is easy to verify that

Since f(n) and g(n) follow the same basic recurrence relation, it is easy to see that g(n) = f(n - 1) for n > 0. The table below shows the value of f(n) for n between 0 and 5. Observe that the number of line segments increases by a factor that quickly gets very close to 4.

     n      f(n)
     -      ----
     
     0         4
     1        20
     2        84
     3       340
     4      1364
     5      5460

The length of a line segment

In order to keep the curves Sn inside the unit interval, the length of a line segment must decrease as n increases. The goal of this section is to determine the proper length of a line segment.

If you observe the top edge of one of the curves (S4 for example), you can see that there are two kinds of line segments that account for the distance along the top edge of the unit square: horizontal segments and segments that have a reference angle of (45 degrees) with the horizontal. If the length of a line segment is x, then the second variety of line segment contributes to the horizontal traversal. By counting the number, y, of horizontal segments and the number, z, of segments with a reference angle, then the horizontal distance will be .

A brief look at the curves S0, S1, S2, S3, S4, and S5 should lead to the following conjectures:

• there are diagonal line segments across the top
• in order to to fill in the remainder of the length along the top, horizontal line segments are needed.

These claims need a formal proof, which the reader should supply. For the moment, assume that the conjectures are correct. Then we have the equation

with solution as the required length of each line segment.

5. Combinatorial Explosion

The table below shows the number of line segments in Sn, together with the approximate increase over the number for the previous n.

     n      line segments      increase factor
     -      -------------      ---------------
     
     0             4
     1            20                5.0
     2            84                4.2
     3           340                4.0476
     4          1364                4.0118
     5          5460                4.0029
     6         21844                4.0081
     7         87380                4.0002

It is tempting to guess that Sn will take about 4 times as long to draw as will Sn-1. This would be true if the drawing algorithm was a non-recursive algorithm. If recursion is used (as has been done here), a different estimate may emerge if we take the recursion into account.

We need to count the number of recursive calls to the curves An, Bn, Cn, and Dn are made at all levels (down to n = 0). The reason we need to do this is that computer time is used for each recursive activation of another function and not only for the actual drawing of the line segment.

Let h(n) represent the total number of function activations needed to draw one of An, Bn, Cn, or Dn. Since the curves differ only in orientation and not in any significant algorithmic manner, we can concentrate on An. Since A0 is empty, there are no recursive function activations, so h(0) = 0. A1 has 4 activations, each to an empty function. However, the programming language will usually need to do some checking at this point, so we can assume that h(1) = 4. A2 makes 4 recursive activations of functions that require h(1) activations apiece. Thus h(2) = 4 h(1). A bit more thought indicates that in general

h(n) = 4 h(n - 1)
h(1) = 4

In this case, we are fortunate because h(n) is a linear homogeneous recurrence relation with constant coefficients. The standard techniques [Rosen] work. In fact, the solution is easily seen to be h(n) = 4^n. The number of recursive activations needed to draw Sn is 4 times this value.

Drawing Sn requires 4^(n+1) recursive function activations, exhibiting exponential growth.

The table below shows the number of recursive activations needed to draw Sn, for n between 0 and 7.

     n      Activations     Line Segments
     -      -----------     -------------
     
     0		     0              4
     1              16             20
     2              64             84
     3             256            340
     4            1024           1364
     5            4096		 5460
     6		 16384          21844
     7	         65536		87380

Notice that the number of activations increase by a factor of 4 each time (exactly). A function activation will take more time than drawing a line segment will. However, both the number of recursive function activations and the number of line segments drawn increase by a factor of 4 (approximately) as n increases. The table below shows sample times for drawing Sn using the Mathematica implementation that accompanies this article. Your times will vary depending on the speed of your processor and what other activities the processor is doing at the time of evaluation.

     n      Time (secs)        Tn/Tn-1
     -      -----------     -------------
     
     0		 1.9               
     1           2.4             1.3
     2           3.3             1.4
     3           8.0             2.4
     4          26.0             3.3
     5         105.0		 4.0
     6	       578.0             5.5

Since S6 took almost 10 minutes, we would predict S7 to take 40 - 60 minutes. The ratios don't appear to be what was predicted. The early ratios are not accurate estimates because Mathematica has a certain amount of overhead to perform a calculation and render the graphics, independent of the time taken to perform the actual recursions. For the larger values of n, another issue comes into play. Recursion requires computer memory since many partial calculations need to be stored while a lower level recursion is being activated. The computer I used to gather the times shown has lots of memory. However, for a large enough n memory will be used up. At that point, most modern computer systems will start using free hard-disk space as if it were memory. Unfortunately, writing to and reading from a hard-disk is much slower than writing to or reading from memory. It might therefore take much longer than the predicted 40 - 60 minutes to draw S7.