Mathwords logoMathwords

Hilbert Curve — Definition, Formula & Examples

A Hilbert curve is a continuous, space-filling curve that passes through every point of a unit square. It is constructed as the limit of an iterative process that repeatedly subdivides the square into smaller quadrants and connects their centers in a specific pattern.

The Hilbert curve is the limit H=lim⁡n→∞HnH = \lim_{n \to \infty} H_n of a sequence of piecewise-linear approximations Hn:[0,1]→[0,1]2H_n:[0,1] \to [0,1]^2, where each HnH_n is a continuous bijection from [0,1][0,1] onto a path visiting all 4n4^n sub-squares of a 2n×2n2^n \times 2^n grid. The limiting map HH is a continuous surjection from the unit interval onto the unit square, demonstrating that a one-dimensional path can fill a two-dimensional region.

How It Works

Construction begins with the order-1 Hilbert curve H1H_1, a U-shaped path connecting the centers of four quadrants of the unit square. To build Hn+1H_{n+1} from HnH_n, you divide each quadrant into four sub-quadrants, place a copy of HnH_n inside each one (applying rotations and reflections as needed), and connect adjacent copies with short linking segments. At each iteration, the curve visits 4n4^n grid cells and has total length proportional to 1−2−n1 - 2^{-n}. The limiting curve is continuous and surjective but nowhere differentiable, with Hausdorff dimension 2.

Worked Example

Problem: Determine how many grid cells the order-3 Hilbert curve visits, and compute the number of straight-line segments in its piecewise-linear approximation.
Step 1: At order nn, the Hilbert curve visits 4n4^n grid cells arranged on a 2n×2n2^n \times 2^n grid. For n=3n = 3:
43=64 cells on an 8×8 grid4^3 = 64 \text{ cells on an } 8 \times 8 \text{ grid}
Step 2: The piecewise-linear path connects the centers of all 64 cells in sequence, so the number of line segments is one fewer than the number of cells:
64−1=63 segments64 - 1 = 63 \text{ segments}
Step 3: Each segment has length 123=18\frac{1}{2^3} = \frac{1}{8}, so the total path length is:
63×18=638=7.87563 \times \frac{1}{8} = \frac{63}{8} = 7.875
Answer: The order-3 Hilbert curve visits 64 grid cells, consists of 63 line segments, and has a total path length of 638\frac{63}{8}.

Why It Matters

Hilbert curves preserve spatial locality better than simple row-major orderings, making them valuable in database indexing, image processing, and geographic information systems. In computational geometry and parallel computing, Hilbert curve mappings are used to partition multi-dimensional data so that nearby points in space remain close along the 1D curve, reducing cache misses and improving query performance.

Common Mistakes

Mistake: Assuming the Hilbert curve is a bijection from [0,1][0,1] to [0,1]2[0,1]^2.
Correction: The limiting curve is surjective (onto) but not injective — some points in the square are visited by more than one parameter value. A continuous bijection from [0,1][0,1] to [0,1]2[0,1]^2 cannot exist because removing a point from [0,1][0,1] disconnects it, but removing a point from [0,1]2[0,1]^2 does not.