Space filling curve

Q: How do you catch a lion in the Sahara?

A: Run along a space filling curve carrying a spear.  ($\dagger$)

Surprisingly, it is possible to construct a continuous and surjective map $[0,1]\mapsto  [0,1]^2$.  In less techie language: you can plot a curve that fills space.  But how do you do it?  The answer uses the following four maps $[0,1]^2\mapsto [0,1]^2$.

$$\begin{align} & \phi_0(x,y) = \frac{1}{2}(y,x) & \text{flip about diagonal and shrink}\\ & \phi_1(x,y) = \frac{1}{2}(x,y)+(0,\frac{1}{2}) & \text{shrink and translate to top left}\\ & \phi_2(x,y) = \frac{1}{2}(x,y)+(\frac{1}{2},\frac{1}{2}) & \text{shrink and translate to top right}\\ & \phi_3(x,y) = \frac{1}{2}(1-y,1-x)+(\frac{1}{2},0) & \text{flip, shrink & translate to bottom right}\\ \end{align}$$

In words the recipe goes like this: 

• start off with any continuous map $\gamma:[0,1]\mapsto[0,1]^2$ with $\gamma(0) = (0,0)$ and $\gamma(1)=(1,0)$.
• apply all four maps $\phi_0,\phi_1,\phi_2,\phi_3$ to $\gamma([0,1])$ to get a new set.
• repeat the previous step over and over and the sets obtained will converge to the space filling curve

Let's call the intermediate maps $\psi_n$.  All we need to do to show that this recipe generates a space filling curve is the following

1. That each $\psi_n$ is continous
2. That $\psi_n$ converges uniformly (and let's call the limit $\psi$)
3. That each $(x,y) \in [0,1]^2$ is in the range of $\psi$

Note that (2) implies that $\psi$ is continous by The Uniform Limit Theorem.  First it will be handy to have a  mathematical formula for $\psi_n$.  I'll just present it here in terms of it's action on a number represented in base 4 notation $0.q_1q_2q_3...$.  (I'm going to call the $q_i$ qubits for quad-bits. It's got nothing to do with quantum computing, I just like the name.)
$$\psi_n(0.q_1q_2q_3...)= \phi_{q_1}\phi_{q_2}\phi_{q_3}...\phi_{q_n}\gamma(0.q_{n+1}q_{n+2}...)$$
Note that there is no ambiguity in this definition since if there are non matching qubits $0.q_1q_2q_3...$ and $0.q_1^{'}q_2^{'}q_3^{'}...$ representing the same number, and the 1st difference is in the Nth qubit, then w.l.o.g. $q_N=q_N^{'}+1$ and for all  $n > N, q_n=0, q_n^{'} = 3$.  But
$$\phi_0\gamma(0.333...) = \phi_1\gamma(0.000...) \\ \phi_1\gamma(0.333...) = \phi_2\gamma(0.000...) \\ \phi_2\gamma(0.333...) = \phi_3\gamma(0.000...) \\ $$
so you get the same point in $[0,1]^2$ whatever the qubit representation you use.

1. Continuity of $\psi_n$ 

This is trivial, since $\psi_n$ is piecewise continuous.

2. Uniform convergence of the $\psi_n$

From the definition it is clear that the distance from $\psi_n(0.q_1q_2q_3...)$ to $\psi_{n+1}(0.q_1q_2q_3...)$ is at most $\frac{\sqrt{2}}{2^n}$ since both numbers are in the same $\frac{1}{2^n}\times\frac{1}{2^n}$ box.  Likewise the distance from $\psi_n(0.q_1q_2q_3...)$ to $\psi_{m}(0.q_1q_2q_3...)$ for any $m > n$ is bounded by $\frac{\sqrt{2}}{2^n}$ meaning that the $\psi_n(0.q_1q_2q_3...)$ converge and that the distance to the limit is bounded by the same number.

3. Surjectivity of $\psi$

Suppose you have an $(x,y)$ in the square.  Choose $q_1$ such that $\psi_{q_1}[0,1]^2$ is the quadrant that contains $(x,y)$, and $q_2$ such that $\psi_{q_1}\psi_{q_2}[0,1]^2$ is the quadrant of the quadrant that contains $(x,y)$ and so on.  Then
$$\psi(0.q_1q_2...) = (x,y)$$
Note that, since we've constructed a fractal, you can also calculate the Hausdorff Dimension for it, and that this turns out to be 2, which supports the notion that it fills space!

($\dagger$) A bad joke.  I heard it from another maths student at Bristol.  What can you say.

($\dagger^2$) And note that the lion has to be sleeping for this to definitely work.

($\dagger^3$) And since $F=ma$ you probably need to go infinitely slowly.