What is a fast n-dimensional Z-order curve algorithm?

Question

Space filling curves are a way to fill a grid with line that preserves locality - that is, two close points at the line are also 2 close points on space.

Is there any fast (O(1)) algorithm to map between an N-dimensional coordinate and the index on the corresponding N-dimensional space-filling curve?

Answer 1

You need to map the N-d point to the interleaved binary format, which is always going to be O(n), then if you have you're 1d sorted array you have to do a binary search O(logM) where M is the number of points; you could use a *HashMap < binary, index > * and change the logM binary search lookup to a constant o(1) lookup.

Answer 2

Maybe it is not O(1) but you can turn the z-index to an octkey. Treat it as base-8 number.