algorithm - 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

您需要将 Nd 点映射到交错二进制格式，该格式始终为 O(n)，然后如果您是一维排序数组，则必须进行二进制搜索 O(logM)，其中 M 是数字点数；您可以使用 *HashMap < binary, index > * 并将 logM 二进制搜索查找更改为常量 o(1) 查找。

Answer 2

也许它不是 O(1)，但您可以将 z-index 转换为八键。将其视为以 8 为基数的数字。