Plane Filling Curves
Yes - there are curves that fill the plane without holes. However, I shall demonstrate this only for a square. Which is no less surprising. Also, it can be shown that any such curve must be self-intersecting.
To get a quick notion of what this page is about click on the applet on the right. Please be warned. Drawing the curve takes time. I could have done this in the background. But, personally, I more enjoy watching it being drawn than pondering over the final result.
The first such curve was discovered by Guiseppe Peano in 1890. The applet demonstrates two constructions: one by D.Hilbert (1862-1943), the other by E.H.Moore (1862-1932). Calling them Peano Monster Curves, B. Mandelbrot (Ref 1, p 58) collected a series of quotations in support of this terminology.
N.Ya.Vilenkin, 1965: Everything has come unstrung! It's difficult to put into words the effect that Peano's result had on the mathematical world. It seemed that everything was in ruins, that all the basic mathematical concepts had lost their meaning.
H.Hahn, 1956: [Peano curve] cannot possibly be grasped by intuition; it can only be understood by logical analysis.
J.Dieudonné, 1975: Some mathematical objects, like the Peano curve, are totally non-intuitive..., extravagant.
In light of Dieudonné's remark it is quite remarkable that Peano's original construction was entirely analytic - there were no drawing, let alone applets, to assist anybody's intuition.
Let me first describe how to generate the sequence of curves a few first members of which are displayed by the applet. Start with the basic staple-like shape as depicted on the first diagram. All the rest of the curves are created sequentially one from another using the same algorithm. Shrink the previous curve to half its size. Simultaneously, decrease the grid size by the factor of two. Place four copies of the curve on the grid. The lower two must be placed directly as they are. The upper two must be rotated a quarter turn - one left, another right. Lastly, connect the four pieces with short straight segments to obtain the next step curve. Sometimes the connecting segments are horizontal, sometimes they are vertical but, otherwise, the construction is straightforward.
The curves become longer and longer but, since it's always possible to move from one step to another, the process will never end. For this very reason none of the curves thus obtained ever fills the square your or my impression to the contrary notwithstanding. (Let me observe in passing that, by construction, none of the curves self-intersects.) What does fill the square is the limiting curve whose existence (or, for that matter, the definition) is not at all obvious.
We may want to redesign the algorithm somewhat. Let's call moving from the first picture to the second a basic step. Now, instead of shrinking the curve to half its size let's concentrate on 4 small squares that form our working square. Disregarding the pieces of the curve that cross small square borders we see (starting with the second stage) that those small squares contain small replicas of the curve drawn on the previous stage, i.e. the staple like shape from the first picture. Now, for every small square, divide it into four smaller squares and apply to each our basic step. What will result is depicted on the third picture. As before, when placing curves in the smaller squares two of the staples are placed in the direction of the bigger one they replace whereas one is turned left and another right quarter turn relative to the position of the parent staple. The algorithm is not convenient from the implementation point of view but is very helpful in proving existence of the limiting curve.
Thus we start with one curve
Consider the first fourth of our interval (currently it's
Ah, it takes longer than I thought it would, but inductively we obtain a sequence of functions
f0, f1, f2, ... each mapping the unit interval into the unit square.
For every point t the distance between its values fn and fn+1 does not exceed
the diagonal of the square obtained on the nth step - 2·1/2n
or 21/2-n. The important thing is that this inequality holds for every point
I can be more formal now. We have
|fn + m(t) - fn(t)| < |fn+1(t)-fn(t)| + ... + |fn + m(t) - fn + m - 1(t)|
Or applying the same inequality repeatedly
|fn+m(t) - fn(t)| < 21/2 - n + 21/2 - (n + 1) + ... + 21/2 - (n + m - 1)
Summing up the geometric series, we can transform this into
|fn + m(t) - fn(t)| < 21/2 - n(1 + 2-1 + ... + 2 - (m - 1)) < 23/2 - n
This means that for every t∈[0,1] we have a Cauchy sequence f0(t), f1(t), ... The plane is known to be a complete space implying that the sequence converges to a point in the unit square which I denote f(t). This convergence is uniform since the above inequality holds simultaneously for all t∈[0,1]. By a known result from Analysis (Ref 4) a sequence of continuous function that converges uniformly converges to a continuous function. Therefore, the limiting function f(t) is continuous, i.e. a curve.
The least we can say about the curve is that, by construction, it passes arbitrarily close to any
point in the square. Thus for any point
The manner of construction of function f is exactly that in which we visualize the many fractal curves: as a limit of uniformly convergent continuous functions. It is important to realize that the fractal is the limit of a sequence of curves and none of the curves in the sequence.
For the Hilbert curve, even B. Mandelbrot, has reservations about the fractal designation for this curve. The property of filling the plane makes its Hausdorff dimension 2 an integer, not fractal. However, it is no less, if not more, a curiosity than fractal curves.
- M. Gardner, Penrose Tiles to Trapdoor Ciphers, W. H. Freeman and Co., NY, 1989.
- B. R. Gelbaum and J. M. H. Olmsted, Counterexamples in Analysis, Holden Day, 1964
- B. Mandelbrot, The Fractal Geometry of Nature, W. H. Freeman and Co., NY, 1982.
- L. Schwartz, Analyse Mathematique, I, Hermann, 1967
- The Peano Curve and Fractal Curves
- Giuseppe Peano
Plane Filling Curves
- Plane Filling Curves
- Plane Filling Curves: Hilbert's and Moore's
- Plane Filling Curves: Peano's and Wunderlich's
- Plane Filling Curves: all possible Peano curve
- Plane Filling Curves: the Lebesgue Curve
- Following the Hilbert Curve
- Plane Filling Curves: One of Sierpinski's Curves