User:Ovinus/sandbox2
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]![Six curves inside squares that get increasingly squiggly](http://upload.wikimedia.org/wikipedia/commons/3/3a/Hilbert_curve.png)
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 into the plane (denoted ). For example, the unit circle, given by , 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, and have the same size because there exists the correspondence ,, , but neither set is the same size as , because 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 has the same number of points as the unit square : 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]![Four curves, each becoming more squiggly](http://upload.wikimedia.org/wikipedia/commons/thumb/5/58/Peano_curve.png/220px-Peano_curve.png)
The existence of a bijection between and 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 -dimensional space () 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 {{Section link}}: required section parameter(s) missing for a simpler example).
![Nine squares in a 3x3 grid, labeled 1 through 9 in the following order from top left to bottom right: 3, 4, 9, 2, 5, 8, 1, 6, 7.](http://upload.wikimedia.org/wikipedia/commons/thumb/9/9e/Peano_curve_square_order.svg/220px-Peano_curve_square_order.svg.png)
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 be an operator taking in a ternary digit (one of ) and outputting a ternary digit, and let be the result of iterating on , times. For example, and . Then, letting the input be written in ternary as ,
where the outermost parentheses group the ternary digits of the output. For example,
It turns out that, although some numbers have multiple equivalent ternary expansions (see 0.999... = 1), 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 , where , map to squares in a specific order such that successive values of give consecutive squares.[c] As 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 , are not even -Hölder continuous for any .[11]
Hilbert curve
[edit]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 . there are thus 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 , , , , and . Then, beginning with the string , repeatedly apply the transformations
- ;
A "turtle" can then mechanically follow the resulting string, where is a left-turn by 90 degrees, is a right turn, is a move forward by a distance , and have no physical interpretation. Beginning with and halving 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 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 ; 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 —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 .
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 does not (it is not compact), and thus cannot be filled with a space-filling curve. (There does exist, however, a continuous surjection .)
(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 . Such a bijection is generally misbehaved, and in particular cannot be continuous, as is later discussed.
- ^ The failure of to be injective comes from the fact that there may be more than one choice of digit at some step.
- ^ For example, the interval maps entirely into the square , and the interval into the square .
- ^ 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 , a space-filling curve passes through every point in the unit square of the form . But the distance between two of these points is at least . Thus, the length of the curve is at least , which tends to infinity.
- ^ A continuous bijection from a compact space into a Hausdorff space (which and 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.
References and citations
[edit]- ^ Johnson, Phillip E. (1972). "The Genesis and Development of Set Theory". The Two-Year College Mathematics Journal. 3 (1): 55. doi:10.2307/3026799. ISSN 0049-4925.
- ^ Cantor, Georg (1878). "Ein Beitrag zur Mannigfaltigkeitslehre". Crelle's Journal (in German). 1878 (84). Walter de Gruyter: 242–258. doi:10.1515/crelle-1878-18788413. ISSN 0075-4102. Retrieved 2 June 2022.
- ^ Netto, Eugen (1879-01-01). "Beitrag zur Mannigfaltigkeitslehre". Crelle's Journal (in German). 1879 (86): 263–268. doi:10.1515/crll.1879.86.263. ISSN 0075-4102.
- ^ a b Sagan 1994, p. 1.
- ^ a b c Peano, Giuseppe (1980). "Sur une courbe, qui remplit toute une aire plane". Mathematische Annalen (in French). 36 (1): 157–160. doi:10.1007/BF01199438. ISSN 1432-1807.
- ^ Moore 1900, p. 73.
- ^ a b Sagan 1994, p. 10.
- ^ Sagan 1994, pp. 31–32.
- ^ Sagan 1994, p. 32–33.
- ^ Sagan 1994, p. 45–46.
- ^ a b de Freitas, Joaquim E.; de Lima, Ronaldo F.; dos Santos, Daniel T. (2019-12-01). "The n-dimensional Peano Curve". São Paulo Journal of Mathematical Sciences. 13 (2): 678–688. arXiv:1812.00766. doi:10.1007/s40863-019-00132-9. ISSN 2316-9028.
- ^ Sagan 1994, p. 40.
- ^ Sagan 1994, p. 35.
- ^ Sagan 1994, p. 34.
- ^ Sagan 1994, p. 13.
- ^ Breinholt & Schierz 1998.
- ^ Alber, J.; Niedermeier, R. (1 August 2000). "On Multidimensional Curves with Hilbert Property". Theory of Computing Systems. 33 (4): 295–312. doi:10.1007/s002240010003. ISSN 1433-0490.
- ^ Sagan 1994, p. 19.
- ^ Sagan 1994, p. 159.
- ^ Hayes 2017.
- ^ Willard 1970, p. 221.
- ^ Hocking, John G. (1961). Topology. Reading, Massachusetts: Addison-Wesley. p. 129. ISBN 978-0486656762. Retrieved 4 June 2022.
Works cited
[edit]- Sagan, Hans (1994). Space-Filling Curves (N ed.). New York: Springer New York. ISBN 978-1-4612-0871-6.
- Willard, Stephen (1970). General Topology. Reading, Massachusetts: Addison-Wesley. ISBN 9780486434797.
- Moore, Eliakim Hastings (1900). "On certain crinkly curves" (PDF). Transactions of the American Mathematical Society. 1 (1): 72–90.
- Breinholt, Greg; Schierz, Christoph (June 1998). "Algorithm 781: generating Hilbert's space-filling curve by recursion". ACM Transactions on Mathematical Software. 24 (2): 184–189. doi:10.1145/290200.290219.
- Prusinkiewicz, Przemyslaw; Lindemayer, Aristid; Fracchia, F. David (1991). Fractals in the fundamental and applied sciences : proceedings of the first IFIP Conference on Fractals in the Fundamental and Applied Sciences, Lisbon, Portugal, 6-8 June, 1990 (PDF). Amsterdam: Elsevier Science. pp. 341–360. ISBN 978-0444887573. Retrieved 8 June 2022.
- Butz, A.R. (April 1971). "Alternative Algorithm for Hilbert's Space-Filling Curve" (PDF). IEEE Transactions on Computers. C-20 (4): 424–426. doi:10.1109/T-C.1971.223258. Retrieved 8 June 2022.
- Hayes, Brian (6 February 2017). "Crinkly Curves". American Scientist. Retrieved 12 June 2022.
https://arxiv.org/pdf/1109.2323.pdf
https://people.math.harvard.edu/~kupers/notes/spacefillingfunctions.pdf
https://link.springer.com/chapter/10.1007/978-3-540-71121-6_4?noAccess=true
Space-Filling Curves: An Introduction with Applications in Scientific Computing
https://par.nsf.gov/servlets/purl/10166539
http://algorithmicbotany.org/papers/ffas-synthesis-of-spacing-filling-curves-on-the-square-grid.pdf
Velho, L., and J. de Miranda Gomes. 1991. Digital halftoning with space filling curves. Computer Graphics 25(4):81–90.
Gardner, M. 1976. Mathematical games: In which “monster” curves force redefinition of the word “curve.” Scientific American 235:124–133.
http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.302.9&rep=rep1&type=pdf
https://www.cut-the-knot.org/do_you_know/hilbert.shtml
http://theory.stanford.edu/~matias/papers/eg2000.pdf
http://www.cs.cmu.edu/~christos/PUBLICATIONS/ieee-tkde-hilbert.pdf
https://www.fs.usda.gov/treesearch/pubs/13672
https://ieeexplore.ieee.org/document/499920
Singular homology groups of Peano spaces http://www.logic.info.waseda.ac.jp/~eda/pdf/singular.pdf
TSP: https://www2.isye.gatech.edu/~jjb/research/mow/mow.html
Maybe Munkres has something
"Space-Filling Curves: An Introduction with Applications in Scientific Computing"