A Complete Taxonomy of Plane-filling Curves

I am in the process of completing several years of work in developing a complete taxonomy of plane-filling curves. There are infinitely many plane-filling curves, but most of the ones you are familiar with can be found among the first nine families:

screen-shot-2017-02-11-at-10-02-11-pm

Some of these were introduced in Mandelbrot’s famous book. They are constructed using “edge-replacement” (Mandelbrot called it “Koch construction”).

tttt

“Edge-replacement curves” are to be contrasted with “node-replacement curves” such as the Hilbert Curve. (I explain the difference between these two techniques in this article).

Have you ever wondered if there is a relationship between the classic Dragon Curve and Mandelbrot’s Amazing self-avoiding Snowflake Sweep?

a1

Have you ever wondered why some space-filling curves are self-avoiding, while others touch themselves all over? Below is the Gosper Curve and Dragon of Eve (a self-avoiding curve I discovered in the 1980’s):

rrr

Both the Dragon of Eve and another curve I discovered (below) each have generators with only three segments. These constitute the simplest generators (in terms of segment count) that afford self-avoiding curves:

self-avoiding

Notice that these curves occupy two kinds of lattice: square and triangular (sometimes called “hexagonal lattice”). I mentioned this to Adam Goucher, and asked him if he had any insights abut the special properties of these curves, in terms of how they relate to the lattices that they occupy. He said that these properties can be understood in terms of the Gaussian integers (square lattice) and Eisenstein integers (triangular lattice).

Thank you Adam! What amazing discoveries poured in after thinking of these curves in this way. I have begun to think of a plane-filling curve as an ordered sum of integers (each segment is an integer “added” to the previous segment in the list). The endpoint is an integer in the plane which represents the family for that curve.

Here are just a few of the hundreds of amazing curves I have fished out of the deep sea, in the process of developing this taxonomy. (Some of the self-touching curves have been smoothed-out with splines to reveal the beautiful sweep of its path as it fills the body).

 

cool

I will be adding more on this subject over the year. Meanwhile, come visit fractalcurves.com.

Is there a 3D Gosper curve?

The Gosper curve is one of the most amazing and satisfying plane-filling curves.

7t_gosper

gosper_curve_1650

The Gosper curve is a self-avoiding, plane-filling fractal curve containing 7^n segments (where n is the order of the teragon). It approximates the shape of a hexagon. It is named after the mathematician William Gosper.

screen-shot-2016-09-26-at-8-17-15-pm

Like all plane-filling curves generated using a deterministic recursive algorithm, the Gosper curve can be mapped to a tiling. In this case, the tile is the hexagon. As you increase the order of the teragon, the number of line segments – and thus hexagons – increases. And the boundary becomes more rugged. Below at right is an image of the Gosper boundary, created by the tiling of seven “rep-tiles“, each self-similar to the whole shape.

hex

Counting Pennies

The regular hexagon is similar to the circle in the sense that the close-packing of circles forms a hexagonal arrangement. Imagine having 343 (7^3) pennies arranged on a table. If you try to push them together into the smallest area you can,  you might end up approximating the shape of the Gosper curve.

pennies

dfgdfgThere are many ways to count a bunch of pennies. In this case you could count them in the order of the Gosper curve’s sweep. Since it is recursive, you could pause every 7 pennies to catch your breath. And you could also pause every 49 pennies for longer breaks. Between each break, you will have traced out a low-order Gosper curve.

On To the Third Dimension

Now, what if we extend this idea to three dimensions? Well, consider the close-packing of spheres. In the case of spheres, there are 12 spheres that can surround a single sphere, making a clump with a total of 13 spheres.

And…just as close-packing circles correspond to the tiling hexagon, 3D circles (spheres) correspond to the tiling rhombic dodecahedron.

Rhombic dodecahedra can be tiled infinitely, leaving no gaps and having no overlaps. This brings us to the big question: might there be a 3D spacefilling curve that can be drawn within a volume which is the union of 13^n rhombic dodecahedra? In other words…

Is there such a thing as a 3D Gosper Curve?
Now, to be fair…asking this question is a bit like asking, “Is there a 3D Mandelbrot Set?” The boring but true answer is no, of course not! …because the canonical Mandelbrot Set is by definition a 2D object. Also, the mathematical properties of complex numbers do not translate into 3D.

1136px-power_8_mandelbulb_fractal_overviewYou may be able to find a 4D analog of the Mandelbrot Set by skipping the third dimension and jumping over to the fourth dimension. (Hamilton tried in vain to find a 3D analog of complex numbers. And this led him to the next dimension – where he discovered quaternions). FYI – the Mandebrot Set’s 2D nature didn’t stop explorers from trying to find a higher being. And in the process, what they found was something extraordinary: The Mandelbulb.

Now, back to the 3D Gosper curve. Is there is anything we can call a “3D Gosper curve”? To earn that title, it would have to have some fundamental attributes in common with the Gosper curve. This is what I had in mind as I set out to discover this elusive higher being. As a template, I chose the tessellation of 13 rhombic dodecahedra, because it it similar to the tessellation of 7 hexagons.

henry_segerman_terdragon_smallI posed my question to mathematician Henry Segerman. Just as you can tile seven hexagons (one in the middle surrounded by six), you can analogously tile thirteen rhombic dodecahedra (one in the middle surrounded by twelve). But can you then take 13 of these shapes and tile them into a larger blob of 13^3 dodecs? To explore the problem, Henry came up with the following images that he created using Rhino. After only two levels of recursion, he came to the conclusion that they probably do not tile   !!!!  

screen-shot-2016-09-17-at-1-40-46-pm

I asked Henry to send me the file for this 3D model, and then asked my colleague Barry Stump to fabricate it on his 3D printer. Here’s what Barry came up with:

screen-shot-2016-10-03-at-3-06-45-pm

Well, three of these shapes tessellate. But we need to tessellate 13 of them with the same symmetry as the original 13 unit tiles – to see with our own eyes and feel with our own hands – before we can be sure.

Before even asking whether a space-filling curve can be drawn that traverses each dodecahedron, I needed to determine whether the overall space can recursively tile without limit, and with no gaps or overlaps. If the answer is negative, then there is no use in asking about the curve, because it would not extend infinitely, as in the case of the canonical Gosper curve.

The jury is out. But it’s not looking good. A proof that it cannot be done would be better than nothing.

On Filling Fractal Dimensions 

screen-shot-2016-10-06-at-10-07-40-amIt is well known that the Hilbert curve can be extended into 3D, as was shown in The Algorithmic Beauty of Plants. (My friend Dave Fracchia did the raytrace rendering of this on an old SGI machine – back in the day 🙂 Anyway, there are still many unanswered questions. I have a feeling that certain people (like Henry) will have key insights about this. Henry has created physical versions of the Hilbert curve. This is an example of a 3D space-filling curve that has a direct analog in 2D. So what is it about the Hilbert curve that allows it to extend into 3D?

screen-shot-2016-09-26-at-8-59-16-pm

My original line of inquiry was this: think of the Hilbert curve in terms of tiling squares. The 2D Hilbert curve maps a line of length 2 to a square of area 2^2 = 4. The 3D Hilbert curve maps a line of length 2 to a cube of volume 2^3 = 8. The idea of the Hilbert curve as progressive squaring is described in my blog post comparing the Hilbert curve with the Peano Sweep:

screen-shot-2016-09-26-at-9-59-51-pm

screen-shot-2016-09-26-at-10-03-38-pmCould the same logic be used with other shapes? Other than the cube, the logical 3D tessellating shape in my mind is the rhombic dodecahedron. But it appears not to tesselate recursively to create rep-tiles. My hope was (and still is) that there exists a tiling polyhedron within which one can fit a line between vertices having a length equal to the cube root of 13, and that 13 of these would tile to form a volume of 13. But am I misguided by looking for the cube root? Perhaps I need to consider the square root? (The Euclidean distance).

img_0318Here’s a picture I drew of 13 unit cubes representing rhombic dodecahedra. (BTW – if you stellate each face of a cube by adding a square pyramid, it becomes a rhombic dodecahedron. And if you start with a “3D checkerboard” of 13 cubes, like I have drawn, the result is 13 tessellating rhombic dodecahedra. Cool, eh? Now, look at red lines in the drawing. the distance from A to B happens to be the square root of 13 (assuming unit cubes).

A line drawn from A to B might be analogous to the line drawn within the hexagon in the image at the beginning of this article. Am I missing something?

I have a feeling that there are answers right around the corner. And it may be that I am simply asking the wrong questions!

And it still may be that we have to jump over the third dimension to the land of quaternions to get the right answers. There, we might find a new realm of hyper-space-filling curves – living among the integer quaternions – analogous to the Gaussian and Eisenstein integers, which are integral domains in which number theory can be used to make sense of space-filling curves.

Space-Filling Curves Are Not Squares

Screen Shot 2014-11-15 at 8.20.35 PMWikipedia says:

“In mathematical analysis, a space-filling curve is a curve whose range contains the entire 2-dimensional unit square (or more generally an n-dimensional hypercube“.

The image at right shows the Hilbert curve as an example. Indeed, the Hilbert curve fills a square. And its 3D counterpart fills a cube.

Screen Shot 2014-11-15 at 8.53.04 PMHowever, a space-filling curve (or…to just stick with two dimensions: a plane-filling curve) can be more generally described as a curve that fills a region of the plane that is topologically equivalent to a square (or…a disk). Note that a filled-in square, a disk, and a cone are topologically the same. “A cone?” you may ask. Yes, it has one surface (interior), and one boundary.

Now consider the following space-filling curves:

2000px-Gosper_curve_3.svg

Here we see the famous Dragon Curve, the Gosper Curve, and two curves that I discovered. If you have spent any time studying the Dragon curve, you know that it can be decomposed into a series of “body parts” joined at wasp-waist points. How many body parts? Why, infinitely many, to be exact. Topologically-speaking, this would be the same as an infinite chain of tangent disks.

Next is the Gosper Curve. it is topologically equivalent to a disk. Mandelbrot compared its boundary to the shape of France. Appropriate for a discussion on fractals, since the boundary of France is almost entirely determined by coastlines and mountain drainage divides.

And what about the last two curves? My first guess was that the third one from left, the “Dragon of Eve“, is topologically equivalent to a disk….however, there are regions of the boundary which get closer and closer, every time the curve is iterated. My conjecture is that the curve approaches a state of self-contact at the limit. That puts it in a different topological category than a mere disk, since the boundary is self-touching at infinitely many points.

The last curve is one I call “Brain-Filler“.

f4b12c8e1b35ba53caa7bd1b253053de

This curve resolves to a region of the plane that is topologically equivalent to a disk. Ignore the lines that extend upward and downward; they are thickened for aesthetic reasons. And besides, when iterated to the limit, the infinitely thin nature of a fractal curve gives way to the finite shape that it fills.

But!

…you may have noticed the way the curve wiggles its way through the shape. It is not evenly-filled, as in the case of the Gosper curve. So, the question comes up: does it really “fill” the space if it is not filling it evenly?

We could ask the same of Mandelbrot’s famous Snowflake Sweep.

9T_snowflake_sweep

Think through this with me: as the curve is iterated repeatedly, replacing each segment with a smaller, transformed version of itself, the interior of the snowflake curve become ever more filled-in. But…the density. varies.

At the limit, I conjecture that the interior will be filled-in with varying degrees of infinite density. And I am talking about different kinds of infinity in the Cantorian sense.

The Fractal Boundaries of Fractal Curves

So…there are space-filling curves that fill planar regions with fractal boundaries – boundaries that are more interesting and varied than boring old squares; boundaries that come around and touch themselves, or even penetrate themselves in ways that dizzy the mind.

Screen Shot 2014-11-15 at 9.27.08 PM

Space-filling curves are like symphonies – beautiful on all scales.

There may be a valid reason why the authors of the Wikipedia page cited above did not include any non-square space-filling curves. But I cannot think of a good reason – other than the fact that the Hilbert Curve provides a clear, easy-to-understand, easy-to-visualize example. However, a good example should not justify an incomplete definition.

Mandelbrot spent his career trying to get geometers away from squares and circles, and to appreciate, understand, and describe the fractal geometry of nature. His amazing book still stands as the best original source for fractal geometry, in my opinion.

I eagerly await your comments!