3D Hilbert curves in even fewer instructions

So far, the LUT based algorithm is the fastest method in general for mapping between Morton and Hilbert orders in 3D. This method performs linearly in the input size, consuming 3 bits of input and producing 3 bits of output per iteration. Let's break it down into 5 logical steps: Extract 3 bits from input: […]

LUT-based 3D Hilbert curves

As referenced in my earlier post about Hilbert curves, it's possible to map between -dimensional Euclidean coordinates and the offset along the Hilbert curve in time by direct application of the transformation group at each recursion level of the curve. The following applies this to the 3D case: The 3D Hilbert curve transforms under the […]

Hilbert curves in O(log(n)) time

Jump to the code Today I present a novel technique for mapping a point in the -dimensional plane to its corresponding -bit offset on the th order Hilbert curve with a running time of on a processor with -bit words. While a large constant factor makes it infeasible in higher dimensions, it is significantly faster […]