The Hilbert Curve

In 1891, the German mathematician David Hilbert published a curve so strange it bent intuition: a single, unbroken line that — in the limit — visits every point of a filled square, leaving no spot untouched.

That seems impossible. A line is one-dimensional; a filled square is two-dimensional. How can something thin and linear cover something thick and areal?

The answer is a recursive trick. Start with a U-shaped path that visits four cells of a 2 × 2 grid. Now shrink that U into one corner, rotate copies into the other three corners, and connect them. You get a curve that visits 16 cells. Repeat: 64 cells, 256 cells, and at each step the curve gets denser, twistier, and more completely fills the square. In the infinite limit the Hilbert curve is everywhere — it is a genuine space-filling curve, an object that is simultaneously a path and a plane.

What makes the Hilbert curve special is not just that it fills space. It is how it fills space: nearby points on the curve stay nearby on the grid. This locality-preserving property, almost magical in how reliably it holds, is the reason the Hilbert curve sits at the heart of spatial databases, image compression, parallel computing layouts, and cache-efficient memory access patterns.

Use the slider to choose the recursion depth and press Draw to animate the curve visiting every cell. At depth 1 it traces a simple U; at depth 6 it visits 4 096 cells with a single continuous stroke.

<div class="controls">
  <label for="depth">{{depth_label}} <span id="depthLabel">3</span> &nbsp;({{visits_prefix}} <span id="cellCount">64</span> {{visits_suffix}})</label>
  <input type="range" id="depth" min="1" max="6" value="3" />
  <button id="drawBtn" type="button">{{draw}}</button>
  <button id="stopBtn" type="button" class="ghost" disabled>{{stop}}</button>
</div>
<canvas id="canvas" width="400" height="400"></canvas>
<div class="info" id="info">{{press_draw}}</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; margin: 0; background: #fff; color: #222; }
.controls { display: flex; align-items: center; gap: .6rem; flex-wrap: wrap; margin-bottom: .5rem; }
label { font-size: .9rem; }
input[type=range] { width: 140px; accent-color: #1d3557; }
button { font: 600 14px system-ui; padding: .4rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }
button:disabled { opacity: .4; cursor: default; }
canvas { display: block; border: 1px solid #cdd9e3; border-radius: 6px;
         max-width: 100%; height: auto; }
.info { font-size: .88rem; color: #555; margin-top: .4rem; min-height: 1.3em; }

// Code not found

Notice how the curve fills the canvas more densely at each step — and how segments that look far apart on a straight line are actually neighbors in the grid. That is the locality property in action: the one-dimensional index along the curve is a surprisingly good proxy for two-dimensional proximity.

A space-filling curve seems to break mathematics. It does not — it refines it.

What the curve actually is. Each finite-depth Hilbert curve $H_{n}$ is an ordinary piecewise-linear path. The true Hilbert curve H is the uniform limit of the sequence $H_{1}$, $H_{2}$, $H_{3}$, … — the curve every segment converges toward as n → ∞. This limit exists, is continuous, and is a surjection from the unit interval [0, 1] onto the unit square [0,1]². Giuseppe Peano proved such limits are possible in 1890; Hilbert made the construction explicit and geometric a year later.

Dimension paradox, resolved. The existence of a continuous surjection from a 1-D interval onto a 2-D square seems to violate dimension theory. It does not, because H is not injective — infinitely many points of [0,1] map to the same point of the square. A true bijection (invertible map) between the two is impossible by topological dimension theory. The Hilbert curve is not a bijection; it is a many-to-one map. Its Hausdorff dimension is 2, matching the square — a sign of how densely it fills space — while it remains parameterized by a 1-D variable.

Locality. The key property is that if two values $t_{1}$ and $t_{2}$ on [0,1] are close, then H($t_{1}$) and H($t_{2}$) tend to be close in the square. The reverse also holds statistically: nearby grid cells tend to receive close parameter values. This is not perfect (a few "jumps" exist at every depth where adjacent cells get distant indices) but for the vast majority of point pairs the correlation is strong — far better than a naive row-by-row raster scan.

The construction is entirely computable: given a depth n and a 1-D index i, you can decode the 2-D grid cell in $O(n)$ bit-operations, and encode a 2-D cell back into its index equally fast. No approximation is needed. That tractability is why the Hilbert curve found its way from pure mathematics into engineering.

The Hilbert curve's locality property turns a mathematical curiosity into a practical tool across a surprising range of fields:

• Spatial databases. A database storing geographic objects (shops, roads, sensor readings) must answer range queries — "find everything within 5 km of here." Storing objects sorted by their Hilbert index means nearby objects cluster in the same disk pages, so a range query touches few pages. This is the Hilbert R-tree, used in PostGIS, BigQuery, and many GIS systems.
• Image processing and video codecs. Scanning pixels in Hilbert order rather than row order keeps spatially correlated pixels adjacent in memory, improving cache hit rates for local-filter operations (blurring, edge detection). Some wavelet-based codecs use it internally.
• Parallel and distributed computing. When a simulation domain is partitioned across many processors, a Hilbert-order partition ensures each processor owns a roughly contiguous region, minimising communication between neighbors.
• Cache-oblivious algorithms. Sorting matrix elements or graph nodes by Hilbert index can dramatically reduce cache misses in algorithms that access data in spatially local patterns.
• Chip and VLSI layout. Placing logic blocks or memory cells in Hilbert order minimises average wire length between related components.

All of these exploits share the same insight: a one-dimensional ordering that respects two-dimensional proximity is immensely valuable, and the Hilbert curve is the best known such ordering. For a deeper look at how indexing connects to algorithm efficiency, see the article on sorting lower bounds or the discussion of dimensionality reduction.

David Hilbert's 1891 construction started as pure mathematics — a proof that dimension is not as rigid as it looks, that a single line can be as rich as a plane. A century later the same idea runs inside spatial databases, image codecs, parallel schedulers, and memory controllers.

The reason is the locality property: nearby places on the curve are usually nearby in the grid. That simple statistical correlation between one dimension and two is powerful enough to reshape how we store data, design chips, and distribute computation.

The Hilbert curve is a reminder that the most useful engineering tools are sometimes discovered when mathematicians ask purely abstract questions about the nature of space. The curve was not invented — it was found, buried inside the definition of continuity itself.