Introduction to Space-filling Curves

In mathematics, one often encounters curves, often as graphs of functions. In the two-dimensional case, these graphs often come about when a dependent variable y has some relationship with an independent variable x, e.g. the parabola y = x².



The graph of the function y = x² is a pictorial representation of this specific relationship between y and x.

Alternatively, we may encounter some more complicated graphs when we allow both x and y to be dependent variables of another variable t, called a parameter. For example, consider the parametric function defined by the two equations y = t² and
x = t, where we specify that the independent variable t can take any real number value. To graph this function on an xy-plane like before, we find the ordered pair (x,y) for each value of t and graph these points.

The perceptive reader will have noted that, through a simple substitution, the two equations of the parametric function above can be combined into the simple relation
y = x², the same parabola as before. Thus the graph of our parametric function is precisely the same as that of our original function, and they represent the same curve in the xy-plane. We say that the parabola is parametrized by y = t², x = t, -∞ < t < +∞, where the inequality specifies the domain of t.

However, though some parametric functions can be easily expressed simply with x and y alone, others do not create a simple, or even single-valued, dependence. Consider the more complicated parametric function y = 3cos(3t) + t, x = sin(t), and its graph in the xy-plane, below (for convenience, t is restricted to the domain -2π/3 < t < 2π on the graph below):



In such a function, substituting to obtain a relation directly between y and x would be much more complicated, and could not be a function of the form y = f(x) anyway as some values of x correspond to multiple values of y. Such curves can also intersect themselves many times, as the one above demonstrates.

Yet another way to look at a parametric function is as a mapping from 1-dimensional space (the "number line" of t) to 2-dimensional space (the xy-plane). In fact, we shall define the term curve as the range in 2-dimensional Euclidean space of such a mapping. We also specify that this mapping must be continuous, i.e. that the graph of the curve does not have any "jumps".

From now on we shall consider only mappings of the unit interval, therefore setting 0 ≤ t ≤ 1. The intuitive idea of the range, or image, of this type of curve in the xy-plane is that it is very "narrow", and does not have any area. For example, for any rectangle in the plane, one can easily measure area, but the area of just one of the sides is zero, or for that matter, the area of all four sides (for more about areas, see here). Only the region contained by the four sides has positive area.

However, in 1890, the Italian mathematician Giuseppe Peano made a remarkable discovery. There is a curve whose domain is the unit interval and whose image (graph) fills the entire unit square! (in the xy-plane, this is defined as the region such that both 0 ≤ x ≤ 1 and 0 ≤ y ≤ 1 are satisfied) In other words, a single line can take up a square, even one mapped from a finite interval.

It is crucial to note the significance of the fact that the mapping is continuous, i.e. produces a curve that fills the unit square. It is relatively "easy" to create a mapping from the unit interval to the unit square without this restriction. One way is through use of a number's decimal expansion (in base 10 notation).

Any number in the unit interval can be written in the form 0.a₁a₂a₃..., where we use 0.999... to obtain 1. Consider the function f defined on the unit interval, that "splits" the decimal expansion into two parts and makes each of these a coordinate of a point in the unit square, with

f(0.a₁a₂a₃a₄a₅a₆...) = (0.a₁a₃a₅,0.a₂a₄a₆...).

To ensure that this function is well-defined, we must "make up our minds" what decimal expansion to use to represent numbers such as 1/2, which equals both 0.5000... and 0.4999.... To remedy this, simply chose as the input of the function the terminating (where terminating means that for some N, n > N implies a_n = 0; for the terminating decimal expansion of 1/2, set N ≡ 1) expansion. Thus f(1/2) ≡ f(0.5000...) and not f(0.4999...). The diagram below indicates graphically the domain and range of the mapping, along with its effect on a selected point.



The function f defined on the unit interval in t-space has as its range the entire unit square in the xy-plane. To see that the entire square is filled, let (0.a₁a₂a₃...,0.b₁b₂b₃...) be a point of the unit square. Then it is easily seen that 0.a₁b₁a₂b₂a₃b₃... maps to this point under f. Since every point in the unit square can be expressed this way, the mapping fills it in its entirety, confirming that the unit interval has "just as many" points as the unit square.

But is the mapping above continuous? It turns out that it is not. For a proof of this fact, and an example of a space-filling curve (where continuity is required), see the next post.

Sources: Counterexamples in Analysis by Bernard R. Gelbaum and John M. H. Olmsted, Space-filling Curve on Wikipedia