In high-dimensional task scheduling, it is common to use a Hilbert-curve ordering. Given a set of points $\{p_i\}_{i=1}^N \subset \mathbb{R}^d$ the goal is to linearly order them such that points nearby in space are also nearby in order. The heuristic behind Hilbert curve scheduling is that ordering based on distance along a Hilbert curve tends to preserve locality.

In practice, you divide space into sufficiently small dyadic boxes, round the location of the points to the centers of those boxes, then order the points based on their distance along the finite order Hilbert curve approximation that passes through each of the boxes exactly once, as demonstrated on the blue points in the following image enter image description here

On the other hand, since $[0,1]$ is not homeomorphic to $[0,1]^2$ and since the fully infinite Hilbert curve is onto and continuous, it can't be 1-1. Thus it seems to me that Hilbert curve ordering is not a well-defined concept - for a point that is mapped to twice, it has no clearly defined "Hilbert distance" along the Hilbert curve.

Is this right, or is there something I'm missing? I think the above reasoning is pretty bulletproof, but I haven't seen the issue even mentioned in the computational literature.

  • 1
    $\begingroup$ If I remember correctly, any point in the square is hit by the Hilbert curve at most 4 times. So you could just decide to use, for example, the first of these 4 times. $\endgroup$ – hmakholm left over Monica Jul 2 '12 at 10:42

The Hilbert curve, understood as the limit of an infinite iterative process, is not one-to-one. But in actual computations one works with an N-th generation of the iterative construction, not with the limit as $N\to\infty$. For example, yours is the 2nd generation curve, and it is a bijection between the linear set $0,1,\dots,15$ and the square matrix $4\times 4$. Maybe it should be called pre-Hilbert curve to emphasize the distinction, but usually it is clear from context whether we have a concept from analysis/topology or from finite mathematics. Computers never let $N\to\infty$, do they?

You may find this relevant: computation of Hilbert distance in Haskell

| cite | improve this answer | |

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.