What can you do with this space?

Nobody could draw a space filling curve by hand, but that doesn’t stop Andrew Stacey

post

A few years back, the students and staff at my school were set an art challenge over the summer break. Those who chose to take part were given a blank postcard and asked the question: What can you do with this space?

I feel that the obvious answer to this question is ‘fill it’. But in mathematics, the combination of the words space and fill links to a very specific concept: space-filling curves. In this article, I’m going to explain what these are, and how this leads to my entry (shown above).

Space-filling curves

A detail of my postcard.

There are many variations on the theme of space-filling curves, but the original and simplest version is a continuous curve that passes through every point in the unit square. Formally, it is a continuous surjective function $\gamma \colon [0,1] \to [0,1]^2$. Note that it only needs to be continuous and doesn’t have to be differentiable, so sharp corners are allowed.

The first space-filling curve was designed by Peano in 1890. Surprisingly, his paper has no pictures. A year later, based on Peano’s work, Hilbert came up with a slightly different construction and included pictures. Hilbert curves seem to be the more popular of the two, with about 20 times more search hits on the internet. You might conclude that pictures are important in mathematics; I couldn’t possibly comment.

The reason why Peano and Hilbert (and others) were interested in these curves was because of Cantor. Not long before Peano published his paper, Cantor had started on his exploration of infinity and established that the unit interval and the unit square had the same quantity of points (this is what caused Cantor’s famous utterance “I see it, but I don’t believe it.”). This meant that there was a function from the unit interval to the unit square that hit every single point. Cantor constructed such a function using continued fractions to represent real numbers, but his function was discontinuous. It was established that there couldn’t be a continuous bijection between the unit interval and unit square, but the question remained as to whether it was possible to create a surjective function that was continuous. That is, a function that visits every point in the unit square but possibly more than once. Peano’s paper answers this with a definitive ‘yes’.

Interestingly, Peano notes that his function is not differentiable. It would later be shown that no such differentiable function could exist.

My interpretation of what Peano and Hilbert were doing is that they were experimenting with mathematics. Cantor’s ideas were spreading and they wanted to understand them better. To do so, they made examples testing the ideas, pushing them to their limits to see if they would break.

Peano curves

Of the several variants out there, I’m going to focus on Peano curves. I’ll explain why once I’ve shown what they are. A space-filling curve is actually very easy to draw (see right) it is defining them that takes a little more work.

The first two iterations of the Peano curve

The modern way to construct a space-filling curve is as a limit of a family of curves that are more straightforward to define. This is not how Peano originally constructed his curve, which was defined by giving a formula based on a way of writing numbers using a base 3 variant of decimals. It is more akin to how Hilbert constructed his curve. The construction of Peano’s curve that I know best starts by dividing the unit square into 9 smaller squares and joining their centres in a specific order, as I’ve illustrated to the right (left panel).

The second iteration splits each of the 9 squares into 9 smaller squares and repeats the pattern in each smaller grid, with some rotations and reflections so that they join up. There are some options as to how to choose the rotations. The one I’ve used is shown next to the first iteration. This process can be repeated and the Peano curve is what you get by doing this infinitely many times. Formally, it is the limit of this family.

The first two iterations of the Hilbert curve

The Hilbert curve is constructed in a similar fashion except that the unit square is divided initially into 4 smaller squares, which are then each further divided into 4 and so on. The first two iterations are shown on the right. I suspect that the real reason Hilbert curves are more well-known is because of the superiority of this division-by-two strategy and not due to Hilbert drawing pictures.

So to fill the postcard with a space-filling curve, I could either colour in the whole postcard to show the final curve or show one of the stages. Neither of these felt like a good entry for an art project. For one, they were both a bit simplistic, and for two, it wouldn’t be obvious what was happening to someone who didn’t already know.

So I wanted to make my design more interesting and somewhat self-explanatory while remaining true to the idea of a space-filling curve.

From space-filling to postcard-filling

Henry Segerman’s 3D printed developing Hilbert curves. You an download the files needed to print your own here. Image: Henry Segerman @henryseg segerman.org.

Ideas rarely come from nothing. I had seen the travelling salesman art of Bob Bosch and so the idea of using a single curve to draw a picture was not far from my mind. Henry Segerman has made some 3D printed shapes which interpolate from one level of a Hilbert curve to another, which introduces the idea of the different levels existing together. I had also seen some animations using different stages of Hilbert curves to indicate levels of darkness in an image, though not as a single curve. Putting these together, I wanted to make an image using different levels of Peano curves to indicate light and dark, while keeping it as a single curve.

I’m not the first to have the idea of using space-filling curves in this fashion, but I like exploring ideas and I find that eventually I have to try things out for myself without worrying about whether I’m retreading old ground or breaking new.

This also seems an appropriate point to explain why I settled on Peano curves rather than Hilbert curves or some other variant. One reason is quite simply that I prefer to use the object less studied. I’d rather adapt something from a well-known case to a less well-known one than simply repeat what has already been done. So the fact that Peano curves are used less than Hilbert curves naturally inclines me towards them. But more importantly, with a Peano curve then the last point on the curve is in the opposite corner to the starting point whereas with a Hilbert curve it is in a neighbouring corner. My eventual construction worked better with opposite corners than neighbouring ones.

The key insight was that the path taken from the centre of one square to the next was relatively unimportant. So long as the route from one centre to the next doesn’t stray outside the two squares themselves, the limit will still be the Peano curve. This is because as the squares get smaller the distance between the original construction and a variation will be no bigger than the width of the squares and this gets vanishingly small.

Travelling diagonally

So rather than joining the centres with straight lines, we travel from one corner to the opposite, as in the leftmost picture above. This is a different, but known, construction of Peano’s curve. As the curve now meets itself, it can be somewhat tricky to trace its actual path. To combat that, I’ve squared-off the corners in the second image. An alternative is to tie a little knot at each corner, which is an approach that I’m quite fond of—and as far as I’m aware hasn’t been studied by anyone else—but which ultimately I didn’t use in this particular design.

The picture and its Peanoification

With this basic pattern it is possible to replace an individual square by a copy of itself (suitably scaled) without disturbing the rest of the curve, as shown in the rightmost picture above. This can also be viewed as a type of path replacement where a single diagonal line is replaced by the crinkled line, and then each segment of that is replaced by a copy of itself, and so on. More on this later.

Using this I could make a picture: start with a grid of squares of suitable dimensions. Create a black-and-white picture by colouring in some squares, then convert that to a Peano curve by using the next level for the darker squares. The diagram to the right shows the pixel picture and its conversion to a Peano curve.

This made it a more interesting image but it didn’t make it self-explanatory. But once I realised I could replace the paths with anything suitable, the last step was not hard to conceive. Just hard to implement. I turned the curve into a text written as the ultimate in joined-up writing.

Exploring beyond

The construction of the Peano curve which works by replacing line segments by more complicated curves is an example of a method which is typically used to produce fractal images. Technically, only the actual Peano curve is a fractal as stopping after a finite number of steps produces a curve that doesn’t have the ‘infinite zoom’ of a genuine fractal. So drawing the fractal that results from the Peano curve results in just a filled square. Not quite as exciting as, say, the Mandelbrot set. But using selective replacements we can produce genuine fractals that have a more aesthetic appearance.

Peano fractals

Continually replacing the line in the central square, we get a curve that looks a bit like the top left image on the left. The top right image is built similarly but with the top right square being replaced each time. In this image, after traversing the eight segments of one level, you are two-thirds of the way closer to your destination by a direct route, but you still have the same distance to travel if you stick to the path. In the opposite direction, we could apply level deepening only to the squares on the outside edges, leading to the bottom left image, while applying the deepening to non-central squares leads to a melding of Peano curves with the Sierpinski carpet on the bottom right.

Another route to explore is to interpolate between the levels. Playing around with different ways to adjust the path gave me the idea of making them flexible, and that led to thinking of the basic path as the end of a family of paths starting from just a diagonal line and slowly crinkling up, as shown below. This interpolation gives a sense of greyscale or can be used to animate between pictures. This can be used to make a more intricate image.

Interpolating the diagonal version of the Peano curve.

So by careful choices, it is possible to find a family of curves starting with just a diagonal line and ending with the full Peano curve and which makes a picture of Peano himself somewhere along the way, as you can see below.

Peano in a Peano curve, and detail of his left eye. Image: no permission required.

Just as Peano and Hilbert experimented with the ideas of Cantor to produce the original space-filling curves, I’ve experimented with their ideas to produce my postcard and more. I suppose my real response to the question ‘what can you do with this space?’ is to pose a question of my own: ‘what can you do with this curve?’.

So far, the answer seems to be ‘quite a lot’.

Further reading

There is a lot of literature on space-filling curves, ranging from viewing then as art forms, as I have done here, through hearing them as music, to practical applications in the field of image analysis. I’ve already mentioned Henry Segerman and Bob Bosch; other names I’ve encountered while researching this article are Herman Haverkort, Jeffrey Ventrella, and Doug McKenna.

From the historical perspective, the original papers of Cantor, Peano, and Hilbert can be found online (albeit in their original languages!) and there is a chapter on them in the book Curves for the Mathematically Curious.

They are a fascinating class of objects to study and after making my postcard I’ve found myself returning to them again and again to play and explore. Somewhat like the curves themselves, the closer I look, the more detail I see. Ultimately, the space that they are filling is that of my imagination.

Andrew is a maths and computer science teacher at Oxford High School, part of the Girls’ Day School Trust. Prior to that, he was an academic mathematician specialising in differential topology. In his copious spare time he writes programs that make images by combining weird mathematical effects such as Peanoification.
@mathforge    loopspace.mathforge.org    + More articles by Andrew

More from Chalkdust