Hilbert curve

From Wikipedia, the free encyclopedia

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.^[1]

Because it is space-filling, its Hausdorff dimension is 2.
H_n is the nth approximation to the limiting curve. The Euclidean length of H_n is , i.e., it grows exponentially with n, while at the same time always being bounded by a square with a finite area.

For multidimensional databases, Hilbert order has been proposed to be used instead of Z order because it has better locality-preserving behavior.

Contents 1 Representation as Lindenmayer system 2 See also 3 References 4 External links

[edit] Representation as Lindenmayer system

The Hilbert Curve can be expressed by a rewrite system (L-system).

Alphabet : L, R

Constants : F, +, −

Axiom : L

Production rules:

L → +RF−LFL−FR+

R → −LF+RFR+FL−

Here, F means "draw forward", + means "turn left 90°", and − means "turn right 90°" (see turtle graphics).

Butz^[2] provided an algorithm for calculating the Hilbert curve in multidimensions.

Hilbert curve, first order

Hilbert curves, first and second orders

Hilbert curves, first to third orders

Hilbert curve in three dimensions

3-D Hilbert curve with color showing progression

[edit] See also

Wikimedia Commons has media related to: Hilbert curve

• Hilbert Curve generation code from Graphics Gems 2
• Sierpiński curve
• z-order (curve)
• Moore curve
• List of fractals by Hausdorff dimension

[edit] References

1. ^ D. Hilbert: Über die stetige Abbildung einer Linie auf ein Flächenstück. Math. Ann. 38 (1891), 459–460.
2. ^ A.R. Butz: Alternative algorithm for Hilbert’s space filling curve. IEEE Trans. On Computers, 20:424-42, April 1971.

[edit] External links

• Dynamic Hilbert curve with JSXGraph