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.

Advertisements

Fractal Curves in Gaussian and Eisenstien Integer Lattices

snowflake_sweep

I have been working on a taxonomy of space-filling curves in the square and triangular lattices. I came across Adam Goucher’s blog: Complex Projective 4-Space. I asked Adam what he thought of my proposed fractal curve families and he told me that I should study the Gaussian and Eisenstein integers. The image below shows Gaussian integers (red dots) and Eisenstein integers (blue dots).

Screen Shot 2015-01-27 at 10.39.25 PM

So cool! Adam pointed me to a whole new world of discovery that I am still unraveling and unfolding to this day.

I will not get into the details of Gaussian and Eisenstein integers here, except to say that they are sets of complex numbers occupying square and triangular lattices respectively. (You can click on the links provided and follow the search to any level of detail you wish).

They can be seen as two-dimensional versions of the one-dimensional number line of integers that we are all so familiar with.

Like their familiar one-dimensional counterpart, the Gaussian and Eisenstein integers form an integral domain: the rules of addition and multiplication apply, and these operations always result in a new number which is within the domain. Gaussian and Eisenstein integers have their own unique prime number and composite number personalities – which make for a fascinating study – including how they relate to families of plane-filling curves.

The Koch Curve and it’s Squarish cousin occupy triangular and square grids, respectively. And each has a “spine” that traverses exactly three units.

grids

Koch_grid

In these two lattices, all distances of grid points from the origin (0+0i) are square roots of integers (Euclidian norm).

two_grids

full_lower

Squaring the Euclidian norm gives us the field norm , the integer that we use to denote the fractal family. It is either prime or composite.

Here are some examples of plane-filling curves that occupy the square lattice:

Example 1 (also discovered by Carbajo)

4S_cool

Example 2 (Mandelbrot’s “Quartet”)

5S_Mandie

Example 3: (a Root 13 self-avoiding curve)13S_full_tile

And here are some examples of plane-filling curves that occur in the triangular lattice:

Example 4: (a curve I discovered)

9T_Tree

Example 5: (a member of the Root 7 family)

7T_Coolness_2

Example 6: (a member of the triangle Root 9 family)

9T_late_night

Check out the generators of these curves (shown at the left of each diagram). You may have noticed that some of them consist of line segments of differing lengths. These represent members of composite fractal families: their spines traverse a distance that is equal to the square root of a composite number in the domain. (Examples 1, 4, and 6 are composite).

The members of “prime” families (examples 2, 3, and 5 above) can only have segments of length 1. Consequently, as they are iterated to create higher-level teragons, with more fractal detail, the texture becomes more even and smooth. The composite curves – on the other hand – have varying density within their flesh, which increases in variety as they are iterated.

This is awesome: it’s another way to show the recursive complexity of composite numbers. And if you ask me (and Greg Chaitin), the composite numbers are way more interesting than the primes!

composite

Here’s a plane-filling curve of the root-8 family. Since 8 = 2^3, this family contains interesting variants of the famous dragon curve, which is a member of the root 2 family. This example has the corners rounded for aesthetics. It shows some of the variation in scale within its flesh.

curly_dragonI’ll be posting more as discoveries are made. Stay tuned!

-Jeffrey

 

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!