Space-Filling Curves

A space-filling curve is a curve whose range covers the whole 2D unit square. We generally imagine space-filling curves as an infinite version of a finite construction using an iterative process.

Peano Curve

The first such curve was first discovered by Guiseppe Peano in 1890, and is thus given the name the ‘Peano Curve’. Peano’s Curve is a surjective, continuous function from the unit interval onto a unit square. However, it is not injective (a one-to-one function that preserves distinctiveness).

function-mapping.gif
Source: mathsisfun.com

Peano’s curve may be constructed using a sequence of steps. In step i, each square s of Si − 1 is partitioned into nine smaller equal squares, and its centre point c is replaced by a contiguous subsequence of the centres of the nine smaller squares. This subsequence is formed the following way:

  1. Group the nine smaller squares into 3 columns
  2. Order the centres contiguously within each column
  3. Order the columns from one side of the square to the other so that the distance between each consecutive pair of points in the subsequence equals the side length of the small squares.
800px-Peanocurve.svg.png
Three Iterations of Peano’s Curve | Source: Wikipedia

The Peano curve itself is the limit of the curves as i goes to infinity.

Hilbert Curve

Hilbert_curve.gif
Source: Wikipedia

In 1891, Hilbert published a variation of Peano’s construction. Hilbert was the first to use a picture, which was included in the article, to help visualise the construction technique.

The difference between the Peano and Hilbert curve is that the latter is based on subdividing squares into four equal smaller squares instead of into nine equal smaller squares. Hence, Hilbert maps intervals of length 2-2n into squares of size 2-n×2-n, whereas Peano’s construction is equivalent to mapping intervals of length 3-2n into squares of size 3-n×3-n.

Other Space Filling Curves

Moore Curve

Moore-curve-stages-0-through-5.png

The Moore Curve could be thought of as the union of four copies of the Hilbert curves combined in such a way to make the endpoints coincide.

Wunderlich Curve

wunderlich3.png

Read this article for more details on its construction.

Koch Snowflake

kochsnowflake13ifs.jpg

 

In my opinion, space-filling curves are another example of how mathematics can be beautiful – creating wonderful shapes and images.

Let me know what you think! M x