Hacker News new | ask | show | jobs
by nkrisc 18 hours ago
Imagine a sheet of paper folded in such a way that if you looked at it perfectly edge-on it would appear as a 2D Hilbert curve.
1 comments

Yes, that's understood, but it's not the point. That would convert a 3D space to a 2D space (the Z dimension is unaffected). But a 2D Hilbert curve converts 2D->1D, and a 3D Hilbert curve converts 3D->1D -- it's a curve winding its way through 3D space. (And yes, it certainly does exist and is used.) Any (quantized) point in 3D can be mapped to a distance from the start of the 3D Hilbert curve.

But Hilbert curves are complicated. If you have n dimensions, you can simply take the sequence of bits describing the position in each dimension and interleave them, forming a longer sequence of bits. It's not nearly as nice of a curve -- adjacent points along the line are not necessarily close in n-dimensional space the way they would be with a Hilbert curve -- but it's simple to calculate and proves that you can generalize this stuff to any number of dimensions.

This interleaving produces what is called a Z-curve or Morton curve. It's not continuous like the Hilbert curve, so mathematically you might not call it a space-filling curve but in CS-land, you probably would.

I see what you mean, I misunderstood initially.