Hilbert-Kurve

Begriff, Bedeutung und Anwendungen

Die Hilbert-Kurve ist eine stetige, raumfüllende Kurve: Sie bildet das Einheitsintervall I = [0,1] auf das gesamte Einheitsquadrat Q = [0,1] × [0,1] ab. Sie wurde 1891 von David Hilbert veröffentlicht. Obwohl ihr Parameter t eindimensional ist, erreicht die Grenzkurve jeden Punkt eines zweidimensionalen Gebiets. Ihre Hausdorff-Dimension ist deshalb exakt 2.

Die Kurve entsteht als Grenzwert rekursiv verfeinerter Näherungen. H_n bezeichnet die Hilbert-Kurve der n-ten Iteration; der gerichtete Polygonzug P_n, der die Mittelpunkte der Teilquadrate in ihrer Reihenfolge verbindet, heißt Hilbert-Polygon. Die endlichen Hilbert-Kurven und Hilbert-Polygone besitzen denselben Grenzwert, die eigentliche Hilbert-Kurve. Die euklidische Länge von P_n beträgt (4^n − 1)·2^(−n) = 2^n − 2^(−n) und wächst für n → ∞ unbegrenzt.

Die Reihenfolge, in der die Kurve die Teilquadrate beziehungsweise Punkte besucht, heißt Hilbert-Ordnung. Sie überträgt Verfahren mit linear geordneten Daten, etwa binäre Suche, binäre Suchbäume oder Skip-Listen, auf mehrdimensionale Daten. Besonders wichtig ist ihre gute Nachbarschaftserhaltung: Räumlich nahe Punkte liegen häufig auch in der linearen Ordnung nahe beieinander. Das ist etwa beim Zugriff auf geografische Daten über Länge und Breite nützlich. Die Z-Kurve lässt sich geringfügig einfacher berechnen, erhält Nachbarschaften aber deutlich schlechter. Anwendungen gibt es unter anderem in Bildverarbeitung, Datendarstellung und Hochleistungsrechnen.

Rekursive Konstruktion

In Dimension d wird das Gebiet [0,1]^d bei jedem Schritt in 2^d kongruente Teilgebiete halber Seitenlänge zerlegt; gleichzeitig wird das Parameterintervall in 2^d gleich lange Teilintervalle geteilt. In zwei Dimensionen entstehen bei jeder Stufe vier Teilquadrate. In jedes wird eine um den Faktor 1/2 verkleinerte, verschobene, gedrehte oder gespiegelte Kopie der vorherigen Kurve eingesetzt. Die Kopien werden so ausgerichtet, dass sie eine einzige gerichtete Kurve bilden. Dieses Vorgehen heißt Selbstähnlichkeit.

In der n-ten Iteration entsprechen 4^n Parameterintervalle genau 4^n Quadraten mit Seitenlänge 2^(−n) und Fläche 4^(−n). Der Parameter wird im Quaternärsystem geschrieben: t = 0₄.τ₁τ₂τ₃… mit τ_i ∈ {0,1,2,3}. Die Koordinaten werden binär dargestellt: x = 0₂.ξ₁ξ₂… und y = 0₂.η₁η₂… mit ξ_i,η_i ∈ {0,1}. Jede weitere Quaternärziffer wählt eines der vier Teilquadrate und liefert je eine neue Binärziffer für x und y.

Bei der Ausgangsausrichtung A werden die Teilquadrate in der Reihenfolge links unten, links oben, rechts oben und rechts unten besucht. Die vier Transformationen lauten: T₀(x,y) = (y/2,x/2), T₁(x,y) = (x/2,(y+1)/2), T₂(x,y) = ((x+1)/2,(y+1)/2), T₃(x,y) = ((2−y)/2,(1−x)/2). T₀ spiegelt an der Hauptdiagonalen, T₁ und T₂ verschieben ohne Spiegelung in die oberen Quadrate, und T₃ spiegelt an der Nebendiagonalen und verschiebt nach rechts unten. Dadurch berühren sich aufeinanderfolgende Quadrate stets an einer ganzen Seite. Im Polygon P_n sind daher alle Teilstrecken gleich lang, achsenparallel und nur durch Richtungswechsel von −90°, 0° oder 90° verbunden.

Insgesamt treten vier absolute Ausrichtungen A, B, C und D auf. Sie entstehen durch die Verkettung der relativen Drehungen und Spiegelungen aller vorherigen Stufen. Die zugehörigen Isometrien bilden eine Gruppe der Ordnung vier, die zur Kleinschen Vierergruppe isomorph ist. Entscheidend ist: Die Ausrichtung eines Teilquadrats hängt nur von der Ausrichtung seines übergeordneten Quadrats und von der aktuellen Ziffer τ_n ab, nicht von späteren Ziffern.

Endliche Raster, Algorithmen und Hilbert-Index

Für eine feste Iterationsstufe n bildet die diskrete Zuordnung ĥ_n die 4^n Parameterwerte aus I_(4^n) eindeutig auf die 2^n × 2^n Rasterpunkte aus I_(2^n)² ab. Die Punkte stehen für die linken unteren Ecken der Rasterquadrate; zur Darstellung des Hilbert-Polygons verwendet man meist deren Mittelpunkte (x_n+2^(−n−1), y_n+2^(−n−1)). P_n ist eine einfache Kurve mit Anfang und Ende, ohne Berührungen oder Überschneidungen.

Benachbarte Parameterwerte führen zu benachbarten Rasterpunkten. Insbesondere gilt |t−t′| ≤ 4^(−n) ⇒ |ĥ_n(t)−ĥ_n(t′)| ≤ 2^(−n). Diese Abschätzung führt im Grenzfall zur gleichmäßigen Stetigkeit.

Die Berechnung von t nach (x,y) kann rekursiv oder iterativ erfolgen. Rekursive Verfahren lesen Quaternärziffern, berechnen zunächst feinere Stufen und wenden beim Rückweg T₀ bis T₃ an. Ein iterativer ganzzahliger Algorithmus verarbeitet für p = 2^n einen Index t ∈ {0,…,p²−1} und liefert x,y ∈ {0,…,p−1}. Bitweises XOR und UND bestimmen das Teilquadrat; eine Hilfsfunktion rot dreht oder spiegelt die bisherigen Koordinaten. Eine explizite Rekursion kann umgekehrt von grob zu fein arbeiten. Sie beginnt beim Quadratmittelpunkt (1/2,1/2) mit Ausrichtung A und ergänzt anhand der aktuellen Ausrichtung und Quaternärziffer jeweils neue Koordinatenbits.

Die Umkehrfunktion der endlichen diskreten Abbildung heißt Hilbert-Index: k̂_n = ĥ_n^(−1). Damit gelten k̂_n ∘ ĥ_n = id und ĥ_n ∘ k̂_n = id auf den jeweiligen diskreten Mengen. Rekursive und iterative Algorithmen gewinnen aus den Binärziffern von x und y die Quaternärziffern von t. Der iterative ganzzahlige Algorithmus arbeitet von großen zu kleinen Quadraten, also von hochrangigen zu niedrigrangigen Stellen. Die Zuordnungen können durch vier Übersetzungstabellen beziehungsweise durch Zustandsübergänge für die Ausrichtungen A bis D beschrieben werden. Ein Zusammenfassen mehrerer Schritte, „recursion unrolling“, kann die Berechnung beschleunigen.

Grenzkurve und ihre Eigenschaften

Erst der Grenzübergang füllt das Quadrat vollständig. Für jedes t existiert h(t) = lim_(n→∞) h_n(t) = (x(t),y(t)), weil die zugehörigen geschachtelten Quadrate Seitenlängen 2^(−n) besitzen. Die Konvergenz ist gleichmäßig: Für ε > 0 kann N = ⌈−log₂(ε)⌉ gewählt werden; für n > N gilt für alle t der Abstand |h_n(t)−h(t)| < 2^(−n) ≤ ε.

Die Grenzabbildung h: [0,1] → [0,1]² ist wohldefiniert, surjektiv und gleichmäßig stetig, aber nicht injektiv. Sie ist sogar Hölder-stetig zum Exponenten 1/d; im zweidimensionalen Fall also zum Exponenten 1/2. Sie ist nirgends differenzierbar und maß-erhaltend: Eine Teilmenge des Parameterintervalls mit eindimensionalem Lebesgue-Maß μ wird auf eine Punktmenge mit d-dimensionalem Lebesgue-Maß μ abgebildet. Für die initiale Ausrichtung A besitzt sie die Symmetrie x(1−t)=1−x(t) und y(1−t)=y(t). Außerdem gilt aus T₀: Ist h(t)=(x,y), dann ist h(t/4)=(y/2,x/2).

Die Mehrdeutigkeit von Stellenwertdarstellungen verursacht keine Mehrdeutigkeit des Funktionswerts h: Beispielsweise stellen 0₄.2 mit anschließend nur Nullen und 0₄.1 mit anschließend nur Dreien beide 1/2 dar und führen zum selben Kurvenpunkt. Umgekehrt können jedoch verschiedene Parameter denselben Punkt ergeben. Beispiele sind h(1/12)=h(11/12)=(0,1/2), h(1/2)=h(1/6)=h(5/6)=(1/2,1/2) und h(5/48)=h(7/48)=h(41/48)=h(43/48)=(1/2,1/4). Jeder Punkt besitzt höchstens vier Parameterwerte als Urbilder; die Anzahlen 1, 2, 3 und 4 kommen alle vor. Punkte, deren beide Koordinaten keine abbrechende Binärdarstellung haben, besitzen genau ein Urbild.

Weil h nicht injektiv ist, existiert keine gewöhnliche Umkehrfunktion. An Punkten mit abbrechender Binärdarstellung einer Koordinate existiert auch lim k_n(x,y) nicht eindeutig. Durch die feste Entscheidung, einen Grenzpunkt jeweils der rechten oder linken beziehungsweise oberen oder unteren Intervallhälfte zuzuordnen, entstehen vier Rechtsinverse k_++, k_+−, k_−+ und k_−−. Für jede gilt h ∘ k_±± = id_Q. Sie sind Funktionen und injektiv, aber weder stetig noch surjektiv. Zusammen liefern ihre Werte genau alle Urbilder eines Punktes; außerhalb der problematischen Rasterlinien stimmen sie überein. Rationale Parameter werden von h auf Punkte mit rationalen Koordinaten abgebildet, und rationale Koordinaten liefern bei diesen Rechtsinversen rationale Parameter.

Symbolische Darstellung, Varianten und höhere Dimensionen

Als Lindenmayer-System, also als regelbasiertes Termersetzungssystem, verwendet die Hilbert-Kurve die Variablen A, B, C, D für Ausrichtungen, die Pfeile ↑, →, ↓, ← als Zeichen für Verbindungen und A als Startsymbol. Die Regeln sind A ⇒ D ↑ A → A ↓ B, B ⇒ C ← B ↓ B → A, C ⇒ B ↓ C ← C ↑ D und D ⇒ A → D ↑ D ← C. Wiederholtes Ersetzen erzeugt die folgenden Iterationen.

Bis auf Spiegelungen und Rotationen ist die Hilbert-Kurve die einzige zweidimensionale raumfüllende FASS-Kurve des Quadrats, deren Anfang und Ende an Ecken liegen. Die Moore-Kurve ist eine geschlossene Variante mit demselben Grundmuster. Ihre Übergänge wenden sich nach außen und innen; sie ist ebenfalls raumfüllend und hat ähnliche Nachbarschaftseigenschaften, verwendet aber alle acht Isometrien der Diedergruppe D₄. Gibt man die Selbstähnlichkeit auf, entstehen unendlich viele weitere stetig raumfüllende Konstruktionen.

In drei Dimensionen wird ein Würfel bei jedem Schritt in acht Teilwürfel zerlegt. Die möglichen Ausrichtungen gehören zu Untergruppen der 48-elementigen Würfelgruppe. Das dargestellte Beispiel „Hilbert-Kurve beta“ verwendet eine 24-elementige Isometriengruppe, die zur symmetrischen Gruppe S₄ isomorph ist. H. Haverkort zählt 920 „face-continuous“ dreidimensionale Hilbert-Kurven, bei denen aufeinanderfolgende Würfel eine Quadratfläche teilen, und insgesamt 10 694 807 verschiedene dreidimensionale Hilbert-Kurven, wenn auch Berührungen an Kanten oder Ecken zugelassen werden. Unterschieden werden unter anderem „facet-gated“, „edge-gated“ und „vertex-gated“ Kurven nach der Lage ihrer Übergänge. Die Hilbert-Kurve beta besitzt besonders gute Nachbarschaftseigenschaften: Bei drei von sechs untersuchten Kriterien erreicht sie Platz eins, bei den übrigen Platz zwei und liegt höchstens 4 % vom Optimum entfernt.

Hilbert-Kurven können auch für andere Gebiete als Quadrate effizient umgesetzt werden. Durch veränderte Durchlaufgeschwindigkeit lassen sich unterschiedliche Dichten berücksichtigen; Konstruktionen sind außerdem in beliebig höheren Dimensionen möglich.