[arutar]

Here's another way that I like to think about it.

First, forget briefly about the Hilbert curve and just think about the unit square [0,1]^2.

If you take any point (x,y) in the unit square, we can associate x and y with binary coordinates, say x = 0.a1a2a3... and y = 0.b1b2b3... Then we can just define a new number z with binary representation 0.a1b1a2b2a3b3... And going the other way, given z in [0,1], we can take the 'even' binary coordinates to get x, and the 'odd' binary digits to get y.

The problem with this specific mapping is that the function is not continuous. But if you are a bit more careful:

1. The first digit says "left half vs right half"

2. The second digit says "top half vs bottom half" (of the rectangle from 1)

3. The third digit says "left half vs right half" (of the square from 2)

etc.

and then if two numbers share the first n binary digits (i.e. your points are close on the real line) then the corresponding points in the plane will also be quite close together (they are inside the same square / rectangle with side length like 2^(-n/2) at step n).

The "reason" why the dimension is different is precisely because of the "n/2": for every n digits of precision you have in the number z, you only get n/2 digits of precision for each of (x, y).

This is a bit imprecise because of issues with non-unique binary representation but (at least for me) it captures the spirit of why this should work!

[jerf]

You can write a fast algorithm to map distances to points on a Hilbert curve on a computer: https://stackoverflow.com/questions/499166/mapping-n-dimensi... It's complicated to just glance at, and the algorithm linked here does an arbitrary number of dimensions which also adds some complexity, but it's not that hard, all things considered. Despite the for loops, in practice it's a O(1) algorithm; if I'm reading the algorithm correctly it's technically O(number of bits in index + number of dimensions) but in practice both of those are fixed and the constant factors are very small and so for practical purposes it's going to be O(1) unless you're routinely dealing with highly variable index sizes and dimension counts in practice.

Thus this is a constructive proof that you can use easily convert Hilbert indices and coordinates back and forth between each other. Again, reading the algorithm I'm pretty sure if you give it the algorithm arbitrarily detailed numbers out to infinity, the obvious extension would "work" in that you can slap a "limit to infinity" on the algorithm in both cases and it would converge to any given point you like.

[praptak]

The issues make it not continuous. The 1d limit of 0.01, 0.011, 0.0111, ... is 0.1

The 2d limit of the same series is the top right point of left half. The 2d representation of 0.1 is the bottom left point of the right half.

The Hilbert curve is mirrored and that's how it solves this problem.