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.


Comments

Post a Comment

Popular posts from this blog

How To Make ASCII Diagrams Beautifuller

Image
I've discovered an excellent tool in asciiflow.com .  The website makes it really easy to create ASCII box diagrams like this They put these things in fruit machines you know! This is ideal for source code banners, which I think should contain helpful documentation - but most programmers think it's a good place for the COPYRIGHT information and nothing else. But wait! we can make it beautifuller... and easier to read... by replacing some of the ASCII characters with ones available in UTF-8: There!  Isn't that better?  (Although some purists may object to non-ASCII characters in your code base.) SOURCE CODE: #!/usr/bin/python2 # coding: utf-8 # + gets converted in different ways depending on it's 4 neighbours # # . N . { nsew(N,S,E,W) has bit 3 set if N in "+|<>" # W + E { nsew(N,S,E,W) has bit 2 set if S in "+|<>" # . S . { nsew(N,S,E,W) has bit 1 set if W in "+-^v" # { nsew(N,S,E,W) has bit 0 set if E ...
Read more

Why growth is falling in all developed countries (as a long term trend)

Image
In this post I argue that economic growth is not the normal state of affairs, it is a blip caused by the discovery of a one-off resource of non-renewable energy.   The logistic equation $$ \frac{dy}{dt} = y(1-y) $$ Here's a simple model.  Humans discover an exploitable but limited resource and start consuming it.  The amount consumed, $y(t)$, is a function of time.  The general form of the equation is $\frac{dy}{dt} = \alpha y (\beta - y)$, but if you choose the right units $\alpha$ and $\beta$ both become $1$. Why should this work, in principle? Early on, the factor $1-y$ is approximately $1$ and can be ignored.  So the model states that annual consumption $dy/dt$ starts off proportional to $y$.  In other words, $y$ grows exponentially at first.  This could happen if exploiting the resource enables further exploitation of the resource.  For example, suppose a few humans are shipwrecked on an island with 1000 trees: they take ages to cut down the ...
Read more

Three ways to look at the Bell/GHZ experiment

Image
In 1964 John Stewart Bell proposed an experiment to determine whether the results of quantum measurements were truly random, or governed by hidden variables, i.e. state that exists prior to the measurement, but which we don’t have access to. The experiment involved creating a large number of EPR pairs, and firing them at two observers, Alice and Bob, who measure their photon’s polarisation, choosing the $\updownarrow$ direction or the $\nearrow\llap\swarrow$ direction at random. Determining the result of the experiment involves doing a complex statistical calculation to see if something called Bell’s inequality is satisfied or violated. The Bell experiment was first performed by in 1982 by Alain Aspect, and the result, as most commonly interpreted, is that hidden variables can only exist if Quantum Mechanics is non-local, i.e. if it supports faster-than-light causality! Some time after Bell proposed his experiment, Greenberger, Horne, and Zeilinger suggested an alternativ...
Read more