Hilbert-Kurve

mini|Abb. 1: Hilbert-Polygone in sieben Iterationen, dazu die Hilbert-Kurve

In der Mathematik ist die Hilbert-Kurve eine (stetige) Kurve, die als Grenzkurve von Polygonzügen die Fläche eines Quadrats vollständig ausfüllt (siehe Abb. 1). Sie ist eine sogenannte FASS-Kurve, somit eine raumfüllende Kurve (engl. space-filling curve, abgekürzt SFC) und wurde 1891 von dem deutschen Mathematiker David Hilbert veröffentlicht.#Hilbert Die Möglichkeit, mit einer stetigen eindimensionalen Kurve ein zweidimensionales Gebiet komplett abdecken zu können, war den Mathematikern des 19. Jahrhunderts neu (siehe auch Monsterkurve).

Die Hilbert-Kurve wird durch eine rekursive Iteration definiert und konstruiert. Die -te Rekursionsstufe wird Hilbert-Kurve der -ten Iteration S. 18., , und der die Teilquadrate verbindende Polygonzug Hilbert-Polygon der -ten Iteration genannt. Die Hilbert-Kurven und die Hilbert-Polygone endlicher Iterationen haben denselben Grenzwert, nämlich die Hilbert-Kurve im engeren Sinn. Die euklidische Länge des Hilbert-Polygons ist , das heißt, sie wächst mit der Nummer der Iteration über alle Grenzen. Die Hilbert-Kurve hat im Limes eine Hausdorff-Dimension von exakt 2, genau wie das Quadrat.

Mithilfe der Hilbert-Kurve endlicher Iteration kann man die Teilquadrate und mithilfe des Limes die Punkte im Quadrat in eine lineare Reihenfolge bringen, die Hilbert-Ordnung genannt wird. Mit ihr lassen sich (effiziente) Verfahren, die auf einer linearen Ordnung beruhen, ins Mehrdimensionale übertragen. Dazu gehört binäres Suchen, binärer Suchbaum, Skip-Liste und andere.

mini|Abb. 2: Farbkodierte Entfernungstabelle von Orten auf der Hilbert-Kurve der 4. Iteration Beim direkten Zugriff steht die Hilbert-Ordnung in Konkurrenz zu einem Zugriff, bei dem die linearen Ordnungen der Dimensionen in unterschiedlicher Rangigkeit zu einer lexikographischen Ordnung hintereinander geschaltet sind – im internen Speicher über ein mehrfach indiziertes Feld resp. im externen Speicher per wahlfreien Zugriff (Random Access). Wenn sich dies gut organisieren lässt, schneidet sie etwas schlechter ab. Sie ist aber überlegen, wenn es sich um eine ungefähre Suche handelt, an die sich eine sequentielle Suche anschließt, bei der Nachbarschaftsbeziehungen (engl. clustering) vorteilhaft ausgenutzt werden können. Dies ist bei -dimensionalen Räumen , bei denen Nachbarschaft durch die euklidische Metrik definiert ist, häufig der Fall – beispielsweise, wenn auf geographische Merkmale eines Objekts über die Schlüssel Länge und Breite zugegriffen werden soll. Die Hilbert-Kurve ist beliebt aufgrund ihrer guten Nachbarschaftserhaltung.B. Moon, H.V. Jagadish, C. Faloutsos, and J.H. Saltz: Analysis of the clustering properties of the Hilbert space-filling curve. IEEE Transactions on Knowledge and Data Engineering, Vol. 13, No.1, January/February 2001.H. K. Dai, H. C. Su: Clustering Performance of 3-Dimensional Hilbert Curves. Lecture Notes in Computer Science. Springer-Verlag, 2014. Bei der Z-Kurve ist die Rechnung geringfügig einfacher, aber die Nachbarschaftserhaltung deutlich schlechter. S. 172.

Die Zuordnung der Hilbert-Kurve einer (endlichen) -ten Iteration ist umkehrbar und kann zu beliebiger Feinheit gesteigert werden. Dieses und die gute Nachbarschaftserhaltung hat eine Vielfalt von Anwendungen der Hilbert-Kurve in der Informatik eröffnet, so in der Bildverarbeitung, Datendarstellung, im HochleistungsrechnenM. Bader: Partitionierung der Menge der Variablen am Beispiel der Berechnung der Temperaturverteilung auf einer Metallplatte. und in anderen Gebieten.C. Pérez-Demydenko, I. Brito Reyes, E. Estevez-Rams, B. Aragón Fernández: Locality preserving homogeneous Hilbert curves by use of arbitrary kernels.

Konstruktion

Die Abb. 3a bis 3c aus dem definierenden Artikel zeigen die drei ersten Iterationen der Hilbert-Kurve. Bei der -ten Iteration bringen Nummern die Intervalle (Teilstrecken der Linie oben in den Grafiken) und die Quadrate mit gleichen Nummern zur Entsprechung. Die verstärkten polygonalen Linien bringen genau diese Reihenfolge der Quadrate heraus.

Eine nachfolgende Iteration verfeinert – bei Intervallen wie bei Quadraten – die Schachtelung um den Faktor 4.

Iterationsschritt Die Konstruktion der Hilbert-Kurve als einer raumfüllenden Kurve

beruht auf einem rekursiven Verfahren: Das Verfahren beginnt mit dem (mehrdimensionalen Einheits-Intervall) als dem zu füllenden Gebiet. Jedes Gebiet wird aufgeteilt in kongruente Teilgebiete Intervalle) der halben Seitenlänge und auf der Eingabeseite ein Intervall in gleich lange Teilintervalle. Das Verfahren überführt damit 1D-Schachtelungen von Intervallen in 2D-Schachtelungen von Quadraten (oder in 3D-Schachtelungen von Würfeln), ist also inklusionserhaltend. Für jedes Teilgebiet ist eine raumfüllende Kurve zu finden, die durch verkleinerte Verschiebung, Spiegelung und/oder Rotation der Vorgängerkurve gebildet wird. (Prinzip der Selbstähnlichkeit)Das Prinzip der Selbstähnlichkeit kann als ein Charakteristikum der Hilbert-Kurve angesehen werden. Andere Kriterien, wie z. B. die gleichförmige »Geschwindigkeit« oder die Berührung zweier Nachbargebiete an einer gemeinsamen -dimensionalen Zelle werden von den Autoren nicht so einheitlich der Hilbert-Kurve zugesprochen, denn auch die Berührung an nur Kanten oder nur Ecken führt im Limes zur Stetigkeit (s. a. den Abschnitt #Weiter gefasste Konstruktionsprinzipien). Die Spiegelungs- und Rotationsoperationen lassen sich so wählen, dass sich die Teilkurven zu einer einzigen gerichteten Kurve zusammenfügen.

Eine Hilbert-Kurve wird wesentlich durch die Reihenfolge charakterisiert, in der die Teilgebiete hintereinander aufgesucht (traversiert) werden. Mit wachsender Dimensionszahl wächst die Anzahl der unterschiedlichen Hilbert-Kurven, die sich dann auch in ihrer Nachbarschaftserhaltung stark unterscheiden können.

Dieser Artikel beschränkt sich fast ausschließlich auf die Dimensionszahl also auf die Abbildung des Einheitsintervalls auf das Einheitsquadrat Bei dieser Dimensionszahl treten alle einschlägigen mathematischen Phänomene bereits in Erscheinung.

Während die Hilbert-Kurve (auf der Ausgabeseite) ein „Teilquadrat“ durchläuft (füllt), soll auch der Parameter auf der Eingabeseite das ihm entsprechende Teilintervall durchlaufen. Dies entspricht der Vorgabe, dass die Hilbert-Kurve in allen Bereichen »gleich schnell« voranschreitet.

Um dies sicherzustellen, wird als Intervallschachtelung auf der Parameterseite die („4-adische“) Darstellung von im Quaternärsystem mit gewählt.Um Undeutlichkeiten oder Verwechslungsmöglichkeiten mit dem Komma der Notationen für Intervalle oder Koordinatenpaare gering zu halten, wird im Folgenden als Trennzeichen zu den Stellen mit negativen Exponenten der Punkt verwendet. Der Text folgt diesbezüglich M. Bader wie auch in der Platzierung der Basis als Präfix bei diesem Punkt. Es sei gesetzt, so dass     Wie üblich bedeutet bei einer -adischen Entwicklung ein Strich über den letzten Ziffern eine unendliche Wiederholung dieser Zifferngruppe, eine Periode. ein Intervall in der -ten Schachtelung des Parameters ist. Auf der Seite des Quadrats (Ausgabeseite) werden die Koordinaten und im Binärsystem („2-adisch“) dargestellt mit Die (abbrechenden) Koordinaten mit und stehen dabei für das Teilquadrat, das diese Koordinaten zur linken unteren Ecke hat. Und die Folge der durch spezifizierten Quadrate, die die Seitenlänge und die Fläche haben, macht eine 2D-Intervallschachtelung in der Ebene aus. Diese Schachtelungen seien als die „Rasterschachtelung“ (der Hilbert-Kurve) bezeichnet.

Die -te Iteration der „Hilbert-Kurve“ ist eine geordnete Folge von an genau einer Quadratseite mit dem Folgequadrat zusammenstoßenden Quadraten (oder deren linken unteren Eckpunkten resp. deren Mittelpunkten). Diese Folge wird am besten durch einen gerichteten Polygonzug von Quadratmittelpunkt

zu Quadratmittelpunkt (Parameter ) verdeutlicht. Dieser Polygonzug enthält alles Wichtige und wird häufig als das Hilbert-Polygon (engl. auch approximating curve und Hilbert pseudo curve) der -ten Iteration bezeichnet (Beispiele finden sich in den Hilbert-Kurven der 1. bis 3. Iteration der obigen Abbildungen).

Polygonzug Im Folgenden wird gezeigt, wie die Quadrate eines Rasters sämtlich in eine Reihenfolge gebracht werden, derart, dass sie bei wachsendem immer kleiner werden, einander näher rücken und im Limes eine Kurve bilden.

Im Sinn des obigen Programms sei rekursiv angenommen, dass in einem Teilquadrat ein Kurvenpunkt der selbstähnlichen Hilbert-Kurve berechnet ist. Es geht nun darum, diesen Punkt (resp. dieses Teilquadrat) so zu den anderen drei Teilquadraten in das Quadrat zu holen, dass alle solche Punkte zusammen genommen eine zusammenhängende Kurve (resp. eine zusammenhängende Folge von Teilquadraten des Rasters ) ergeben. Eine solche Transformation lässt sich zerlegen in:

|style="width:35em"| die Verkleinerung des Quadrats linear um den Faktor , || (Skal) |- | eine (die Hilbert-Kurve charakterisierende) Parallelverschiebung und || (Parv) |- | eine Isometrie (= orthogonale Abbildung = Drehung und/oder Spiegelung). || (Ausr)

Für die Wahl der passenden Drehungen und/oder Spiegelungen ist die Festlegung hilfreich, wo ein Quadrat einer Rasterschachtelung von der Kurve betreten und wo es verlassen wird. Bei der Hilbert-Kurve sind dies die Ecken genau einer Quadratseite.Entscheidet man sich für die Mitte einer Quadratseite statt für die Ecken, dann erhält man eine Abwandlung der hier definierten Hilbert-Kurve, nämlich die geschlossene Hilbert-Kurve nach Moore. Da es auch auf die Richtung und Orientierung ankommt, werde dieses Charakteristikum eines Quadrats im Raster mit dem Begriff „Ausrichtung“ (engl. orientation, stateJ. Lawder S. 53ff) versehen und die Ausrichtung „hoch—rechts—runter“ (in Koordinaten resp. die Strecke für „Eintritt links rechts unten“) mit dem Buchstaben gekennzeichnet. S. 31.

Aber auch die bloße Platzierung des Teilquadrats hängt von der Ausrichtung ab. Ist das große Quadrat (links in der Abbildung 4) gemäß ausgerichtet, dann wird bei der Hilbert-Kurve das Quadrat abhängig von der Quaternärziffer in eines der vier Teilquadrate platziert, und zwar platziert die Quaternärstelle nach links unten, nach links oben, nach rechts oben und nach rechts unten, also nach dem „Grundmuster“ (engl. base pattern oder basic patternSo M. Bader in der Vorlesung. „Grundmotiv“ bei Wunderlich) 20px.Das Grundmuster fällt in diesem Fall der 2-dimensionalen Hilbert-Kurve exakt mit der Ausrichtung zusammen.Im Gegensatz dazu hat die nicht-stetige Z-Kurve die parallele (nicht antiparallele) Anordnung 20px, bei der die Winkel (0,1,2) und (1,2,3) beliebig spitz werden können. Ein Grundmuster für die 3-dimensionale Hilbert-Kurve ist 22px (s. a. den Abschnitt Ausblick auf 3 Dimensionen).

Andere Ausrichtungen (als , und auch Platzierungsmuster) lassen sich durch eine vorgeschaltete Isometrie aus der Diedergruppe des Quadrats darstellen.

Die zur Herstellung des einfachen Zusammenhangs (und damit der Stetigkeit im Limes) erforderlichen Drehungen und/oder Spiegelungen sind ebenfalls Isometrien aus und zusammen mit der Platzierung auszuführen. Diese Kombination wird im folgenden Abschnitt unter dem Begriff „Transformation“ beschrieben.

Transformation der rekursiven Teilquadrate auf das Einheitsquadrat mini|240px|Abb. 4: Die Einbettung des Teilquadrats der -ten Iteration rechts resp. eines seiner Punkte in das 4 mal so große Quadrat links – in welches Teilquadrat und wie, wird von der Quaternärziffer abhängig gemacht.

Um den Wechsel der Ausrichtung von einer Iteration zur nächsten präzise zu erfassen, sei angenommen, dass beide Quadrate, das große (links in der Abbildung 4) wie das Teilquadrat (rechts) gleich, bspw. gemäß , ausgerichtet sind.

Die benötigten vier Transformationen S. 49. hängen von der Quaternärziffer ab und seien mit und bezeichnet:

|style="width:15em"| ||