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. 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 ekursive Iteration definiert und konstruiert. Die ${\displaystyle n}$-te Rekursionsstufe wird Hilbert-Kurve der ${\displaystyle n}$-ten Iteration, ${\displaystyle H_{n}}$, und der die Teilquadrate verbindende Polygonzug ${\displaystyle P_{n}}$ Hilbert-Polygon der ${\displaystyle n}$-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 ${\displaystyle P_{n}}$ ist ${\displaystyle (4^{n}-1)\,2^{-n}=2^{n}-2^{-n}}$, das heißt, sie wächst mit der Nummer ${\displaystyle n}$ 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.

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 ${\displaystyle d}$-dimensionalen Räumen ${\displaystyle \mathbb {R} ^{d}}$, 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. Bei der Z-Kurve ist die Rechnung geringfügig einfacher, aber die Nachbarschaftserhaltung deutlich schlechter.

Die Zuordnung ${\displaystyle h_{n}}$ der Hilbert-Kurve einer (endlichen) ${\displaystyle n}$-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 Hochleistungsrechnen und in anderen Gebieten.

1. ↑ #Hilbert
2. ↑ Michael Bader: Space-Filling Curves. An Introduction with Applications in Scientific Computing (= Timothy J. Barth, Michael Griebel, David E. Keyes, Risto M. Nieminen, Dirk Roose, Tamar Schlick [Hrsg.]: Texts in Computational Science and Engineering. Band 9). 1. Auflage. Springer-Verlag, 2013, ISBN 978-3-642-31045-4, ISSN 1611-0994, doi:10.1007/978-3-642-31046-1 (englisch, 278 S.).  S. 18.
3. ↑ 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.
4. ↑ H. K. Dai, H. C. Su: Clustering Performance of 3-Dimensional Hilbert Curves. Lecture Notes in Computer Science. Springer-Verlag, 2014.
5. ↑ Michael Bader: Space-Filling Curves. An Introduction with Applications in Scientific Computing (= Timothy J. Barth, Michael Griebel, David E. Keyes, Risto M. Nieminen, Dirk Roose, Tamar Schlick [Hrsg.]: Texts in Computational Science and Engineering. Band 9). 1. Auflage. Springer-Verlag, 2013, ISBN 978-3-642-31045-4, ISSN 1611-0994, doi:10.1007/978-3-642-31046-1 (englisch, 278 S.).  S. 172.
6. ↑ M. Bader: Partitionierung der Menge der Variablen am Beispiel der Berechnung der Temperaturverteilung auf einer Metallplatte.
7. ↑ 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.