to do:

- Turtle animation, interval mapping animation (should help w/ understanding) - Crude application to TSP - Signal processing - Cannon Thurston maps

- Can have differentiability almost everywhere (surprising indeed) - Hahn-M.. theorem also applies to Frechet spaces (Sagan 108) - Contextualizing Osgood curves and why they are materially different

Space-filling curve edit

The first six iterations in the construction of the Hilbert curve, an archetypal space-filling curve. The Hilbert curve itself is the limit of this series of curves and passes through every point in the unit square.

In mathematics, especially the field of general topology, a space-filling curve (among other names) is a curve which completely fills up some topological space. Often, this space is taken to be the unit square, unit cube, or unit hypercube.

A mathematical curve has a very general definition: a continuous function from the unit interval into a given space. For example, if that space is the plane, then the curve is a plane curve. A curve's behavior may defy intuition; it can intersect itself infinitely many times, have infinite length, or even have positive area. The existence of space-filling curves, then, was a great surprise to late nineteenth-century mathematicians. The first known example, the Peano curve, was constructed by Italian mathematician Giuseppe Peano in 1890, although his construction was entirely abstract and included no illustrations. A geometric interpretation of the Peano curve was soon realized, and space-filling curves in general are now easily visualized using computers.

Space-filling curves are often constructed as the limit of a series of more well-behaved curves which become increasingly squiggly and dense in the unit square (or whatever chosen space). For a suitable choice of curves, the result is a curve which passes through every point in the space; in other words, every point in the space has some number between 0 and 1 (inclusive) which maps to it. For the unit square and cube, it is a theorem that this mapping cannot be a one-to-one correspondence—there will always be points in the square or cube with multiple numbers mapping to it, essentially a place where the curve touches itself. In fact, there are infinitely many such points. The curve also has no well-defined length and cannot be everywhere-differentiable.

Despite their infinite nature, space-filling curves and their brethren have applications in computer science. Their power lies in reducing n-dimensional data into one-dimensional data with good locality, the property that points close in the input space will also be close in the output space. They also may be used in machining as the path of a miller removing a large section of material.

Background edit

A plane curve is defined as a continuous function mapping the unit interval $[0,1]$ into the plane (denoted $\mathbb {R} ^{2}$ ). For example, the unit circle, given by $f(t)=\langle \cos 2\pi t,\sin 2\pi t\rangle$ , is a plane curve: It is continuous, having no sudden jumps, and takes numbers in the unit interval to points in the plane. But, unlike a circle, a general plane curve may exhibit unusual or unintuitive behavior: It may retrace itself (perhaps infinitely many times), have infinite length, or even have positive area. Among these "pathological" curves are the space-filling plane curves.

In mathematics, two sets are the same size if there exists a one-to-one correspondence (a bijection) between them. For example, $S_{1}=\{0,1,2\}$ and $S_{2}=\{3,4,5\}$ have the same size because there exists the correspondence $0\leftrightarrow 3$ , $1\leftrightarrow 4$ , $2\leftrightarrow 5$ , but neither set is the same size as $S_{3}=\{0,1,2,3\}$ , because $S_{3}$ will always have an element left unpaired. This definition naturally generalizes to infinite sets, such as the set of real numbers. It is a highly counterintuitive fact—only first understood in the late–nineteenth century—that the unit interval $[0,1]$ has the same number of points as the unit square $[0,1]^{2}$ : There exists a bijection between them.^[a] In other words (somewhat loosely speaking), a line segment has the same number of points as a square.

History edit

The first few iterates leading to the Peano curve, the first known space-filling curve. Ultimately, the curve passes through every point of the unit square.

The existence of a bijection between $[0,1]$ and $[0,1]^{2}$ was established by German set theorist Georg Cantor in his 1878 paper "Ein Beitrag zur Mannigfaltigkeitslehre", a followup to his influential first set theory article (published 1874).^[1]^[2] Cantor's bijection was not continuous, prompting the search of a continuous bijection between the sets. Only a year later, German mathematician Eugen Netto proved such a bijection could not exist,^[3] and attention turned to finding a continuous surjection (which allows two inputs to map to the same output point).^[4]

In 1890, Italian mathematician Giuseppe Peano found the Peano curve, the first known space-filling curve.^[5]^[4] Peano's construction was entirely analytic, making no reference to geometry and including no illustrations. The curve can be visualized, however, as the limit of a set of curves (see User:Ovinus/sandbox2 § Peano curve).^[5] In 1891, the German mathematician David Hilbert not only made Peano's curve "luminous to the geometric imagination"^[6] in this way, but also constructed his own curve, known as the Hilbert curve, and really a general geometric process to construct a whole class of space-filling curves.^[7]

More space-filling curves were constructed by E. H. Moore (in 1900, really a minor alteration of Hilbert's curve), Henri Lebesgue (1904), Wacław Sierpiński (1912), George Pólya (1913), and Bill Gosper (1973).

Definition edit

A space-filling curve in n-dimensional space is a curve whose range completely fills the unit n-hypercube. For n=2, the curve fills the unit square and is called a plane-filling curve or surface-filling curve. Space-filling curves are sometimes called space-filling functions to distance them from the colloquial understanding of a curve, or called Peano curves after their primary discoverer. Often space-filling curves are constructed as the limit of a sequence of well-behaved curves, but the space-filling curve itself is only the limit function.

The choice of the unit square or cube is arbitrary, and so this definition is easily generalized: Sagan (1994) defines a space-filling curve as a curve in $n$ -dimensional space ( $n\geq 2$ ) with positive Jordan content (a precise notion of area, volume, and so forth—the unit hypercube has Jordan content 1). In general, a space-filling curve is simply a curve which completely fills some topological space. The spaces for which such a curve exists are characterized completely by the Hahn–Marurkiewicz theorem. Unless otherwise noted, this article uses the unit-hypercube convention.

Examples edit

Space-filling curves have various definitions and constructions. Most commonly, a space-filling curve is constructed as the limit of a set of better-behaved functions that become increasingly dense and squiggly within the unit square (or cube, hypercube, and so forth). Some, such as the Lebesgue and Peano curves, have relatively easy analytic forms—that is, explicit formulas, rather than a definition appealing to geometric intuition. Many of these curves can be constructed using a Lindenmayer system (see Hilbert curve § Notes for a simpler example).

The intervals

[(a-1)/9,a/9]

map into the labeled squares (

a=1,2,...,9

). The blue line indicates the order of the squares—not the curve itself.

Peano curve edit

The two-dimensional Peano curve, as Peano's original paper expounded,^[5] has a particularly compact formula, using ternary (base-3 arithmetic). Let $k(d)=2-d$ be an operator taking in a ternary digit (one of $\{0,1,2\}$ ) and outputting a ternary digit, and let $k^{n}(d)=k(k(\cdots k(d)))$ be the result of iterating $k$ on $d$ , $n$ times. For example, $k(0)=2$ and $k^{2}(0)=0$ . Then, letting the input $t$ be written in ternary as $0_{3}t_{1}t_{2}t_{3}t_{4}...$ ,

$f_{\text{peano}}(t)={\begin{bmatrix}0_{3}t_{1}(k^{t_{2}}(t_{3}))(k^{t_{2}+t_{4}}(t_{5}))(k^{t_{2}+t_{4}+t_{6}}(t_{5}))...\\0_{3}(k^{t_{1}}(t_{2}))(k^{t_{1}+t_{3}}(t_{4}))(k^{t_{1}+t_{3}+t_{5}}(t_{6}))...\end{bmatrix}},$ ^[8]

where the outermost parentheses group the ternary digits of the output. For example,

$f_{\text{peano}}(1/6)=f_{\text{peano}}(0_{3}0111...)={\begin{bmatrix}0_{3}0(k^{1}(1))(k^{1+1}(1))...\\0_{3}(k^{0}(1))(k^{0+1}(1))...\end{bmatrix}}={\begin{bmatrix}0_{3}0111...\\0_{3}1111...\end{bmatrix}}={\begin{bmatrix}1/6\\1/2\end{bmatrix}}.$

It turns out that, although some numbers have multiple equivalent ternary expansions (see 0.999... = 1), $f_{\text{peano}}$ is independent of the chosen representation and is thus well-defined. Given the ternary expansions of the coordinates of a point in the unit square, this function may be undone (working digit by digit), showing that it is surjective.^[b] The function can also be shown to be everywhere continuous, and together, these two properties make the Peano curve a space-filling curve.^[9] Higher-dimensional Peano curves may be obtained in a similar fashion.^[10]^[11] Other, equivalent, analytic representations of the Peano curve also exist, as do related curves with a similar construction based on ternary expansions.^[12]

Peano's analytic construction may be understood geometrically by observing what happens to different intervals of the input. Intervals of the form $[(a-1)/3^{2n},a/3^{2n}]$ , where $a=1,2,...,3^{2n}$ , map to squares in a specific order such that successive values of $a$ give consecutive squares.^[c] As $n$ goes to infinity, the curve is obtained.^[13]

The Peano curve and its higher-dimensional generalizations are nowhere differentiable.^[14] Their coordinate functions, each distributed uniformly in $[0,1]$ , are not even $q$ -Hölder continuous for any $q>1/n$ .^[11]

Hilbert curve edit

The iterations leading to the Hilbert curve are done in pieces.

The Hilbert curve is usually constructed geometrically, as the limit of a sequence of curves. Begin with a grid of four squares and a curve, composed of three line segments, through their centers. Repeatedly subdivide each square into four pieces and draw a curve between their centers, with four possible orientations, depending on how the curve enters that square. At step $n$ . there are thus $4^{n}$ squares, all of whose centers are connected. In the limit, this process yields the Hilbert curve.^[7]

The Hilbert curve is easier to understand geometrically than the Peano curve, but its analytic forms are gruesome and unilluminating. Sagan (1994) gives an explicit form as a complex-valued function.^[15] There do exist much simpler constructions, such as a recursive approach or a turtle graphics–based Lindenmayer system (L-system).^[16]^[d] An L-system is a formal language combined with a set of production rules which allow the production of some set of strings, which are often fractal-like. Let the symbols be $L$ , $R$ , $F$ , $-$ , and $+$ . Then, beginning with the string $L$ , repeatedly apply the transformations

L\to {+}RF{-}LFL{-}FR{+}

;

R\to {-}LF{+}RFR{+}FL{-}.

A "turtle" can then mechanically follow the resulting string, where $L$ is a left-turn by 90 degrees, $R$ is a right turn, $F$ is a move forward by a distance $k$ , and $-/+$ have no physical interpretation. Beginning with $k=1$ and halving $k$ at each step (so that the path fits in the unit square), the turtle's path approaches the Hilbert curve.

Unlike the Peano curve, the Hilbert curve has many distinct natural generalizations into higher dimensions, depending on what properties are desired, because many different connection schemes between the eight subcubes may be chosen.^[17]

The Hilbert curve and its higher-dimensional analogues are nowhere differentiable.^[18]

Lebesgue curve edit

Others edit

- Sierpinski, Gosper

Properties edit

Space-filling curves are non-rectifiable, meaning they cannot be assigned a meaningful finite length.^{[proof 1]} They are non-differentiable at an infinite set of points, and so are only in the $C^{0}$ class of functions (see smoothness). This set of points need not be dense;

A space-filling curve into the unit square cannot be injective. That is, it cannot associate each point in the output with a unique value in $[0,1]$ ; there will always be collisions.^{[proof 2]} In fact, more can be said: The set of points for which the curve fails to be injective is dense in the output space. Consider the Peano construction's sequence of curves, for instance; the points on "adjacent" horizontal and vertical segments get closer and closer, and therefore coincide in the limit. Every point with dyadic rational coordinates—that is, points of the form $(a/2^{n},b/2^{m})$ —can be reached in more than one way. It is possible, however, to have injective curves that have positive area (in the sense of Lebesgue measure). These are the Osgood curves, which are not truly space-filling curves. Further, their Jordan content is undefined.

Because they completely fill an open set, space-filling curves in n-dimensional space have fractal dimension $n$ .

Although many space-filling curves exhibit self-similarity at arbitrarily small scales, they are not truly fractals, which are characterized by having a non-integer fractal dimension. The image of a curve filling the unit square, for example, is the square itself, and thus has Hausdorff dimension 2.^[19]^[20] An example of a true fractal curve includes the Koch snowflake, which has a Hausdorff dimension of about 1.262.

Hahn–Mazurkiewicz theorem edit

The Hahn–Mazurkiewicz theorem, discovered by Hans Hahn and Stefan Mazurkiewicz, completely characterizes the spaces in which space-filling curves exist:

A non-empty Hausdorff topological space is a continuous image of the unit interval if and only if it is compact, connected, locally connected, and metrizable.^[21] (Such spaces are called Peano spaces.)^[22]

For example, the unit square satisfies all these requirements, but the real plane $\mathbb {R} ^{2}$ does not (it is not compact), and thus cannot be filled with a space-filling curve. (There does exist, however, a continuous surjection $\mathbb {R} \to \mathbb {R} ^{2}$ .)

(Maybe mention the proof, which uses the fact that any compact set is a continuous image of the Cantor set)

Generalization: https://www.ams.org/journals/proc/1976-058-01/S0002-9939-1976-0413063-0/S0002-9939-1976-0413063-0.pdf

Applications edit

Despite their counterintuitive and infinite nature, space-filling curves have important applications outside of mathematics, including routing problems, locality-sensitive hashing, and other algorithms.

- Video encoding/compression ideas - Routing problems

Hashing edit

- Z-order/Morton curve stuff - Hilbert curve probably used somewhere

A formal construction edit

- Probably either Peano (which only references ternary arithmetic, really) or Lebesgue (which requires the Cantor set)

Notes and references edit

Notes edit

^ More specifically, they both have the cardinality of the continuum, denoted ${\mathfrak {c}}$ . Such a bijection is generally misbehaved, and in particular cannot be continuous, as is later discussed.
^ The failure of $f_{\text{peano}}$ to be injective comes from the fact that there may be more than one choice of digit at some step.
^ For example, the interval $[0,1/9]$ maps entirely into the square $[0,1/3]\times [0,1/3]$ , and the interval $[1/9,2/9]$ into the square $[0,1/3]\times [1/3,2/3]$ .
^ A recursive construction is given in Breinholt & Schierz (1998). A construction of the intermediate curves by connecting polygons inscribed within tiles is given in Prusinkiewicz, Lindemayer & Fracchia (1991). An algorithm based on the binary representation of the input is given in Butz (1971).

Proofs

^ For any fixed $n$ , a space-filling curve passes through every point in the unit square of the form $(a/n,b/n)$ . But the distance between two of these points is at least $1/n$ . Thus, the length of the curve is at least $n^{2}\cdot (1/n)$ , which tends to infinity.
^ A continuous bijection from a compact space into a Hausdorff space (which $[0,1]$ and $[0,1]^{2}$ are, respectively) is necessarily a homeomorphism. If a bijective space-filling curve existed, then would construct a homeomorphism between the unit interval and the unit square, which does not exist—while the unit interval has an infinite number of cut points, the unit square has none.