View source for Space-filling curve

{{Short description|Curve whose range contains the unit square}}
[[Image:Peanocurve.svg|400px|thumb|Three iterations of the [[Peano curve]] construction, whose limit is a space-filling curve.]]
In [[mathematical analysis]], a '''space-filling curve''' is a [[curve]] whose [[Range of a function|range]] reaches every point in a higher dimensional region, typically the [[unit square]] (or more generally an ''n''-dimensional unit [[hypercube]]). Because [[Giuseppe Peano]] (1858–1932) was the first to discover one, space-filling curves in the [[plane (mathematics)|2-dimensional plane]] are sometimes called ''Peano curves'', but that phrase also refers to the [[Peano curve]], the specific example of a space-filling curve found by Peano.

The closely related '''FASS curves''' (approximately space-Filling, self-Avoiding, Simple, and Self-similar curves)
can be thought of as finite approximations of a certain type of space-filling curves.<ref>
Przemyslaw Prusinkiewicz and Aristid Lindenmayer.
[https://books.google.com/books?id=4F7lBwAAQBAJ "The Algorithmic Beauty of Plants"].
2012.
p. 12
</ref><ref>
Jeffrey Ventrella.
[https://books.google.com/books?id=Qj-zAwAAQBAJ "Brainfilling Curves - A Fractal Bestiary"].
2011.
p. 43
</ref><ref>
Marcia Ascher.
[https://books.google.com/books?id=FQBaDwAAQBAJ "Mathematics Elsewhere: An Exploration of Ideas Across Cultures"].
2018.
p. 179.
</ref><ref>
[https://books.google.com/books?id=lPdQAAAAMAAJ "Fractals in the Fundamental and Applied Sciences"].
1991.
p. 341-343.
</ref><ref>
Przemyslaw Prusinkiewicz; Aristid Lindenmayer; F. David Fracchia.
[http://algorithmicbotany.org/papers/fass.html "Synthesis of Space-Filling Curves on the Square Grid"].
1989.
</ref><ref>
[https://tilings.math.uni-bielefeld.de/glossary/FASS-curve/ "FASS-curve"].
D. Frettlöh, E. Harriss, F. Gähler: Tilings encyclopedia, https://tilings.math.uni-bielefeld.de/
</ref>

== Definition ==
Intuitively, a curve in two or three (or higher) dimensions can be thought of as the path of a continuously moving point.  To eliminate the inherent vagueness of this notion, [[Camille Jordan|Jordan]] in 1887 introduced the following rigorous definition, which has since been adopted as the precise description of the notion of a ''curve'':

{{block indent|A curve (with endpoints) is a [[continuous function]] whose domain is the [[unit interval]] {{nowrap|[0, 1]}}.}}

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

Sometimes, the curve is identified with the [[Image_(mathematics)#Image_of_a_function|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&nbsp;{{nowrap|(0, 1)}}).

==History==
In 1890, [[Giuseppe Peano]] discovered a continuous curve, now called the [[Peano curve]], that passes through every point of the unit square.{{sfn|Peano|1890}} His purpose was to construct a [[continuous mapping]] from the [[unit interval]]  onto the [[unit square]]. Peano was 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.  The problem Peano solved was whether such a mapping could be continuous; i.e., a curve that fills a space. Peano's solution does not set up a continuous [[one-to-one correspondence]] between the unit interval and the unit square, and indeed such a correspondence does not exist (see {{section link|#Properties}} below).

It was common to associate the vague notions of ''thinness'' and 1-dimensionality to curves; all normally encountered curves were [[piecewise]] 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]] (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 function|piecewise linear]] continuous curves, each one more closely approximating the space-filling limit.

Peano's ground-breaking article contained no illustrations of his construction, which is defined in terms of [[ternary expansion]]s and a [[mirroring operator]].  But the graphical construction was perfectly clear to him—he made an ornamental tiling showing a picture of the curve in his home in Turin.  Peano's article also ends by observing that the technique can be obviously extended to other odd bases besides base 3.  His choice to avoid any appeal to [[proof without words|graphical visualization]] was motivated by a desire for a completely rigorous proof owing nothing to pictures.  At that time (the beginning of the foundation of general topology), graphical arguments were still included in proofs, yet were becoming a hindrance to understanding often counterintuitive results.

A year later, [[David Hilbert]] published in the same journal a variation of Peano's construction.{{sfn|Hilbert|1891}} Hilbert's article was the first to include a picture helping to visualize the construction technique, essentially the same as illustrated here.  The analytic form of the [[Hilbert curve]], however, is more complicated than Peano's.

[[File:Hilbert curve.svg|400px|thumb|Six iterations of the Hilbert curve construction, whose limiting space-filling curve was devised by mathematician [[David Hilbert]].]]

== Outline of the construction of a space-filling curve ==
Let <math>\mathcal{C}</math> denote the [[Cantor space]] <math>\mathbf{2}^\mathbb{N}</math>.

We start with a continuous function <math>h</math> from the Cantor space <math>\mathcal{C}</math> onto the entire unit interval <math>[0,\, 1]</math>.  (The restriction of the [[Cantor function]] to the [[Cantor set]] is an example of such a function.)  From it, we get a continuous function <math>H</math> from the topological product <math>\mathcal{C} \;\times\; \mathcal{C}</math> onto the entire unit square <math>[0,\, 1] \;\times\; [0,\, 1]</math> by setting

<math display="block">H(x,y) = (h(x), h(y)). \, </math>

Since the Cantor set <math>\mathcal{C}</math> is [[homeomorphic]] to its cartesian product with itself <math>\mathcal{C} \times \mathcal{C}</math>, there is a continuous bijection <math>g</math> from the Cantor set onto <math>\mathcal{C} \;\times\; \mathcal{C}</math>. The composition <math>f</math> of <math>H</math> and <math>g</math> is a continuous function mapping the Cantor set onto the entire unit square.  (Alternatively, we could use the theorem that every [[compact set|compact]] metric space is a continuous image of the Cantor set to get the function <math>f</math>.)

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

== Properties ==
[[File:ComparingSFCurves-MortonHilbert1024.png|thumb|520px|[[Z-order curve|Morton]] and [[Hilbert curve|Hilbert]] curves of level 6 (4<sup>5</sup>=1024 cells in the [[Recursion (computer science)|recursive square partition]]) plotting each address as different color in the [[RGB color model|RGB standard]], and using [[Geohash]] labels. The neighborhoods have similar colors, but each curve offers different pattern of grouping similars in smaller scales.]]

If a curve is not injective, then one can find two intersecting ''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 (set theory)|intersection]] of the two images is [[Empty set|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.  However, 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]] from the unit interval onto the unit square (any continuous [[bijection]] from a [[compact space]] onto a [[Hausdorff space]] is a homeomorphism).  But a unit square has no [[cut-point]], and so cannot be homeomorphic to the unit interval, in which all points except the endpoints are cut-points. There exist non-self-intersecting curves of nonzero area, the [[Osgood curve]]s, but by [[Netto's theorem]] they are not space-filling.{{sfn|Sagan|1994|p=131}}

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 theory|knots]].  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 curves]].  No differentiable space-filling curve can exist. Roughly speaking, differentiability puts a bound on how fast the curve can turn. Michał Morayne proved that the [[continuum hypothesis]] is equivalent to the existence of a Peano curve such that at each point of the real line at least one of its components is differentiable.<ref>{{Cite journal |last=Morayne |first=Michał |date=1987 |title=On differentiability of Peano type functions |url=https://eudml.org/doc/264945 |journal=Colloquium Mathematicum |volume=53 |issue=1 |pages=129–132 |doi=10.4064/cm-53-1-129-132 |issn=0010-1354|doi-access=free }}</ref>

== The Hahn–Mazurkiewicz theorem ==
The [[Hans Hahn (mathematician)|Hahn]]–[[Stefan Mazurkiewicz|Mazurkiewicz]] theorem is the following characterization of spaces that are the continuous image of curves:

{{block indent|A non-empty [[Hausdorff space|Hausdorff]] topological space is a continuous image of the unit interval if and only if it is a compact, [[connected space|connected]], [[locally connected]], [[second-countable space]].}}

Spaces that are the continuous image of a unit interval are sometimes called ''Peano spaces''.

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 [[Pavel Samuilovich Urysohn|Urysohn]] [[metrization theorem]], second-countable then implies metrizable. Conversely, a compact metric space is second-countable.

==Kleinian groups==

There are many natural examples of space-filling, or rather sphere-filling, curves in the theory of doubly degenerate [[Kleinian group]]s. For example,
{{harvtxt|Cannon|Thurston|2007}} showed that the circle at infinity of the [[universal cover]] of a fiber of a [[mapping torus]] of a [[pseudo-Anosov map]] is a sphere-filling curve. (Here the sphere is the sphere at infinity of [[hyperbolic space|hyperbolic 3-space]].)

==Integration==

[[Norbert Wiener|Wiener]] pointed out in ''The Fourier Integral and Certain of its Applications'' that space-filling curves could be used to reduce [[Lebesgue integration]] in higher dimensions to Lebesgue integration in one dimension.

==See also==
{{Div col}}
* [[Dragon curve]]
* [[Gosper curve]]
* [[Hilbert curve]]
* [[Koch curve]]
* [[Moore curve]]
* [[Murray polygon]]
* [[Sierpiński curve]]
* [[Space-filling tree]]
* [[Spatial index]]
* [[Hilbert R-tree]]
* [[Bx-tree|''B''<sup>''x''</sup>-tree]]
* [[Z-order (curve)]] (Morton order)
* [[Cannon–Thurston map]]
* [[Self-avoiding walk]] (all SFC is)
* [[List of fractals by Hausdorff dimension]]
{{Div col end}}

==Notes==
{{reflist}}

==References==
* {{Citation | last1=Cannon | first1=James W. | last2=Thurston | first2=William P. | author2-link=William Thurston | title=Group invariant Peano curves | orig-year=1982 | doi=10.2140/gt.2007.11.1315 | mr=2326947 | year=2007 | journal=Geometry & Topology | issn=1465-3060 | volume=11 | issue=3 | pages=1315–1355| doi-access=free }}
* {{citation|first=D.|last=Hilbert|author-link=David Hilbert|url=http://www.digizeitschriften.de/dms/img/?PID=GDZPPN002253135|title=Ueber die stetige Abbildung einer Linie auf ein Flächenstück|journal=Mathematische Annalen|volume=38|issue=3|year=1891|pages=459–460|doi=10.1007/BF01199431|s2cid=123643081|language=de}}
* {{citation|first=B. B.|last=Mandelbrot|author-link=Benoît Mandelbrot|title=The Fractal Geometry of Nature|contribution=Ch. 7: Harnessing the Peano Monster Curves|publisher=W. H. Freeman|year=1982}}.
* {{citation|first=Douglas M.|last=McKenna|contribution=SquaRecurves, E-Tours, Eddies, and Frenzies: Basic Families of Peano Curves on the Square Grid|title=The Lighter Side of Mathematics: Proceedings of the Eugene Strens Memorial Conference on Recreational Mathematics and its History|publisher=[[Mathematical Association of America]]|year=1994|pages=[https://archive.org/details/lightersideofmat0000unse/page/49 49–73]|editor1-first=Richard K.|editor1-last=Guy|editor1-link=Richard K. Guy|editor2-first=Robert E.|editor2-last=Woodrow|isbn=978-0-88385-516-4|url=https://archive.org/details/lightersideofmat0000unse/page/49}}.
* {{citation|first=G.|last=Peano|author-link=Giuseppe Peano|url=http://www.digizeitschriften.de/dms/img/?PID=GDZPPN002252376|title=Sur une courbe, qui remplit toute une aire plane|journal=[[Mathematische Annalen]]|volume=36|issue=1|year=1890|pages=157–160|doi=10.1007/BF01199438|s2cid=179177780|language=fr}}.
* {{citation|first=Hans|last=Sagan|title=Space-Filling Curves|series=Universitext|publisher=Springer-Verlag|year=1994|isbn=0-387-94265-3|mr=1299533|doi=10.1007/978-1-4612-0871-6}}.

==External links==
{{Commons category|Space filling curves|Space-filling curves}}
* [http://people.csail.mit.edu/jaffer/Geometry/MDSFC Multidimensional Space-Filling Curves]
* [http://www.cut-the-knot.org/do_you_know/hilbert.shtml Proof of the existence of a bijection] at [[cut-the-knot]]

Java applets:
* [http://www.cut-the-knot.org/Curriculum/Geometry/Peano.shtml Peano Plane Filling Curves] at cut-the-knot
* [http://www.cut-the-knot.org/Curriculum/Geometry/PlaneFillingCurves.shtml Hilbert's and Moore's Plane Filling Curves] at cut-the-knot
* [http://www.cut-the-knot.org/Curriculum/Geometry/PeanoComplete.shtml All Peano Plane Filling Curves] at cut-the-knot

{{Fractals}}

[[Category:Theory of continuous functions]]
[[Category:Fractal curves]]
[[Category:Iterated function system fractals]]