Что такое быстрый алгоритм N-мерной кривой Z-порядка?

Question

Кривые заполнения пространства - это способ заполнения сетки линией, сохраняющей локальность, то есть две точки закрытия на линии также являются двумя точками закрытия в пространстве.

Есть ли пост (O(1)) алгоритм для отображения между N-мерной координатой и индексом на соответствующей N-мерной кривой заполнения пространства?

Answer 1

Вам необходимо сопоставить точку Nd с чередованным двоичным форматом, который всегда будет O(n), тогда, если у вас есть отсортированный массив 1d, вы должны выполнить бинарный поиск O(logM), где M - число из точек; Вы можете использовать *HashMap * и изменить поиск в двоичном поиске logM на поиск с постоянной o(1).

Answer 2

Возможно, это не O(1), но вы можете превратить z-index в октаву. Относитесь к нему как к основанию-8.