Obtaining the Parameterization of a Space-Filling Curve

curvesdiscrete mathematicsgeneral-topology

So, I am working with a grid that has $N_x$, $N_y$ and $N_z$ voxels along the $x$, $y$ and $z$ axis respectively. There is this bijection that I apply in order to use the grid as one large vector and it is as such:

$$
\tag{1}
\label{eq:param}
l(i,j,k)=i⋅(N_x)^2+j⋅(N_y)^1+k⋅(N_z)^0
$$

where $i,j,k$ are the indices of a voxel in the grid. It occurred to me that this is a very arbitrary way of having a grid turned into a vector, of converting 3D to 1D and I started looking into it a little bit more. I came across the concept of a space-filling curve and it seemed to me like those curves were better behaved and had interesting properties.

I wanted to work with them, it turns out that in order to do that I need a way to compute the values $l(i,j,k)$ for these curves. So my question is:

Is there a way to obtain a parameterization such as the one in Equation \ref{eq:param} for a space-filling curve?

P.S. If there is no general method, it is enough to discuss one particular example of a space-filling curve where that is possible.

P.P.S. In case there are no examples with a neat closed-form expression like Equation \ref{eq:param}, it is okay if there is a computational procedure to compute an $l(i,j,k)$, given the indices $i,j$ and $k$.

Best Answer

Some space-filling curves, such as Peano curve and Hilbert curve, can be regarded as certain generalization of $d$-ary expansion. This is because $d$-ary expansion on the unit interval $[0, 1]$ can be thought as parametrizing $[0, 1]$ by the infinite rooted $d$-ary tree $T_d = \{0, \cdots, d-1\}^{\mathbb{N}}$, and likewise, the aforementioned curves can also be parametrized by $T_d$ for certain choices of $d$.

For instance, let $\gamma : [0, 1] \to [0, 1]^2$ be the Hilbert curve as in the construction illustrated in here. Its first four steps are demonstrated below:

Now we recursively define $S_a$'s as follows:

Set $S_{\varnothing} = [0, 1]^2$.
Let $n \geq 1$ and $a = (a_1, \cdots, a_{n-1})$, where the empty list is denoted by $\varnothing$. If $S_a$ is defined, then divide $S_a$ into $4$ sub-squares of equal sizes. In order to label them, define $e_1, \cdots, e_{n-1}$ by

$$ e_i = \begin{cases} (1, 0), & a_i = 0; \\ (0, 0), & a_i = 1 \text{ or } 2; \\ (1, 1), & a_i = 3 \end{cases} \qquad \text{and} \qquad e = \sum_{i=1}^{n-1} e_i \pmod{2}. $$

Although the meaning of $e$ is not clear at this moment, we remark that $e$ determines the shape of the curve on $S_a$. Then label the sub-squares by the following rules:

Then we have:

Proposition. For any $x \in [0, 1]^2$, let $a_1, a_2, \cdots \in \{0,1,2,3\}$ be such that $x \in S_{a_1,\cdots,a_n}$ for all $n \geq 1$. If $t = 0.a_1 a_2 \cdots _{(4)}$ denotes the $4$-ary expansion with digits $a_1, a_2, \cdots$, then $\gamma(t) = x$.

For instance, the following picture shows the regions corresponding to different values of the first 3 digits $(a_1, a_2, a_3)$:

This plot also suggests why we adopt the above weird-looking labeling rule. It simply labels sub-squares according to their order of appearance along the Hilbert curve.

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.

Best Answer

Related Solutions

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

[Math] Space-filling curve with distance locality

Related Question