The Hilbert Curve

A Hilbert curve (also known as a Hilbert space-filling curve) is a continuous fractal space-filling curve first described by the German mathematician David Hilbert in 1891, as a variant of the space-filling curves discovered by Giuseppe Peano in 1890.

Because it is space-filling, its Hausdorff dimension is 2 (precisely, its image is the unit square, whose dimension is 2 in any definition of dimension; its graph is a compact set homeomorphic to the closed unit interval, with Hausdorff dimension 2).

H_n is the  n th approximation to the limiting curve. The Euclidean length of  H_n  is \textstyle 2^n - {1 \over 2^n} , i.e., it grows exponentially with n, while at the same time always being bounded by a square with a finite area.

Hilbert curve, first order

Hilbert curves, first and second orders

Hilbert curves, first to third orders

Both the true Hilbert curve and its discrete approximations are useful because they give a mapping between 1D and 2D space that fairly well preserves locality. If (x,y) are the coordinates of a point within the unit square, and d is the distance along the curve when it reaches that point, then points that have nearby d values will also have nearby (x,y) values. The converse can’t always be true. There will sometimes be points where the (x,y) coordinates are close but their d values are far apart. This is inevitable when mapping from a 2D space to a 1D space. But the Hilbert curve does a good job of keeping those d values close together much of the time. So the mappings in both direction do a fairly good job of maintaining locality.

First 8 steps toward building the Hilbert curve

Because of this locality property, the Hilbert curve is widely used in computer science. For example, the range of IP addresses used by computers can be mapped into a picture using the Hilbert curve. Code to generate the image would map from 2D to 1D to find the color of each pixel, and the Hilbert curve is sometimes used because it keeps nearby IP addresses close to each other in the picture. A grayscale photograph can be converted to a dithered black and white image using thresholding, with the leftover amount from each pixel added to the next pixel along the Hilbert curve. Code to do this would map from 1D to 2D, and the Hilbert curve is sometimes used because it does not create the distracting patterns that would be visible to the eye if the order were simply left to right across each row of pixels. Hilbert curves in higher dimensions are an instance of a generalization of Gray codes, and are sometimes used for similar purposes, for similar reasons. For multidimensional databases, Hilbert order has been proposed to be used instead of Z order because it has better locality-preserving behavior. For example, Hilbert curves have been used to compress and accelerate R-tree indexes (see Hilbert R-tree). They have also been used to help compress data warehouses.

Given the variety of applications, it is useful to have algorithms to map in both directions. In many languages, these are better if implemented with iteration rather than recursion. The following C code performs the mappings in both directions, using iteration and bit operations rather than recursion. It assumes a square divided into n by n cells, for n a power of 2, with integer coordinates, with (0,0) in the lower left corner, (n-1,n-1) in the upper right corner, and a distance d that starts at 0 in the lower left corner and goes to n^2-1 in the lower-right corner.

This entry was posted in Mathematics. Bookmark the permalink.