Space-filling curve

From Academic Kids

Space-filling curves or Peano curves are curves, first described by Giuseppe Peano, 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)).

Space-filling curves are curves whose ranges contain the entire 2-dimensional unit square (or the 3-dimensional unit cube). 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.

Missing image
Hilbert_curve.png
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 counter-intuitive.

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

Contents

1 Literature
2 See also
3 External links

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> H(x,y) = (h(x),h(y)) <math>

Since the Cantor set is homeomorphic to the product <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 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>).

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.

Literature

  • Hans Sagan, Space-Filling Curves, Springer-Verlag 1994

See also

External links

Navigation

Academic Kids Menu

  • Art and Cultures
    • Art (http://www.academickids.com/encyclopedia/index.php/Art)
    • Architecture (http://www.academickids.com/encyclopedia/index.php/Architecture)
    • Cultures (http://www.academickids.com/encyclopedia/index.php/Cultures)
    • Music (http://www.academickids.com/encyclopedia/index.php/Music)
    • Musical Instruments (http://academickids.com/encyclopedia/index.php/List_of_musical_instruments)
  • Biographies (http://www.academickids.com/encyclopedia/index.php/Biographies)
  • Clipart (http://www.academickids.com/encyclopedia/index.php/Clipart)
  • Geography (http://www.academickids.com/encyclopedia/index.php/Geography)
    • Countries of the World (http://www.academickids.com/encyclopedia/index.php/Countries)
    • Maps (http://www.academickids.com/encyclopedia/index.php/Maps)
    • Flags (http://www.academickids.com/encyclopedia/index.php/Flags)
    • Continents (http://www.academickids.com/encyclopedia/index.php/Continents)
  • History (http://www.academickids.com/encyclopedia/index.php/History)
    • Ancient Civilizations (http://www.academickids.com/encyclopedia/index.php/Ancient_Civilizations)
    • Industrial Revolution (http://www.academickids.com/encyclopedia/index.php/Industrial_Revolution)
    • Middle Ages (http://www.academickids.com/encyclopedia/index.php/Middle_Ages)
    • Prehistory (http://www.academickids.com/encyclopedia/index.php/Prehistory)
    • Renaissance (http://www.academickids.com/encyclopedia/index.php/Renaissance)
    • Timelines (http://www.academickids.com/encyclopedia/index.php/Timelines)
    • United States (http://www.academickids.com/encyclopedia/index.php/United_States)
    • Wars (http://www.academickids.com/encyclopedia/index.php/Wars)
    • World History (http://www.academickids.com/encyclopedia/index.php/History_of_the_world)
  • Human Body (http://www.academickids.com/encyclopedia/index.php/Human_Body)
  • Mathematics (http://www.academickids.com/encyclopedia/index.php/Mathematics)
  • Reference (http://www.academickids.com/encyclopedia/index.php/Reference)
  • Science (http://www.academickids.com/encyclopedia/index.php/Science)
    • Animals (http://www.academickids.com/encyclopedia/index.php/Animals)
    • Aviation (http://www.academickids.com/encyclopedia/index.php/Aviation)
    • Dinosaurs (http://www.academickids.com/encyclopedia/index.php/Dinosaurs)
    • Earth (http://www.academickids.com/encyclopedia/index.php/Earth)
    • Inventions (http://www.academickids.com/encyclopedia/index.php/Inventions)
    • Physical Science (http://www.academickids.com/encyclopedia/index.php/Physical_Science)
    • Plants (http://www.academickids.com/encyclopedia/index.php/Plants)
    • Scientists (http://www.academickids.com/encyclopedia/index.php/Scientists)
  • Social Studies (http://www.academickids.com/encyclopedia/index.php/Social_Studies)
    • Anthropology (http://www.academickids.com/encyclopedia/index.php/Anthropology)
    • Economics (http://www.academickids.com/encyclopedia/index.php/Economics)
    • Government (http://www.academickids.com/encyclopedia/index.php/Government)
    • Religion (http://www.academickids.com/encyclopedia/index.php/Religion)
    • Holidays (http://www.academickids.com/encyclopedia/index.php/Holidays)
  • Space and Astronomy
    • Solar System (http://www.academickids.com/encyclopedia/index.php/Solar_System)
    • Planets (http://www.academickids.com/encyclopedia/index.php/Planets)
  • Sports (http://www.academickids.com/encyclopedia/index.php/Sports)
  • Timelines (http://www.academickids.com/encyclopedia/index.php/Timelines)
  • Weather (http://www.academickids.com/encyclopedia/index.php/Weather)
  • US States (http://www.academickids.com/encyclopedia/index.php/US_States)

Information

  • Home Page (http://academickids.com/encyclopedia/index.php)
  • Contact Us (http://www.academickids.com/encyclopedia/index.php/Contactus)

  • Clip Art (http://classroomclipart.com)
Toolbox
Personal tools