Hilbert’s Curve

Prev: Error-Correcting Codes

Next: Floating-Point

Sections

• 16-1 A Recursive Algorithm for Generating the Hilbert Curve
• 16-2 Coordinates from Distance along the Hilbert Curve
• 16-3 Distance from Coordinates on the Hilbert Curve
• 16-4 Incrementing the Coordinates on the Hilbert Curve
• 16-5 Non-Recursive Generating Algorithms
• 16-6 Other Space-Filling Curves
• 16-7 Applications

Problems

1. A simple way to cover an $n\times n$ grid in a way that does not make too many big jumps, and hits every point once and only once, is to have a $2n$-bit variable $s$ that is incremented at each step, and form $x$ from the first and every other bit of $s$, and $y$ from the second and every other bit of $s$. This is equivalent to computing the perfect outer unshuffle of $s$, and then letting $x$ and $y$ be the left and right halves of the result. Investigate this curve’s locality property by sketching the curve for $n=3$.

2. A variation of exercise 1 is to first transform $s$ into $\mathrm{Gray}(s)$, see page 312, and then let $x$ and $y$ be formed from every other bit of the result, as in exercise 1. Sketch the curve for $n=3$. Has this improved the locality property?

3. How would you construct a three-dimensional analog of the curve of exercise 1?