Hilbert curve

From Wikipedia, the free encyclopedia

Jump to: navigation, search
First 8 steps toward building 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.[1]

Because it is space-filling, its Hausdorff dimension is 2.
Hn is the nth approximation to the limiting curve. The Euclidean length of Hn is  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.

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

Contents

[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.

[edit] See also

[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

Personal tools