Space-Filling Curve - Sarcasm Wiki

Contents

1. Overview
2. Etymology
3. Cultural Impact

Curve whose range contains the unit square

Three iterations of the Peano curve construction, whose limit is a space-filling curve.

In the esoteric realm of mathematical analysis , a space-filling curve stands as a monument to counter-intuition: a curve whose range is so expansive, so utterly pervasive, that it manages to touch, or rather occupy, every single point within a higher-dimensional region. Most frequently, this region is the unassuming unit square in two dimensions, though its reach extends to the more generalized n-dimensional unit hypercube . This concept, once considered an impossibility by many, was first unveiled by Giuseppe Peano (1858–1932) in 1890. Consequently, space-filling curves that manifest within the 2-dimensional plane are occasionally referred to as Peano curves. It’s a slightly unhelpful nomenclature, as that very phrase also specifically designates the original, particular example of a space-filling curve that Peano himself unearthed.

There exist, as if to further complicate matters, the closely related FASS curves. “FASS,” for those who enjoy acronyms, stands for “approximately space-Filling, self-Avoiding, Simple, and Self-similar” curves. These can be conceptually understood as finite, practical approximations of specific types of space-filling curves, offering a somewhat more tractable, if less mind-bending, glimpse into their properties.

Definition

One might, in a moment of naive intuition, imagine a curve in two, three, or even higher dimensions as merely the trajectory of a point moving continuously through space. However, such a notion, while evocative, is riddled with inherent vagueness – a cardinal sin in mathematics. To rectify this perceived sloppiness, Camille Jordan (1838–1922) provided, in 1887, a definition of exquisite rigor, which has since been universally embraced as the precise, unassailable description of what a curve actually is:

A curve (complete with its designated endpoints, because details matter) is formally defined as a continuous function whose domain is the humble unit interval [0, 1].

In its most abstract and generalized form, the range of such a function could, theoretically, reside within any arbitrary topological space . However, for the purposes of more grounded, commonly investigated scenarios, this range typically lies within a familiar Euclidean space . This means we’re often dealing with the 2-dimensional plane, yielding a planar curve, or the 3-dimensional space, giving us a space curve.

It is worth noting that, occasionally, the term “curve” is used somewhat loosely to refer to the image of the function—that is, the actual set of all possible points the function can attain—rather than the function itself. Furthermore, it’s entirely possible to define curves that lack the convenience of endpoints, by simply extending the domain of the continuous function to the entire real line or, perhaps, the open unit interval (0, 1). Because, apparently, boundaries are for the faint of heart.

History

In a move that undoubtedly sent ripples of disbelief through the mathematical community, Giuseppe Peano , in 1890, presented a continuous curve—the one now eponymously known as the Peano curve —that possessed the astonishing property of passing through every single point of the unit square. His motivation, as is often the case with such groundbreaking discoveries, was not born of idle curiosity but a specific challenge: to construct a continuous mapping that could project the 1-dimensional unit interval onto the 2-dimensional unit square . Peano was spurred on by the earlier, equally unsettling, findings of Georg Cantor , who had demonstrated that the infinite number of points contained within a unit interval possessed the exact same cardinality as the infinite number of points found in any finite-dimensional manifold , including, crucially, the unit square. Cantor’s result proved that a one-to-one correspondence existed between these seemingly disparate sets of points. Peano’s subsequent problem was to determine if such a mapping could additionally be continuous—that is, if a curve could truly “fill” a space. Peano’s ingenious solution did indeed provide a continuous mapping, but it did not establish a continuous one-to-one correspondence between the unit interval and the unit square. Such a correspondence, as we now understand, simply does not exist (a fact explored further in the “Properties” section below).

Prior to Peano’s revelation, it was conventional, and frankly, quite comfortable, to associate curves with vague notions of “thinness” and intrinsic 1-dimensionality. After all, nearly all curves encountered in practical or theoretical contexts were piecewise differentiable—meaning they possessed piecewise continuous derivatives—and it was self-evident that such curves could not possibly occupy an entire unit square. Thus, Peano’s space-filling curve was perceived as profoundly, almost offensively, counterintuitive. It shattered established preconceptions with the elegance of a mathematical truth.

Following Peano’s initial, groundbreaking example, it became a relatively straightforward exercise to derive other continuous curves whose ranges encompassed the n-dimensional hypercube for any positive integer n. The technique was also readily adaptable to construct continuous curves without endpoints, which could, with similar audacity, fill the entirety of n-dimensional Euclidean space , whether n was 2, 3, or any other positive integer.

Most of the space-filling curves that have achieved widespread recognition are constructed through an iterative process. They emerge as the limit of a sequence of piecewise linear continuous curves, each successive iteration providing a closer, more intricate approximation of the ultimate space-filling limit. It’s like watching chaos slowly coalesce into order, or perhaps, order dissolving into chaos, depending on your perspective.

Peano’s seminal article, a testament to pure mathematical rigor, notably contained no graphical illustrations of his construction. His definition relied entirely on ternary expansions and a mirroring operator, a stark contrast to the visual aids often employed to demystify complex concepts. Yet, the graphical construction was perfectly clear in his own mind; he even created an ornamental tiling in his Turin home that depicted the curve. His article concludes with the observation that his technique could be effortlessly extended to other odd bases beyond base 3. Peano’s deliberate avoidance of any appeal to graphical visualization was a conscious choice, driven by a profound desire for a proof that was entirely rigorous, owing absolutely nothing to potentially misleading pictures. In that era, the nascent stages of general topology, graphical arguments, while still prevalent, were increasingly recognized as potential impediments to understanding the often counterintuitive results that were beginning to emerge.

A mere year later, David Hilbert published his own variation of Peano’s construction in the same journal. Hilbert’s article distinguished itself by being the first to include a visual representation, a picture that significantly aided in conceptualizing the construction technique—essentially the same approach illustrated here. However, the analytic formulation of the Hilbert curve proved to be considerably more intricate than Peano’s original. Because, of course, simplicity is rarely a primary objective when one is busy reshaping mathematical understanding.

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

Constructing a space-filling curve is not for the faint of heart, but rather for those who appreciate the intricate dance between sets and functions. Let’s outline the general approach, which is a rather elegant, if somewhat convoluted, journey through abstract spaces.

We begin by letting ({\mathcal {C}}) denote the Cantor space , which is formally represented as ({\mathbf {2} ^{\mathbb {N} }}).

The first step requires a continuous function, let’s call it (h), which maps from this Cantor space ({\mathcal {C}}) onto the entirety of the unit interval ([0,,1]). For those seeking a concrete example, the restriction of the well-known Cantor function to the Cantor set serves as a perfect illustration of such a function. From this initial mapping, we then derive a new continuous function, (H), which takes us from the topological product ({\mathcal {C}};\times ;{\mathcal {C}}) (essentially, two copies of the Cantor space combined) onto the entire unit square ([0,,1];\times ;[0,,1]). This is achieved by the straightforward definition: $$H(x,y)=(h(x),h(y)).,$$

Now, a rather convenient property of the Cantor set is that it is homeomorphic to its own cartesian product with itself, ({\mathcal {C}}\times {\mathcal {C}}). This means there exists a continuous bijection , let’s denote it (g), which maps the Cantor set directly onto ({\mathcal {C}};\times ;{\mathcal {C}}). With (H) and (g) in hand, we can then form their composition, creating a function (f). This function (f) is continuous and maps the Cantor set onto the entire unit square . (Alternatively, one could bypass some of these intermediate steps by directly invoking the powerful theorem which states that every compact metric space is a continuous image of the Cantor set , thereby directly obtaining the function (f).)

Finally, having established (f) as a continuous function from the Cantor set to the unit square, the ultimate goal is to extend this function to a continuous function, (F), whose domain encompasses the entire unit interval ([0,,1]). This extension can be accomplished through a couple of methods. One approach involves applying the Tietze extension theorem to each individual component of (f). A more intuitively appealing, though no less rigorous, method is to extend (f) “linearly.” This means that for each of the open intervals ((a,,b)) that were deleted during the construction of the Cantor set , we define the extended portion of (F) on ((a,,b)) to be the straight line segment within the unit square that connects the values (f(a)) and (f(b)). And there you have it: a continuous function, born from abstract spaces, that manages to touch every single point in a higher dimension. Because, apparently, simple paths are just too dull.

Properties

Morton and Hilbert curves of level 6 (4^5 = 1024 cells in the recursive square partition ) plotting each address as different color in the 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 —that is, if different points in its domain can map to the same point in its range—then one can invariably find two intersecting subcurves. These subcurves are obtained by considering the images of two distinct, disjoint segments from the curve’s domain (which is typically the unit line segment). The two subcurves are said to “intersect” if the intersection of their respective images is non-empty . One might be tempted, in a moment of common sense, to assume that “intersecting” necessarily implies a dramatic crossing, much like two non-parallel lines meeting at a distinct point. However, this is mathematics, and such straightforward interpretations are often too pedestrian. Two curves (or two subcurves of a single curve) may merely contact one another without actually crossing, as elegantly demonstrated by a line that is precisely tangent to a circle.

A continuous curve that is non-self-intersecting (i.e., injective ) fundamentally cannot fill the unit square . The reason for this lies in the realm of topology . If such a curve were to fill the unit square, it would imply that the curve constitutes a homeomorphism from the unit interval onto the unit square. This is because any continuous bijection from a compact space to a Hausdorff space is, by definition, a homeomorphism. However, the unit square lacks any cut-point —a point whose removal disconnects the space. Conversely, the unit interval is replete with cut-points; every point within it, save for the two endpoints, acts as one. Since a homeomorphism preserves topological properties like the existence of cut-points, and the unit square possesses none while the unit interval has many, it follows that they cannot be homeomorphic. Thus, a non-self-intersecting continuous curve is simply incapable of filling the unit square. Though, it must be noted that there exist non-self-intersecting curves that do possess a nonzero area, such as the Osgood curves , but by Netto’s theorem , these are definitively not space-filling.

For the classic Peano and Hilbert space-filling curves , where two subcurves “intersect” in the precise, technical sense, what occurs is typically self-contact rather than a dramatic self-crossing. It’s a subtle distinction, but crucial. Furthermore, a space-filling curve can be (everywhere) self-crossing if its successive approximation curves exhibit self-crossing behavior. However, the more commonly illustrated space-filling curve approximations are often designed to be self-avoiding, as beautifully depicted in the figures above, showcasing a more ordered progression. In three dimensions, these self-avoiding approximation curves can even exhibit the fascinating complexity of containing knots . While these approximation curves remain confined within a bounded portion of n-dimensional space, their total lengths increase without any bound, stretching into infinity as they strive to fill the space.

Space-filling curves are, perhaps unsurprisingly, specific instances of the broader category of fractal curves , exhibiting self-similarity and intricate detail across scales. A particularly intriguing property is that no differentiable space-filling curve can possibly exist. Roughly speaking, the very concept of differentiability imposes a limit on how rapidly, or sharply, a curve can turn. A space-filling curve, by its nature, must execute an infinite number of infinitely sharp turns to touch every point, thereby violating the conditions for differentiability. In a testament to the unexpected connections within mathematics, Michał Morayne proved in 1987 that the infamous continuum hypothesis is logically equivalent to the existence of a Peano curve such that, at every single point on the real line , at least one of its component functions is differentiable. Because, naturally, the most fundamental properties of a curve must ultimately depend on assumptions about the size of infinity.

The Hahn–Mazurkiewicz theorem

The Hahn –Mazurkiewicz theorem stands as a profound characterization, precisely delineating which topological spaces can be expressed as the continuous image of curves. It’s a sort of litmus test for “curve-fillable” spaces.

Specifically, the theorem states:

A non-empty Hausdorff topological space is a continuous image of the unit interval if and only if it satisfies four concurrent conditions: it is a compact , connected , locally connected , and second-countable space .

Spaces that fulfill these stringent criteria, allowing them to be the continuous image of a unit interval, are sometimes, quite appropriately, dubbed Peano spaces .

It’s worth noting that in many formulations of the Hahn –Mazurkiewicz theorem , the condition of being “second-countable” is often replaced by “metrizable.” These two formulations are, in fact, entirely equivalent in this context. In one direction, any compact Hausdorff space is inherently a normal space , and, by the power of Urysohn’s metrization theorem , being second-countable subsequently implies that it must also be metrizable. Conversely, any compact metric space is necessarily second-countable. So, whether you prefer your spaces counted or measured, the outcome, in this particular case, is precisely the same.

Kleinian groups

The theory of doubly degenerate Kleinian groups provides a rich, if somewhat abstract, source of natural examples of space-filling—or, more accurately, sphere-filling—curves. These are not merely theoretical constructs but emerge organically from the deep structures of hyperbolic geometry. For instance, Cannon & Thurston (2007) demonstrated a particularly striking example: the circle at infinity of the universal cover of a fiber of a mapping torus of a pseudo-Anosov map is, in fact, a sphere-filling curve. In this specific context, the “sphere” in question refers to the sphere at infinity of hyperbolic 3-space . Because, apparently, even the boundaries of infinite spaces have to be completely filled by something.

Integration

Norbert Wiener , in his seminal work The Fourier Integral and Certain of its Applications, astutely observed a practical, if somewhat mind-bending, application for space-filling curves. He pointed out that these curves could be ingeniously employed to reduce the complexity of Lebesgue integration in higher dimensions, simplifying it to a more manageable Lebesgue integration in a single dimension. It’s an elegant mathematical hack, allowing one to traverse a multi-dimensional volume as if it were merely a line, thereby streamlining calculations that would otherwise be prohibitively intricate.

Notes

^ Przemyslaw Prusinkiewicz and Aristid Lindenmayer. “The Algorithmic Beauty of Plants”. 2012. p. 12
^ Jeffrey Ventrella. “Brainfilling Curves - A Fractal Bestiary”. 2011. p. 43
^ Marcia Ascher. “Mathematics Elsewhere: An Exploration of Ideas Across Cultures”. 2018. p. 179.
^ “Fractals in the Fundamental and Applied Sciences”. 1991. p. 341-343.
^ Przemyslaw Prusinkiewicz; Aristid Lindenmayer; F. David Fracchia. “Synthesis of Space-Filling Curves on the Square Grid”. 1989.
^ “FASS-curve”. D. Frettlöh, E. Harriss, F. Gähler: Tilings encyclopedia, https://tilings.math.uni-bielefeld.de/
^ Peano 1890.
^ Hilbert 1891.
^ Sagan 1994, p. 131.
^ Morayne, Michał (1987). “On differentiability of Peano type functions”. Colloquium Mathematicum. 53 (1): 129–132. doi :10.4064/cm-53-1-129-132. ISSN 0010-1354.