Space-filling curve

In mathematical analysis

Mathematical analysis

Mathematical analysis, which mathematicians refer to simply as analysis, has its beginnings in the rigorous formulation of calculus. It is the branch of pure mathematics most explicitly concerned with the notion of a limit, whether the limit of a sequence or the limit of a function...

, a space-filling curve is a curve

Curve

In mathematics, a curve is, generally speaking, an object similar to a straight line but which is not required to be straight. Often curves in two-dimensional or three-dimensional Euclidean space are of interest....

 whose range contains the entire 2-dimensional unit square

Unit square

In mathematics, a unit square is a square whose sides have length 1. Often, "the" unit square refers specifically to the square in the Cartesian plane with corners at , , , and .-In the real plane:...

 (or more generally an N-dimensional hypercube

Hypercube

In geometry, a hypercube is an n-dimensional analogue of a square and a cube . It is a closed, compact, convex figure whose 1-skeleton consists of groups of opposite parallel line segments aligned in each of the space's dimensions, perpendicular to each other and of the same length.An...

). Because Giuseppe Peano

Giuseppe Peano

Giuseppe Peano was an Italian mathematician, whose work was of exceptional philosophical value. The author of over 200 books and papers, he was a founder of mathematical logic and set theory, to which he contributed much notation. The standard axiomatization of the natural numbers is named in his...

 (1858–1932) was the first to discover one, space-filling curves in the 2-dimensional plane

Plane (mathematics)

In mathematics, a plane is any flat, two-dimensional surface. A plane is the two dimensional analogue of a point , a line and a space...

 are commonly called Peano curves.

Definition

Intuitively, a "continuous curve" in 2 or 3 (or higher) dimensions can be thought of as the "path of a continuously moving point". To eliminate the inherent vagueness of this notion Jordan

Camille Jordan

Marie Ennemond Camille Jordan was a French mathematician, known both for his foundational work in group theory and for his influential Cours d'analyse. He was born in Lyon and educated at the École polytechnique...

 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

Curve

In mathematics, a curve is, generally speaking, an object similar to a straight line but which is not required to be straight. Often curves in two-dimensional or three-dimensional Euclidean space are of interest....

 (with endpoints) is a continuous function

Continuous function

In mathematics, a continuous function is a function for which, intuitively, small changes in the input result in small changes in the output. Otherwise, a function is said to be "discontinuous". A continuous function with a continuous inverse function is called "bicontinuous"...

 whose domain is the unit interval

Unit interval

In mathematics, the unit interval is the closed interval [0,1], that is, the set of all real numbers that are greater than or equal to 0 and less than or equal to 1...

 [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

Euclidean space

In mathematics, Euclidean space is the Euclidean plane and three-dimensional space of Euclidean geometry, as well as the generalizations of these notions to higher dimensions...

 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)).

History

In 1890 Peano discovered a densely self-intersecting curve that passes through every point of the unit square. His purpose was to construct a continuous mapping from the unit interval

Unit interval

In mathematics, the unit interval is the closed interval [0,1], that is, the set of all real numbers that are greater than or equal to 0 and less than or equal to 1...

  onto the unit square

Unit square

In mathematics, a unit square is a square whose sides have length 1. Often, "the" unit square refers specifically to the square in the Cartesian plane with corners at , , , and .-In the real plane:...

. Peano was motivated by Georg Cantor

Georg Cantor

Georg Ferdinand Ludwig Philipp Cantor was a mathematician, best known as the creator of set theory, which has become a fundamental theory in mathematics...

's earlier counterintuitive result that the infinite number of points in a unit interval is the same cardinality

Cardinality

In mathematics, the cardinality of a set is a measure of the "number of elements of the set". For example, the set A = {2, 4, 6} contains 3 elements, and therefore A has a cardinality of 3. There are two approaches to cardinality – one which compares sets directly using bijections and...

 as the infinite number of points in any finite-dimensional manifold

Manifold

In mathematics, more specifically in differential geometry and topology, a manifold is a mathematical space that on a small enough scale resembles the Euclidean space of a specific dimension, called the dimension of the manifold....

, such as the unit square. The problem Peano solved was whether such a mapping could be continuous, i.e, a curve that fills a space.
It was common to associate the vague notions of "thinness" and "1-dimensionality" to curves; all normally encountered
curves were piecewise

Piecewise

In mathematics, a piecewise-defined function is a function whose definition changes depending on the value of the independent variable...

 differentiable (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

Hypercube

In geometry, a hypercube is an n-dimensional analogue of a square and a cube . It is a closed, compact, convex figure whose 1-skeleton consists of groups of opposite parallel line segments aligned in each of the space's dimensions, perpendicular to each other and of the same length.An...

 (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, each one more closely approximating the space-filling limit.

Peano's ground-breaking paper contained no illustrations of his construction. But a year later, Hilbert published a new and simpler construction, now known as the Hilbert Curve. His 1891 paper was the first to include a picture of the construction technique, essentially the same as illustrated here.

Outline of the construction of a space-filling curve

Let $\backslash mathcal\{C\}$ denote the Cantor space

Cantor space

In mathematics, a Cantor space, named for Georg Cantor, is a topological abstraction of the classical Cantor set: a topological space is a Cantor space if it is homeomorphic to the Cantor set. In set theory, the topological space 2^ω is called "the" Cantor space...

$\backslash mathbf\{2\}^\backslash mathbb\{N\}$.

We start with a continuous function $h$ from the Cantor space $\backslash mathcal\{C\}$ onto the entire unit interval $[0,1]$. (The restriction of the Cantor function

Cantor function

In mathematics, the Cantor function, named after Georg Cantor, is an example of a function that is continuous, but not absolutely continuous. It is also referred to as the Devil's staircase.-Definition:...

 to the Cantor set

Cantor set

In mathematics, the Cantor set, introduced by German mathematician Georg Cantor in 1883 , is a set of points lying on a single line segment that has a number of remarkable and deep properties. Through consideration of it, Cantor and others helped lay the foundations of modern general topology...

 is an example of such a function.) From it, we get a continuous function $H$ from the topological product $\backslash mathcal\{C\}\; \backslash times\; \backslash mathcal\{C\}$ onto the entire unit square $[0,1]\; \backslash times\; [0,1]$ by setting
$H(x,y)\; =\; (h(x),h(y)).\backslash ,$

Since the Cantor set is homeomorphic to the product $\backslash mathcal\{C\}\; \backslash times\; \backslash mathcal\{C\}$, there is a continuous bijection $g$ from the Cantor set onto $\backslash mathcal\{C\}\; \backslash times\; \backslash mathcal\{C\}$. 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

Tietze extension theorem

In topology, the Tietze extension theorem states that, if X is a normal topological space andis a continuous map from a closed subset A of X into the real numbers carrying the standard topology, then there exists a continuous map...

 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)$).

Properties

A space-filling curve must be everywhere self-intersecting in the technical sense that the curve is not injective. If a curve is not injective, then one can find two "subcurves" of the curve, each obtained by considering the images of two disjoint segments from the curve's domain (the unit line segment). The two subcurves intersect if the intersection

Intersection (set theory)

In mathematics, the intersection of two sets A and B is the set that contains all elements of A that also belong to B , but no other elements....

 of the two images is non-empty. One might be tempted to think that the meaning of "curves intersecting" is that they necessarily cross each other, like the intersection point of two non-parallel lines, from one side to the other. But two curves (or two subcurves of one curve) may contact one another without crossing, as, for example, a line tangent to a circle does.

A non-self-intersecting continuous curve cannot fill the unit square because that will make the curve a homeomorphism

Homeomorphism

In the mathematical field of topology, a homeomorphism or topological isomorphism or bicontinuous function is a continuous function between two topological spaces that has a continuous inverse function...

 from the unit interval onto the unit square (any continuous bijection

Bijection

In mathematics, a bijection, or a bijective function, is a function f from a set X to a set Y with the property that, for every y in Y, there is exactly one x in X such that f = y and no unmapped element exists in either X or Y.Alternatively, f is bijective if it is a one-to-one correspondence...

 from a compact space

Compact space

In mathematics, more specifically general topology and metric topology, a compact space is an abstract mathematical space in which, intuitively, whenever one takes an infinite number of "steps" in the space, eventually one must get arbitrarily close to some other point of the space...

 onto a Hausdorff space

Hausdorff space

In topology and related branches of mathematics, a Hausdorff space, separated space or T₂ space is a topological space in which distinct points have disjoint neighbourhoods. Of the many separation axioms that can be imposed on a topological space, the "Hausdorff condition" is the most...

 is a homeomorphism). But a unit-square has no cut-point

Cut-point

In topology, a cut-point is a point of a connected space such that its removal causes the resulting space to be disconnected. For example every point of a line is a cut-point, while no point of a circle is a cut-point...

, and so cannot be homeomorphic to the unit interval, in which all points except the endpoints are cut-points.

For the classic Peano and Hilbert space-filling curves, where two subcurves intersect (in the technical sense), there is self-contact without self-crossing. A space-filling curve can be (everywhere) self-crossing if its approximation curves are self-crossing.

A space-filling curve's approximations can be self-avoiding, as the figures above illustrate. In 3 dimensions, self-avoiding approximation curves can even contain knot

Knot theory

In mathematics, knot theory is the area of topology that studies mathematical knots. While inspired by knots which appear in daily life in shoelaces and rope, a mathematician's knot differs in that the ends are joined together to prevent it from becoming undone. In precise mathematical language, a...

s.

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

Space-filling curves are special cases of fractal

Fractal

A fractal is "a rough or fragmented geometric shape that can be split into parts, each of which is a reduced-size copy of the whole," a property called self-similarity...

 constructions.

No differentiable space-filling curve can exist. Roughly speaking, differentiability puts a bound on how fast the curve can move.

Proof that a square and its side contain the same number of points

The highly counterintuitive result that the cardinality

Cardinality

In mathematics, the cardinality of a set is a measure of the "number of elements of the set". For example, the set A = {2, 4, 6} contains 3 elements, and therefore A has a cardinality of 3. There are two approaches to cardinality – one which compares sets directly using bijections and...

 of a unit interval

Unit interval

In mathematics, the unit interval is the closed interval [0,1], that is, the set of all real numbers that are greater than or equal to 0 and less than or equal to 1...

 is the same as the cardinality of any finite-dimensional manifold

Manifold

In mathematics, more specifically in differential geometry and topology, a manifold is a mathematical space that on a small enough scale resembles the Euclidean space of a specific dimension, called the dimension of the manifold....

, such as the unit square

Unit square

In mathematics, a unit square is a square whose sides have length 1. Often, "the" unit square refers specifically to the square in the Cartesian plane with corners at , , , and .-In the real plane:...

, was first obtained by Cantor in 1878, but it can be more intuitively proved using space-filling curves.

As noted under Properties (above), space-filling curves cannot be bijective. Because a bijection between a set A and a set B is needed to prove that A and B have the same cardinality, the existence of space-filling curves is not a direct proof that a square (or cube or hypercube) has as many points as its side. But space-filling curves can be used to obtain such a proof via the Cantor–Bernstein–Schroeder theorem

Cantor–Bernstein–Schroeder theorem

In set theory, the Cantor–Bernstein–Schroeder theorem, named after Georg Cantor, Felix Bernstein, and Ernst Schröder, states that, if there exist injective functions f : A → B and g : B → A between the sets A and B, then there exists a bijective function h : A → B...

, which asserts the existence of a bijection between A and B given that injections exist both from A to B and from B to A.

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). This is true whether their self-intersection is self-crossing, or merely self-contacting.

More formally, consider a space-filling curve that 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, because an explicit definition of the right inverse is easily given, it does not require the use of the axiom of choice

Axiom of choice

In mathematics, the axiom of choice, or AC, is an axiom of set theory. Informally put, the axiom of choice says that given any collection of bins, each containing at least one object, it is possible to make a selection of exactly one object from each bin, even if there are infinitely many bins and...

. For example, in the Hilbert curve each point in the square is the image

Image (mathematics)

In mathematics, the image of a subset of a function's domain under the function is the set of all outputs obtained when the function is evaluated at each element of the subset...

 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

Line (geometry)

In Euclidean geometry, a line is a straight curve. When geometry is used to model the real world, lines are used to represent straight objects with negligible width and height. Lines are an idealization of such objects and have no width or height at all and are usually considered to be infinitely...

 or line segment

Line segment

In geometry, a line segment is a part of a line that is bounded by two end points, and contains every point on the line between its end points. Examples of line segments include the sides of a triangle or square. More generally, when the end points are both vertices of a polygon, the line segment...

.

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

Connected space

In topology and related branches of mathematics, a connected space is a topological space which cannot be represented as the union of two or more disjoint nonempty open subsets. Connectedness is one of the principal topological properties that is used to distinguish topological spaces...

, locally connected second-countable space

Second-countable space

In topology, a second-countable space is a topological space satisfying the "second axiom of countability". Specifically, a space is said to be second-countable if its topology has a countable base...

.

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

Hausdorff space

In topology and related branches of mathematics, a Hausdorff space, separated space or T₂ space is a topological space in which distinct points have disjoint neighbourhoods. Of the many separation axioms that can be imposed on a topological space, the "Hausdorff condition" is the most...

 is a normal space

Normal space

In topology and related branches of mathematics, normal spaces, T₄ spaces, T₅ spaces, and T₆ spaces are kinds of topological spaces. These conditions are examples of separation axioms.- Definitions :...

 and, by the Urysohn

Pavel Samuilovich Urysohn

Pavel Samuilovich Urysohn, Pavel Uryson was a Ukrainian mathematician who is best known for his contributions in the theory of dimension, and for developing Urysohn's Metrization Theorem and Urysohn's Lemma, both of which are fundamental results in topology. His name is also commemorated in the...

 metrization theorem

Metrization theorem

In topology and related areas of mathematics, a metrizable space is a topological space that is homeomorphic to a metric space. That is, a topological space is said to be metrizable if there is a metric such that the topology induced by d is...

, second-countable then implies metrizable. Conversely a compact metric space is second-countable.

See also

• Dragon curve
  Dragon curve
  A dragon curve is any member of a family of self-similar fractal curves, which can be approximated by recursive methods such as Lindenmayer systems.-Heighway dragon:...
  
  
• Gosper curve
  Gosper curve
  The Gosper curve, named after Bill Gosper, also known as the flowsnake , is a space-filling curve. It is a fractal object similar in its construction to the dragon curve and the Hilbert curve....
  
  
• Moore curve
  Moore curve
  A Moore curve is a continuous fractal space-filling curve which is a variant of the Hilbert curve. Precisely, it is the loop version of the Hilbert curve, and it may be thought as the union of four copies of the Hilbert curves combined in such a way to make the endpoints coincide.Because the Moore...
  
  
• Sierpiński curve
  Sierpinski curve
  Sierpiński curves are a recursively defined sequence of continuous closed plane fractal curves discovered by Wacław Sierpiński, which in the limit completely fill the unit square: thus their limit curve, also called the Sierpiński curve, is an example of a space-filling curve.Because the...
  
  
• Space-filling tree
  Space-filling tree
  Space-filling trees are geometric constructions that are analogous to space-filling curves, but have a branching, tree-like structure and are rooted. A space-filling tree is defined by an incremental process that results in a tree for which every point in the space has a finite-length path that...
  
  
• Hilbert R-tree
  Hilbert R-tree
  Hilbert R-tree, an R-tree variant, is an index for multidimensional objects like lines, regions, 3-D objects, or high dimensional feature-based parametric objects. It can be thought of as an extension to B+-tree for multidimensional objects....
  
  
• B^x-tree
  Bx-tree Moving Object Index
  In computer science, the B^x tree is a query and update efficient B+ tree-based index structure for moving objects.-Index structure:...
  
  
• Z-order (Morton-order)
  Z-order (curve)
  Z-order, Morton-order or Morton code first proposed in 1966 by G. M. Morton, is a space-filling curve which is often used in computer science: Due to its good locality-preserving behaviour it is used in data structures for mapping multidimensional data to one dimension...
  
  
• Fractal
  Fractal
  A fractal is "a rough or fragmented geometric shape that can be split into parts, each of which is a reduced-size copy of the whole," a property called self-similarity...
  
  
• List of fractals by Hausdorff dimension
• Osgood curve
  Osgood curve
  In mathematics, an Osgood curve is a Jordan curve of positive area. The first example was found by .Examples of Osgood curves can be produced by slightly modifying one of the constructions of space-filling curves with image the unit square to make it an embedding, though the cost is that it no...
  
  

External links

• Multidimensional Space-Filling Curves
• Proof of the existence of a bijection at cut-the-knot
  Cut-the-knot
  Cut-the-knot is a free, advertisement-funded educational website maintained by Alexander Bogomolny and devoted to popular exposition of many topics in mathematics. The site has won more than 20 awards from scientific and educational publications, including a Scientific American Web Award in 2003,...
  
  

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