[Math] Why is this not a space-filling curve

analysisplane-curves

From Wikipedia, a space-filling curve is a curve (i.e. a continuous function whose domain is the unit interval $[0,1]$) whose range contains the entire 2-dimensional unit square.

Many examples of space-filling curves are known, such as the Peano curve

Image credit: Wikipedia

and the Hilbert curve

Image credit: Wikipedia

(both curves are the limiting curves of the iteration seen in the pictures).

According to http://en.wikipedia.org/wiki/Space-filling_curve#History, the Peano curve was the first example of a space-filling curve to be found (by Peano). Presumably, when searching for a space-filling curve with an iterative approach in mind, Peano must have come across this curve as well:

enter image description here

(and so on), which has a much simpler description than the one he actually chose and, indeed, would be easy to think of even for a child (call it the "accordion curve").

This leaves two possibilities:

Peano chose the Peano curve for a reason other than merely it being a space-filling curve or, more likely
The "accordion curve" shown in this post is not a space-filling curve.

Which is it? If the accordion curve is space-filling, it is surely the easiest space-filling curve to describe and understand, so I strongly suspect that it is not space-filling after all. At the same time, though, I have been unable to find a reason why it should not be.

Best Answer

Expanding the answer by Rahul Narain: the accordion construction does not work. In order to obtain a continuous curve in the limit, there must be a modulus of continuity $\omega$ which works for every stage of construction: that is, $|f_n(x)-f_n(y)|\le \omega(|x-y|)$ for every $n$. In particular, $|f_n(x)-f_n(y)|\le 1/2$ when $|x-y|<\delta$, where $\delta>0$ is independent of $n$. Then the inverse image of each vertical line segment in the accordion must have length $\ge \delta$, which leads to a contradiction as $n$ increases.

Related Solutions

Analysis – Can a Space-Filling Curve be Injective Everywhere?

There are no continuous bijections from $\mathbb{R}$ to $\mathbb{R}^2$, or to $[0,1]^2$.

Suppose $f$ is a continuous injection from $\mathbb{R}$ into $\mathbb{R}^2$. Then for each $n \in \mathbb{N}$, $f|_{[-n,n]}$ is a continuous injection from a compact space to a Hausdorff space, and hence a homeomorphism onto its image. Thus the image $f([-n,n])$ is nowhere dense: it's compact, hence closed, hence if it were somewhere dense it would contain a closed ball. But then there would be infinitely many points that could be deleted from it without disconnecting it, contradicting it being homeomorphic to $[-n,n]$.

Thus the image of $f$ is a countable union of nowhere-dense sets. So by the Baire category theorem it can't be all of $\mathbb{R}^2$, or indeed any set with nonempty interior.

[Math] Space-filling curve with distance locality

The first problem is that "distance along the curve" is not meaningful for a space-filling curve -- the usual definition of distance for smooth curves (limit of approximating polygons) leads to the distance between two general points on the curve being infinite.

If you replace "distance along the curve" with "difference in parameters", then I can do it for $[0,\infty)\to\mathbb R^2$, but getting a doubly-infinite domain seems to be impossible.

Possible for $[0,\infty)\to \mathbb R^2$: Divide the plane into unit squares and number them in a spiral going out from the origin:

12 11 10  9  .
13  2  1  8  .
14  3  0  7  .
15  4  5  6 21
16 17 18 19 20

The classic Peano curve construction yields a space-filling curve $[0,1]\to[0,1]^2$. Put countably many of these together into $f:\mathbb [0,\infty)\to\mathbb R^2$, such that $f([n,n+1/2])$ fills the square numbered $n$ in the diagram, and $f([n+1/2,n+1])$ is just a simple connection from the endpoint of one Peano curve and the begining of the next.

This $f$ fills space but does not satisfy distance locality. But $g(t) = f(t^3)$ does. The cubic growth ensures that each winding in the spiral occupies a bounded amount of $t$, so the parameter distance between each square and any of its 8 neighbors is globally bounded.

Impossible for $\mathbb R\to \mathbb R^2$: Assume $f:\mathbb R\to\mathbb R^2$ is space-filling and satisfies your distance locality criterion. With appropriate scaling and translation we can assume $f(0)=(0,0)$ and $a=b=1$. We can then prove by induction on $n$ that $|f(t)|<n \Rightarrow |t|<n$ for all integers $n$, and therefore $|f(t)|>|t|-1$ in general. Then let $D=1+\max\limits_{|t|\le 1}|f(t)|$, and consider the two sets $$ P = \{ f(t) \mid t > 1 \land |f(t)| > D \} $$ $$ M = \{ f(t) \mid t < -1 \land |f(t)| > D \} $$ $P$ and $M$ are both nonempty -- one contains $f(D+1)$, the other $f(-(D+1))$ -- and their union is the connected set $\{x\in \mathbb R^2\mid |x|\ge D\}$. Therefore their closures must intersect. But near a point where the closures meet, there must be $t$s that violate distance locality.

Related Question