Space-filling curves

A curve is continuous function whose domain is an interval of the real numbers (often the unit interval ). A space-filling curve is a curve whose image completely fills a higher-dimensional space, like a hypercube (here we'll consider the unit square ).

Background

The unit interval and the unit square were proved to have the same cardinality by Cantor: let be a point in the unit square, and lets write and as Real numbers like and may not have a unique decimal expansion, but two: one of them ends in an infinite string of s. In this case we just choose the latter representation.

We can build an injective map to the unit interval by taking Note that this is not surjective, even though we are tempted to just reconstruct the two numbers from the decimal expansion: the preimage of is , but is not a valid expansion according to our rule. So we only have

But we can simply build , which is also injective, so we also have

Thus,

His reaction to this very counterintuitive result was: Je le vois, mais je ne le crois pas! (I see it, but I don't believe it!). ¹

Cantor did eventually find a bijective function, using continued fractions. It was later proved that such functions are necessarily discontinuous.

Space-filling curves

Peano, motivated by this result, presented a continuous, surjective map from the unit interval to the unit square, now called a space-filling curve.

This was (and still is, at least for me) very ground-breaking as well. We have a line, which we intuitively think as 1D, that completely fills a plane, which we think as 2D. This led mathematicians to rethink about the concept of dimension.

Anyway, the Peano curve is not injective, so the curve must intersect itself. These curves are generally defined as the limit of a sequence of iteratively constructed, piecewise linear, continuous curves.

Another construction of a space-filling curve was provided by Hilbert.

The production rules are the following:

Hilbert Curve Playground

Footnotes

1. https://en.wikipedia.org/wiki/Paradoxes_of_set_theory#Je_le_vois,_mais_je_ne_crois_pas ↩