Space-filling
curve

### From Wikipedia, the free
encyclopedia

**Space-filling curves** or **Peano curves** are curves, first
described by Giuseppe Peano (1858–1932), whose ranges contain the
entire 2-dimensional unit square (or the 3-dimensional unit cube).

Intuitively, a "continuous
curve" in the 2-dimensional plane or in the 3-dimensional space can be
thought of as the "path of a continuously moving point". To eliminate
the inherent vagueness of this notion, Jordan
in 1887 introduced the following rigorous definition, which has since been
adopted as the precise description of the notion of a "continuous
curve":

A curve (with
endpoints) is a continuous function whose domain is the unit
interval [0,1].

In the most general form, the
range of such a function may lie in an arbitrary topological space, but in the
most common cases, the range will lie in a Euclidean
space such as the 2-dimensional plane (a "plane curve") or the
3-dimensional space ("space curve").

Sometimes, the curve is
identified with the range or image of the function (the set of all possible
values of the function), instead of the function itself. It is also possible to
define curves without endpoints to be a continuous function on the real line
(or on the open unit interval (0,1)).

In 1890, Peano discovered a **densely
self-intersecting** curve which passed through every point of the unit
square. This was the first example of a space-filling curve. Peano's purpose
was to construct a continuous mapping from the unit
interval onto the unit square, motivated by Georg
Cantor's earlier counterintuitive result that the infinite number of points
in a unit
interval is the same cardinality as the infinite number of points in any
finite-dimensional manifold, such as the unit square.

Six iterations of
the Hilbert
curve, a space-filling curve devised by mathematician David
Hilbert

It was common to associate the
vague notions of "thinness" and "1-dimensionality" to
curves; all normally encountered curves were piecewise
smooth (that is, have piecewise continuous derivatives), and such curves cannot
fill up the entire unit square. Therefore, Peano's space filling curve was
found to be highly counterintuitive.

From Peano's example, it was easy
to deduce continuous curves whose ranges contained the n-dimensional hypercube
(for any positive integer n). It was also easy to extend Peano's example to
continuous curves without endpoints which filled the entire n-dimensional
Euclidean space (where n is 2, 3, or any other positive integer).

Most well-known space-filling
curves are constructed iteratively as the limit of a sequence of piecewise
linear continuous curves.

## Contents[hide] |

## [edit]
Outline of the construction of a space-filling curve

Let denote the Cantor
space .

We start with a continuous
function *h* from the Cantor
space onto the entire unit interval [0,1].
(The restriction of the Cantor function to the Cantor set
is an example of such a function.) From it, we get a continuous function *H* from the topological product onto the entire unit square by setting

Since the Cantor set
is homeomorphic to the product , there is a continuous
bijection *g* from the Cantor set
onto . The composition *f* of *H* and *g* is a continuous function mapping the Cantor set
onto the entire unit square. (Alternatively, we could use the theorem that
every compact
metric space is a continuous image of the Cantor set
to get the function *f*.)

Finally, one can extend *f* to a continuous function *F*
whose domain is the entire unit interval [0,1]. This
can be done either by using the Tietze extension theorem on each of the
components of *f*, or by simply extending *f* "linearly" (that is, on each of the
deleted open interval (*a*,*b*) in the
construction of the Cantor set, we define the extension part of *F* on (*a*,*b*)
to be the line segment within the unit square joining the values *f*(*a*) and *f*(*b*)).

## [edit] Properties

Approximation curves remain
within a bounded portion of n-dimensional space, but their lengths increase
without bound.

The space-filling curve is always
self-intersecting, although the approximation curves in the sequence can be
self-avoiding. There cannot be any non-self-intersecting (i.e. injective) continuous
curve filling up the unit square, because that will make the curve a homeomorphism
from the unit interval onto the unit square (any continuous bijection
from a compact space onto a Hausdorff
space is a homeomorphism), but the unit-square (which has no cut-point) is
not homeomorphic to the unit interval (all points of which, except the
endpoints, are cut-points).

## [edit] Proof that a
square and its side contain the same number of points

The highly counterintuitive
result that the cardinality of a unit
interval is the same as the cardinality of any finite-dimensional manifold, such
as the unit
square, was first obtained by Cantor in 1878, but it can be more
intuitively proved using space-filling curves.

Space-filling curves are always
self-intersecting. This means that they are not injective,
and as a consequence not bijective. Since a bijection between a set A and a set B is
needed to prove that A and B have the same cardinality, space-filling curves
are not a direct proof that a square (or cube or hypercube) has as many points
as its side, but they can be used to obtain such a proof.

Intuitively, consider that the
difficulty resided in showing that a function of the unit interval can fill a
square or a cube or a hypercube, and this task was successfully accomplished by
Peano. Indeed, being self-intersecting, his curves even manage to
"overfill" the square. In other words, although Peano curves are not
injective (because they overfill the space), they are surjective
(because they fill it).

More formally, consider a
space-filling curve which maps a unit interval [0,1] onto a unit square
[0,1]×[0,1]. One can define a right inverse for it which will be an injection
from [0,1]×[0,1] into [0,1]. And *x* goes to <*x*,0> is an
injection from [0,1] into [0,1]×[0,1]. Using the Cantor–Bernstein–Schroeder theorem,
we get a bijection between [0,1] and [0,1]×[0,1]. We conclude that [0,1] and
[0,1]×[0,1] have the same cardinality.

One advantage of this proof is
that, since an explicit definition of the right inverse is easily given, it
does not require the use of the axiom
of choice. For example, in the Hilbert curve each point in the square is
the image of from one to four points in the line
segment. When one of the coordinates is a rational number with a power of two
in the denominator, that coordinate can be approached either from below or
above giving two (not necessarily distinct) values for the preimage.
Similarly, when both are such, then there are four (not necessarily distinct).
Since the number of possible preimages for each point is finite (indeed less
than or equal to four), one can just choose the smallest of them
systematically, making the axiom of choice unnecessary.

Similarly, finite-dimensional
space-filling curves can be used to prove, in general, that any
finite-dimensional space contains the same number of points as any line or line
segment.

## [edit] The
Hahn-Mazurkiewicz theorem

The Hahn-Mazurkiewicz theorem is
the following characterization of general continuous curves:

*A Hausdorff topological space is a continuous image of the unit interval if
and only if it is a compact, connected,
locally connected second-countable space.*

*Note:* In many formulations of the Hahn-Mazurkiewicz
theorem, "second-countable" is replaced by "metrizable".
These two formulations are equivalent. In one direction a compact Hausdorff
space is a normal space and, by the Urysohn metrization theorem, second-countable then
implies metrizable. Conversely a compact metric space is second-countable.

## [edit] Literature

- Hans Sagan,
*Space-Filling Curves*, Springer-Verlag 1994. ISBN 0387942653. - B. B. Mandelbrot,
*The Fractal Geometry of Nature*, Ch. 7, "Harnessing the Peano Monster Curves", W. H. Freeman, 1982 - Douglas M. McKenna, "SquaRecurves,
E-Tours, Eddies, and Frenzies: Basic Families of Peano Curves on the
Square Grid", a chapter from
*The Lighter Side of Mathematics - Proceedings of the Eugene Strens Memorial Conference on Recreational Mathematics and its History*, Math. Assoc. of America, 1994 - G. Peano,
*Sur une courbe, qui remplit toute une aire plane.*Math. Ann 36 (1890), 157-160.

## [edit] See also

- Dragon
curve
- Gosper
curve
- Hilbert
curve
- Hilbert
R-tree
- Moore
curve
- Sierpiński curve
- Z-order (curve)
- Self-similar
fractal
- List of fractals by
Hausdorff dimension

## [edit] External links

Java applets:

- Peano
Plane Filling Curves at cut-the-knot
- Hilbert's
and Moore's Plane Filling Curves at cut-the-knot
- All
Peano Plane Filling Curves at cut-the-knot

Retrieved from
"http://en.wikipedia.org/wiki/Space-filling_curve"