I'm not sure I understand how you can use a single number to say where on the Hilbert curve you are. As the curve is infintely, iteratively defined, you either can't say where you are on the curve, or you can say "length x, iterations y", which makes it 2 dimensional.

▲

isoprophlex 4 days ago | parent | next [-]

If you take the length of the entire curve as a number l irrespective of the iteration depth, you can say you are at position 42% of l. Because at iter n, the segments are replaced by a new shape that does not grow beyond the bounds of the segments at n-1, the iterations are 'contractive', and iterating more deeply only makes the x, y location of 'i am at 42%' more precise.

▲

arutar 4 days ago | parent | prev | next [-]

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 4 days ago \| parent \| next [-]
		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 3 days ago \| parent \| prev [-]
		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.

▲

praptak 4 days ago | parent | prev | next [-]

Yeah, it is not entirely obvious. You need to prove that if you fix a number x from range [0,1] then the point at "x * length(Hn)" converges to a point in 2D, for every x, as n goes to infinity (Hn = nth Hilbert curve).

The limit for x is the mapping from x to a point in 2D.

The proof is by observing that the subsequent "jumps" are exponentially smaller.

▲

ComplexSystems 4 days ago | parent | prev [-]

You say lim y->inf (length x, iteration y).