3

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.

Z-order-curve

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?

MaiaVictor
  • 51,090
  • 44
  • 144
  • 286
  • I highly doubt there is an algorithm which does not depend on the dimensionality of the space. This sounds too good to be true. – Salvador Dali Aug 03 '15 at 06:47

2 Answers2

2

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.

Louis Ricci
  • 20,804
  • 5
  • 48
  • 62
1

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

Micromega
  • 12,486
  • 7
  • 35
  • 72