Hilbert-Kurve

Datei:Hilbert curve!.gif

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.<ref name="Hilbert">#Hilbert</ref> 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 <math>n </math>-te Rekursionsstufe wird Hilbert-Kurve der <math>n </math>-ten Iteration<ref>{{#ifexist:Vorlage:bibISBN/{{#invoke:URIutil|plainISBN|978-3-642-31045-4}} | {{bibISBN/{{#invoke:URIutil|plainISBN|978-3-642-31045-4}}

  |record = Vorlage:bibISBN/{{#invoke:URIutil|plainISBN|978-3-642-31045-4}}
  |format = Literatur
  |Autor = 
  |Titel = 
  |TitelErg = 
  |Band = 
  |Auflage = 
  |Kommentar= 
  |Kapitel = 
  |Seite = 
  |Seiten = 
  |Spalten = 
  |ArtikelNr = 
  |Fundstelle = 
  |DOI = 
  |Online = 
  |URL = 
  |Linktext = 
  |Format = 
  |KBytes = 
  |Abruf = 
  |Typ = 

}}{{#ifeq: 0 | 0

   | {{#invoke:TemplatePar|check
       |all= 1=
       |opt= 2= format= Autor= Titel= TitelErg= Hrsg= Sammelwerk= WerkErg= Band= Nummer= Auflage= Datum= Sprache= NummerReihe= BandReihe= HrsgReihe= Kommentar= Kapitel= Seite= Seiten= Spalten= ArtikelNr= Fundstelle= DOI= Online= URL= Linktext= Format= KBytes= Abruf= Typ=

|template=Vorlage:bibISBN |cat=Wikipedia:Vorlagenfehler/Vorlage:BibISBN}}

     }}

| {{#if:||{{#ifeq: 0 | 0 | }}}}}} S. 18.</ref>, <math>H_n </math>, und der die Teilquadrate verbindende Polygonzug <math>P_n </math> Hilbert-Polygon der <math>n </math>-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 <math>P_n </math> ist <math>(4^n-1) \, 2^{-n} = 2^n - 2^{-n} </math>, das heißt, sie wächst mit der Nummer <math>n </math> 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.

Datei:Hilbert Index vs Distance.svg

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 <math>d </math>-dimensionalen Räumen <math>\R^d </math>, 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.<ref name="Moon">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.</ref><ref>H. K. Dai, H. C. Su: Clustering Performance of 3-Dimensional Hilbert Curves. Lecture Notes in Computer Science. Springer-Verlag, 2014.</ref> Bei der Z-Kurve ist die Rechnung geringfügig einfacher, aber die Nachbarschaftserhaltung deutlich schlechter.<ref>{{#ifexist:Vorlage:bibISBN/{{#invoke:URIutil|plainISBN|978-3-642-31045-4}} | {{bibISBN/{{#invoke:URIutil|plainISBN|978-3-642-31045-4}}

  |record = Vorlage:bibISBN/{{#invoke:URIutil|plainISBN|978-3-642-31045-4}}
  |format = Literatur
  |Autor = 
  |Titel = 
  |TitelErg = 
  |Band = 
  |Auflage = 
  |Kommentar= 
  |Kapitel = 
  |Seite = 
  |Seiten = 
  |Spalten = 
  |ArtikelNr = 
  |Fundstelle = 
  |DOI = 
  |Online = 
  |URL = 
  |Linktext = 
  |Format = 
  |KBytes = 
  |Abruf = 
  |Typ = 

}}{{#ifeq: 0 | 0

   | {{#invoke:TemplatePar|check
       |all= 1=
       |opt= 2= format= Autor= Titel= TitelErg= Hrsg= Sammelwerk= WerkErg= Band= Nummer= Auflage= Datum= Sprache= NummerReihe= BandReihe= HrsgReihe= Kommentar= Kapitel= Seite= Seiten= Spalten= ArtikelNr= Fundstelle= DOI= Online= URL= Linktext= Format= KBytes= Abruf= Typ=

|template=Vorlage:bibISBN |cat=Wikipedia:Vorlagenfehler/Vorlage:BibISBN}}

     }}

| {{#if:||{{#ifeq: 0 | 0 | }}}}}} S. 172.</ref>

Die Zuordnung <math>h_n </math> der Hilbert-Kurve einer (endlichen) <math>n </math>-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<ref>M. Bader: Partitionierung der Menge der Variablen am Beispiel der Berechnung der Temperaturverteilung auf einer Metallplatte.</ref> und in anderen Gebieten.<ref name="Demydenko">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.</ref>

{{#invoke:Vorlage:Anker|f |errCat=Wikipedia:Vorlagenfehler/Vorlage:Anker |errHide=1}}Konstruktion

• Abb. 3a: 1. Iteration <math>H_1 </math> der Hilbert-Kurve
  Abb. 3a: 1. Iteration <math>H_1 </math> der Hilbert-Kurve
• Abb. 3b: Hilbert-Kurve <math>H_2 </math> der 2. Iteration
  Abb. 3b: Hilbert-Kurve <math>H_2 </math> der 2. Iteration
• Abb. 3c: Hilbert-Kurve <math>H_3 </math> der 3. Iteration
  Abb. 3c: Hilbert-Kurve <math>H_3 </math> der 3. Iteration
• Abb. 3d: 3D-Hilbert-Kurven, 1. bis 3. Iteration
  Abb. 3d: 3D-Hilbert-Kurven, 1. bis 3. Iteration

Die Abb. 3a bis 3c aus dem definierenden Artikel<ref name="Hilbert" /> zeigen die drei ersten Iterationen der Hilbert-Kurve. Bei der <math>n </math>-ten Iteration bringen <math>4^n </math> Nummern die <math>4^n </math> Intervalle (Teilstrecken der Linie oben in den Grafiken) und die <math>4^n </math> Quadrate mit gleichen Nummern zur Entsprechung. Die verstärkten polygonalen Linien <math>P_n </math> bringen genau diese Reihenfolge der Quadrate heraus.<ref name="Sagan" />

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

<math>

\begin{array}{llllll} h \; \colon & \mathcal{I} := [0,1] := \{t \mid 0 \le t \le 1 \} & \to & \mathcal{I}^d & = & \;\; [0,1] \times [0,1] \times \dotso \\ & t & \mapsto & h(t) & = & (\;\;\; \underbrace{ x \;\;\;\; , \;\;\;\;\, y \;\;\;\; , \; \dotso }_{d \text{ Komponenten} } \;\;\; ) \\ \end{array} </math> beruht auf einem rekursiven Verfahren:

1. Das Verfahren beginnt mit dem (mehrdimensionalen Einheits-Intervall) <math>[0,1]^d = \mathcal{I}^d </math> als dem zu füllenden {{#if:trim|<math>d </math>-dimensionalen}} Gebiet.
2. Jedes Gebiet wird aufgeteilt in <math>2^d </math> kongruente Teilgebiete {{#if:trim|(<math>d </math>-dimensionale}} Intervalle) der halben Seitenlänge und auf der Eingabeseite ein Intervall in <math>2^d </math> 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.<ref name="Sagan" />
3. 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)<ref group="Anmerkung">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 <math>(d\!-\!1)</math>-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).</ref>
4. Die Spiegelungs- und Rotationsoperationen lassen sich so wählen, dass sich die <math>2^d </math> 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 <math>d </math> 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 {{#if:trim|}} also auf die Abbildung des Einheitsintervalls <math>\mathcal{I} </math> auf das Einheitsquadrat {{#if:trim|}} Bei dieser Dimensionszahl treten alle einschlägigen mathematischen Phänomene bereits in Erscheinung.

{{#invoke:Vorlage:Anker|f |errCat=Wikipedia:Vorlagenfehler/Vorlage:Anker |errHide=1}}Während die Hilbert-Kurve (auf der Ausgabeseite) ein „Teilquadrat“ durchläuft (füllt), soll auch der Parameter <math>t </math> 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 <math>t =: 0_4.\!\tau_1 \tau_2 \tau_3 \dotso \in \mathcal{I} </math> im Quaternärsystem mit <math>\tau_n \in \{0,1,2,3\} </math> gewählt.<ref group="Anmerkung">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 <math>b \in \{2,4\}</math> als Präfix bei diesem Punkt.</ref> Es sei <math>t_n := 0_4.\!\tau_1 \tau_2 \dotso \tau_n </math> gesetzt, so dass

<math>\{t \mid t_n \le t < t_n + 4^{-n} \} \;=\; [t_n, \, t_n + 4^{-n} [ \;\; = \; [\, 0_4.\!\tau_1 \tau_2 \dotso \tau_n, \; 0_4.\!\tau_1 \tau_2 \dotso \tau_n \overline{3} \,[ </math>     <ref group="Anmerkung">Wie üblich bedeutet bei einer <math>b</math>-adischen Entwicklung ein Strich über den letzten Ziffern eine unendliche Wiederholung dieser Zifferngruppe, eine Periode.</ref>

ein Intervall in der <math>n </math>-ten Schachtelung des Parameters <math>t </math> ist. Auf der Seite des Quadrats (Ausgabeseite) werden die Koordinaten <math>x =: 0_2.\! \xi_1 \xi_2 \xi_3 \dotso \in \mathcal{I}</math> und <math>y =: 0_2.\! \eta_1 \eta_2 \eta_3 \dotso \in \mathcal{I}</math> im Binärsystem („2-adisch“) dargestellt mit {{#if:trim|<math>\xi_n, \eta_n \in \{0,1\} </math>.}} Die (abbrechenden) Koordinaten <math>(x_n,y_n) \in \mathcal{I}^2 = \mathcal{Q} </math> mit <math>x_n := 0_2.\!\xi_1 \xi_2 \dotso \xi_n </math> und <math>y_n := 0_2.\!\eta_1 \eta_2 \dotso \eta_n </math> stehen dabei für das Teilquadrat, das diese Koordinaten zur linken unteren Ecke hat. Und die Folge der durch <math>\bigl((x_n,y_n)\bigr)_{n\in\N} </math> spezifizierten Quadrate, die die Seitenlänge <math>2^{-n} </math> und die Fläche <math>4^{-n} </math> haben, macht eine 2D-Intervallschachtelung in der Ebene aus. Diese {{#if:trim|<math>d </math>D-}}Schachtelungen seien als die „Rasterschachtelung“ <math>R := \bigl(R_n\bigr)_{n\in\N}</math> (der Hilbert-Kurve) bezeichnet.

Die <math>n </math>-te Iteration <math>H_n </math> der „Hilbert-Kurve“ ist eine geordnete Folge von <math>4^n </math> 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

<math>\bigl( \dot{x}_n(t), \dot{y}_n(t) \bigr) := \bigl( x_n(t) + 2^{-n-1}, y_n(t) + 2^{-n-1} \bigr) </math>

zu Quadratmittelpunkt (Parameter <math>t^\prime := t+4^{-n} </math>) verdeutlicht. Dieser Polygonzug <math>P_n </math> enthält alles Wichtige und wird häufig als das Hilbert-Polygon (engl. auch approximating curve<ref name="Haverkort2" /> und Hilbert pseudo curve) der <math>n </math>-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 <math>4^n </math> Quadrate eines Rasters <math>R_n </math> sämtlich in eine Reihenfolge <math>0,1,2,\dotso,4^n-1 </math> gebracht werden, derart, dass sie bei wachsendem <math>n </math> 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 <math>\in R_n </math> 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 <math>\in R_{n-1} </math> zu holen, dass alle solche Punkte zusammen genommen eine zusammenhängende Kurve (resp. eine zusammenhängende Folge von Teilquadraten des Rasters <math>R_n </math>) ergeben. Eine solche Transformation lässt sich zerlegen in:

die Verkleinerung des Quadrats linear um den Faktor <math>\tfrac12 </math>,	(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 <math>R_n </math> von der Kurve betreten und wo es verlassen wird. Bei der Hilbert-Kurve sind dies die Ecken genau einer Quadratseite.<ref group="Anmerkung">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.</ref> Da es auch auf die Richtung und Orientierung ankommt, werde dieses Charakteristikum eines Quadrats im Raster mit dem Begriff „Ausrichtung“ (engl. orientation<ref name="Moon" />, state<ref>J. Lawder S. 53ff</ref>) versehen und die Ausrichtung „hoch—rechts—runter“ (in Koordinaten <math>\scriptstyle \underset{y}{\uparrow} \underset{x}{\rightarrow} \underset{y}{\downarrow} </math> resp. die Strecke <math>{(0,0)\underline{\color{Mulberry}\bullet\!\!\!\color{Green}\to}(1,0)} </math> für „Eintritt links {{#if:trim|unten—Austritt}} rechts unten“) mit dem Buchstaben <math>\mathbf{A} </math> gekennzeichnet.<ref>{{#ifexist:Vorlage:bibISBN/{{#invoke:URIutil|plainISBN|978-3-642-31045-4}} | {{bibISBN/{{#invoke:URIutil|plainISBN|978-3-642-31045-4}}

  |record = Vorlage:bibISBN/{{#invoke:URIutil|plainISBN|978-3-642-31045-4}}
  |format = Literatur
  |Autor = 
  |Titel = 
  |TitelErg = 
  |Band = 
  |Auflage = 
  |Kommentar= 
  |Kapitel = 
  |Seite = 
  |Seiten = 
  |Spalten = 
  |ArtikelNr = 
  |Fundstelle = 
  |DOI = 
  |Online = 
  |URL = 
  |Linktext = 
  |Format = 
  |KBytes = 
  |Abruf = 
  |Typ = 

}}{{#ifeq: 0 | 0

   | {{#invoke:TemplatePar|check
       |all= 1=
       |opt= 2= format= Autor= Titel= TitelErg= Hrsg= Sammelwerk= WerkErg= Band= Nummer= Auflage= Datum= Sprache= NummerReihe= BandReihe= HrsgReihe= Kommentar= Kapitel= Seite= Seiten= Spalten= ArtikelNr= Fundstelle= DOI= Online= URL= Linktext= Format= KBytes= Abruf= Typ=

|template=Vorlage:bibISBN |cat=Wikipedia:Vorlagenfehler/Vorlage:BibISBN}}

     }}

| {{#if:||{{#ifeq: 0 | 0 | }}}}}} S. 31.</ref>

{{#invoke:Vorlage:Anker|f |errCat=Wikipedia:Vorlagenfehler/Vorlage:Anker |errHide=1}}Aber auch die bloße Platzierung des Teilquadrats hängt von der Ausrichtung ab. Ist das große Quadrat <math>\in R_{n-1} </math> (links in der Abbildung 4) gemäß <math>\mathbf{A} </math> ausgerichtet, dann wird bei der Hilbert-Kurve das Quadrat <math>\in R_n </math> abhängig von der Quaternärziffer <math>\tau = \tau_n </math> in eines der vier Teilquadrate platziert, und zwar platziert die Quaternärstelle <math>\tau=0</math> nach links unten, <math>\tau=1</math> nach links oben, <math>\tau=2</math> nach rechts oben und <math>\tau=3</math> nach rechts unten, also nach dem „Grundmuster“ (engl. base pattern<ref name="Haverkort2" /> oder basic pattern<ref>So M. Bader in der Vorlesung. „Grundmotiv“ bei Wunderlich</ref>) Datei:Hilbert curve Grundmotiv 2D.svg.<ref group="Anmerkung">Das Grundmuster fällt in diesem Fall der 2-dimensionalen Hilbert-Kurve exakt mit der Ausrichtung <math>\mathbf{A} </math> zusammen.</ref><ref group="Anmerkung" name="Z-Kurve">Im Gegensatz dazu hat die nicht-stetige Z-Kurve die parallele (nicht antiparallele) Anordnung Datei:Z curve Grundmotiv 2D.svg, bei der die Winkel (0,1,2) und (1,2,3) beliebig spitz werden können.</ref> Ein Grundmuster für die 3-dimensionale Hilbert-Kurve ist Datei:Hilbert curve Grundmotiv 3D.svg (s. a. den Abschnitt Ausblick auf 3 Dimensionen).

Andere Ausrichtungen (als <math>\mathbf{A} </math>, und auch Platzierungsmuster) lassen sich durch eine vorgeschaltete Isometrie aus der Diedergruppe <math>D_4 </math> des Quadrats darstellen.

Die zur Herstellung des einfachen Zusammenhangs (und damit der Stetigkeit im Limes) erforderlichen Drehungen und/oder Spiegelungen sind ebenfalls Isometrien aus <math>D_4 </math> 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

{{#invoke:Vorlage:Anker|f |errCat=Wikipedia:Vorlagenfehler/Vorlage:Anker |errHide=1}}

Datei:Hilbert curve recursive embedding!.svg

Abb. 4: Die Einbettung des Teilquadrats der <math>n</math>-ten Iteration rechts resp. eines seiner Punkte <math>{\color{Mulberry}\bullet} </math> in das 4 mal so große Quadrat links – in welches Teilquadrat und wie, wird von der Quaternärziffer <math>\tau:=\tau_n</math> 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äß <math>\mathbf{A} </math>, ausgerichtet sind.

Die benötigten vier Transformationen<ref name="Rose" /><ref>{{#ifexist:Vorlage:bibISBN/{{#invoke:URIutil|plainISBN|978-3-642-31045-4}} | {{bibISBN/{{#invoke:URIutil|plainISBN|978-3-642-31045-4}}

  |record = Vorlage:bibISBN/{{#invoke:URIutil|plainISBN|978-3-642-31045-4}}
  |format = Literatur
  |Autor = 
  |Titel = 
  |TitelErg = 
  |Band = 
  |Auflage = 
  |Kommentar= 
  |Kapitel = 
  |Seite = 
  |Seiten = 
  |Spalten = 
  |ArtikelNr = 
  |Fundstelle = 
  |DOI = 
  |Online = 
  |URL = 
  |Linktext = 
  |Format = 
  |KBytes = 
  |Abruf = 
  |Typ = 

}}{{#ifeq: 0 | 0

   | {{#invoke:TemplatePar|check
       |all= 1=
       |opt= 2= format= Autor= Titel= TitelErg= Hrsg= Sammelwerk= WerkErg= Band= Nummer= Auflage= Datum= Sprache= NummerReihe= BandReihe= HrsgReihe= Kommentar= Kapitel= Seite= Seiten= Spalten= ArtikelNr= Fundstelle= DOI= Online= URL= Linktext= Format= KBytes= Abruf= Typ=

|template=Vorlage:bibISBN |cat=Wikipedia:Vorlagenfehler/Vorlage:BibISBN}}

     }}

| {{#if:||{{#ifeq: 0 | 0 | }}}}}} S. 49.</ref> hängen von der Quaternärziffer <math>\tau \in \{0,1,2,3\} </math> ab und seien mit <math>T_0, T_1, T_2 </math> und <math>T_3</math> bezeichnet:

<math>T_1 \ := \ ( x , y ) \mapsto \bigl( \tfrac{x}2 , \tfrac{y+1}2 \bigr) </math>	<math>T_2 \ := \ ( x , y ) \mapsto \bigl( \tfrac{x+1}2 , \tfrac{y+1}2 \bigr) </math>
<math>T_0 \ := \ ( x , y ) \mapsto \bigl( \tfrac{y}2 , \tfrac{x}2 \bigr) </math>	<math>T_3 \ := \ ( x , y ) \mapsto \bigl( \tfrac{2-y}2 , \tfrac{1-x}2 \bigr) </math>

Alle Transformationen skalieren zunächst die übergebenen Koordinaten <math> ( x , y ) </math> des Punktes mit dem Faktor {{#if:trim|<math>\tfrac{1}2 </math>,}} da die Teilquadrate die halbe Seitenlänge haben, und enthalten eine Verschiebung in das durch <math>\tau </math> (s. o.) bestimmte Teilquadrat. Zudem ist von einer Transformation je nach Lage ggf. eine (von <math>\tau </math> abhängige) Viertelrotation, Spiegelung, d. h. eine Kongruenzabbildung <math>\in D_4 </math> durchzuführen:

• Bei <math>\tau \!=\! 0 </math> kommt die Transformation <math>T_0 </math> zum Zuge. Sie spiegelt ihr Argument an der »Hauptdiagonalen« (strichpunktiert in Abbildung 4), wodurch sich der Drehsinn des Quadrats ändert. Die Eintrittsecke ins Teilquadrat (links unten) bleibt erhalten.
  (Alle Übertritte von einem Quadrat zum nächsten sind in der Abbildung 7 als kurze blaugrüne Pfeile vom Grundmuster des einen Quadrats diagonal zur Austrittsecke und von der Eintrittsecke des anderen Quadrats diagonal zu dessen Grundmuster dargestellt.)
  Die Austrittsecke dieses Teilquadrats ist nachher links oben und führt zum nächsten Teilquadrat mit <math>\tau \!=\! 1 </math>.
• Die Zielquadrate bei den Transformationen <math>T_1 </math> und <math>T_2 </math> haben dieselbe Ausrichtung <math>\mathbf{A} </math> mit Eintrittsecke links unten und Austrittsecke rechts unten, daher ist keine Spiegelung (und keine Drehung) erforderlich. Jedoch wird die Kurve skaliert in je eines der oberen Teilquadrate verschoben.
  <math>T_1 </math> verschiebt bei <math>\tau \!=\! 1 </math> die Kurve um <math>\tfrac{1}2 </math> in {{#if:trim|<math>y </math>-Richtung,}} also ins linke obere Teilquadrat. <math>T_2 </math> verschiebt für <math>\tau \!=\! 2 </math> die Kurve diagonal ins rechte obere Teilquadrat.
  Die Eintrittsecke des Teilquadrats mit <math>\tau \!=\! 1 </math> fällt mit der Austrittsecke von <math>\tau \!=\! 0 </math> und die Austrittsecke von <math>\tau \!=\! 1 </math> mit der Eintrittsecke von <math>\tau \!=\! 2 </math> zusammen.
• Die Transformation <math>T_3 </math> spiegelt für <math>\tau \!=\! 3 </math> ihr Argument an der »Nebendiagonalen« (strichpunktiert in Abbildung 4), wodurch sich der Drehsinn des Quadrats ändert. Danach wird das gespiegelte Ergebnis um <math>\tfrac{1}2 </math> in {{#if:trim|<math>x </math>-Richtung,}} also ins rechte untere Teilquadrat verschoben, so dass die Eintrittsecke rechts oben liegt – an der Stelle der Austrittsecke des vorangehenden Teilquadrats mit <math>\tau \!=\! 2 </math> – und die Austrittsecke mit der Austrittsecke des Ausgangsquadrates übereinstimmt (rechts unten).

Ersichtlich sind die Punkte <math>(x,y) </math> über die sie enthaltenden Quadrate in eine Reihenfolge gebracht, die der Reihenfolge der Intervalle des Parameters <math>t </math> entspricht – sowohl bezüglich der 4 Teilquadrate <math>\in R_n </math> als auch bei den Anschlüssen zwischen zwei Quadraten <math>\in R_{n-1} </math>.

{{#invoke:Vorlage:Anker|f |errCat=Wikipedia:Vorlagenfehler/Vorlage:Anker |errHide=1}}Dabei findet der Übertritt von einem Quadrat zum nachfolgenden Nachbarquadrat immer nur über eine gemeinsame Quadratseite statt (s. kurze blaugrüne Pfeile in der Abbildung 7), sodass sich beim Polygonzug <math>P_n </math> von Quadratmittelpunkt zu Quadratmittelpunkt ausschließlich Teilstrecken gleicher Länge, der Seitenlänge, ergeben, die alle zu den Koordinatenachsen parallel und miteinander in einer linearen Kette verbunden sind – mit der offensichtlichen Konsequenz, dass die Hilbert-Kurve im Limes stetig ist. Die Teilstrecken des Polygons erfahren dabei nur Richtungswechsel <math>\in \{-90^\circ,0^\circ,90^\circ\}</math>.

{{#invoke:Vorlage:Anker|f |errCat=Wikipedia:Vorlagenfehler/Vorlage:Anker |errHide=1}}Die Abbildung 4 zeigt darüber hinaus, dass ausgehend von der Ausrichtung <math>\mathbf{A} </math> zwei neue (absolute) Ausrichtungen <math>\mathbf{D} </math> (:= „rechts—hoch—links“) und <math>\mathbf{B} </math> (:= „links—runter—rechts“) hinzukommen, und die Abbildungen 7 und 5, dass nur noch eine weitere Ausrichtung (:= „runter—links—hoch“), genannt <math>\mathbf{C} </math>, fehlt, so dass es bei insgesamt vier Ausrichtungen bleibt. Sie seien im Folgenden in der Menge <math>\mathbf{V} := \{\mathbf{A}, \mathbf{B}, \mathbf{C}, \mathbf{D} \} </math> zusammengefasst. Die zugehörige Gruppe <math>V </math> der benötigten Isometrien ist eine Untergruppe der Diedergruppe <math>D_4 </math> des Quadrats, wird erzeugt von der Drehung um 180° (Spiegelung am Quadratmittelpunkt) und einer Spiegelung an einer Diagonalen, hat also die Gruppenordnung vier, den Exponenten zwei und ist isomorph zur Kleinschen Vierergruppe.

{{#invoke:Vorlage:Anker|f |errCat=Wikipedia:Vorlagenfehler/Vorlage:Anker |errHide=1}}

Datei:Hilbert curve 3 Orient!.svg

Abb. 5: Hilbert-Polygone der ersten bis dritten Iteration.
Die Quadratmittelpunkte sind in der Reihenfolge des Hilbert-Index (Schrift gedreht) miteinander verbunden.
Der Hilbert-Index eines Teilquadrates mit Mittelpunkt <math>(x,y) </math> findet sich am Schnittpunkt von <math>x </math>-Spalte mit <math>y </math>-Zeile.
(Alle Angaben im Binärsystem)
Blass in den Quadratmitten die „absolute Ausrichtung“.
Bei 8 Punkten der finalen Hilbert-Kurve sind zugehörige Werte des Parameters <math>t = h^{-1}(x,y)</math> angegeben (grün).
Der Mittelpunkt <math>(\scriptstyle ^1\!/_2,^1\!/_2 \textstyle) </math> des großen (und jedes) Quadrats ist ein Tripelpunkt. Er hat <math>t = h^{-1}(\scriptstyle ^1\!/_2,^1\!/_2 \textstyle ) \, = \, \scriptstyle ^2\!/_{12}, ^6\!/_{12}, ^{10}\!/_{12} </math>.

In der Abbildung 5 ist das große Quadrat, das Quadrat der {{#if:trim|<math>0 </math>-ten}} Iteration (= Quadrat des Rasters <math>R_0 </math>), gemäß <math>\mathbf{A} </math> ausgerichtet – und dementsprechend in seiner Mitte gekennzeichnet. Die relativen Ausrichtungen der Quadrate höherer Iterationen sind rekursiv von Iteration zu Iteration den Regeln dieses Abschnitts entsprechend entwickelt und die Ergebnisse als absolute Ausrichtungen im Zentrum der Quadrate eingetragen. Als solche sind sie auf die initiale (absolute) Ausrichtung, hier <math>\mathbf{A}</math>, des Ausgangsquadrates bezogen. Die absolute Ausrichtung eines Quadrats ist also die Akkumulation (Komposition, Verkettung) der relativen Ausrichtungen aller seiner rekursiven Vorgänger mit der initialen Ausrichtung am Rekursionsanfang.<ref group="Anmerkung">Ist <math>\mathbf{A}</math> die initiale Ausrichtung, dann gibt es im Raster <math>R_n </math> (für <math>n>0 </math>) <math>4^{n-1}+2^{n-1} </math> Quadrate der (absoluten) Ausrichtung <math>\mathbf{A}</math>, <math>4^{n-1} </math> Quadrate der Ausrichtungen <math>\mathbf{B}</math> und <math>\mathbf{D}</math> und <math>4^{n-1}-2^{n-1} </math> Quadrate der Ausrichtung <math>\mathbf{C}</math>.</ref>

{{#invoke:Vorlage:Anker|f |errCat=Wikipedia:Vorlagenfehler/Vorlage:Anker |errHide=1}} Bemerkung 1

Weil im vorstehenden Abschnitt das Quadrat der Iteration <math>\in R_n </math> »zeitlich« vor dem großen Quadrat <math>\in R_{n-1} </math> als »vorhanden« angesehen wird, könnte man anzunehmen versucht sein, dass die (Ausrichtungen der) großen Quadrate (links) der höherwertigen Ziffern durch diejenigen späterer Iterationen (rechts) beeinflusst würden. Das Gegenteil ist jedoch der Fall:

• Die absolute Ausrichtung des großen Quadrats beeinflusst (zusammen mit der Quaternärziffer <math>\tau_n </math>) direkt die absolute Ausrichtung des Teilquadrats.

Das kann man übrigens schon beim Zeichnen von Hilbert-Polygonen zweier aufeinander folgender Iterationen feststellen, spielt für die Umkehrbarkeit der <math>h_n </math> (s. Abschnitt #Hilbert-Polygon) eine große Rolle und wirkt sich auf die (Art der) Stetigkeit von <math>h </math> (s. Abschnitt #Hilbert-Kurve) aus. Diese Abhängigkeit ist in der tabellarischen Abbildung 7 und im gleichwertigen Übergangsdiagramm der Abbildung 8 für alle vier vorkommenden Varianten (= Ausrichtungen) herausgearbeitet. Eine darauf basierende explizite Rekursionsformel für <math>h </math> wird im entsprechenden Abschnitt vorgestellt.

Diskrete Mathematik

In diesem Kapitel wird mit <math>n\in\N_0 </math> die endliche Iterationsstufe bezeichnet, die Einheitsintervalle <math>\check{\mathcal{I}} := \mathcal{I}\!\setminus\!\{1\} = [0,1[</math> und <math>\check{\mathcal{Q}}</math> sind oben halboffen, und für <math>m\in\N </math>, bspw. <math>m = 2^n</math> oder <math>m = 4^n </math>, ist

<math>\mathcal{I}_m := \{0,\tfrac1m,\tfrac2m, \dotso, 1-\tfrac1m\} = \{0,1,2,\dotso, m\!-\!1\} \cdot \tfrac1m \; \; \subset \check{\mathcal{I}}</math>

eine diskrete Menge von <math>m </math> Elementen.

Hilbert-Polygon

Die Zuordnung der Hilbert-Kurve <math>H_n </math> der <math>n </math>-ten Iteration ist

<math>

\begin{array}{lrlllll} h_n \; \colon & \check{\mathcal{I}} & \to & \check{\mathcal{Q}} & := & \;\; \check{\mathcal{I}} & \times & \check{\mathcal{I}} \\ & t & \mapsto & \displaystyle h_n(t) = h_n(t_n) & = & \bigl(x_n(t) = x_n(t_n) &, & y_n(t) = y_n(t_n) \bigr) \, . \\ \end{array} </math> Das Bild <math>h_n(\check{\mathcal{I}}) </math> ist eine diskrete Menge, und zwar ist

<math>h_n(\check{\mathcal{I}}) = \mathcal{I}_{2^n} \times \mathcal{I}_{2^n} = {\mathcal{I}_{2^n}}^2 </math>.

Die Koordinaten <math>\bigl( x_n(t), y_n(t) \bigr) </math> stehen dabei für linke untere Ecken von Quadraten des Rasters {{#if:trim|<math>R_n </math>.}} In graphischen Darstellungen wird die Reihenfolge der Quadrate, deretwegen ja der ganze Aufwand getrieben wird, am einfachsten durch Verbindungsstrecken zwischen den Quadraten sichtbar gemacht. Am deutlichsten wird diese Reihenfolge, wenn man statt der <math>4^n </math> Ecken die <math>4^n </math> Quadratmittelpunkte

<math>\bigl(\dot{x}_n(t), \, \dot{y}_n(t) \bigr) := \bigl(x_n(t) + 2^{-n-1}, \; y_n(t) + 2^{-n-1} \bigr) \qquad \qquad (t \in \mathcal{I}_{4^n}) </math>

nimmt, weil die Verbindungsstrecken verschiedener Iterationsstufen dann getrennt bleiben und Symmetrien klarer herauskommen. Dieser Polygonzug in der Ebene von Quadratmittelpunkt zu Quadratmittelpunkt wird häufig als das Hilbert-Polygon <math>P_n </math> der <math>n </math>-ten Iteration bezeichnet.<ref group="Anmerkung">Im Gegensatz dazu ist <math>H_n </math> eine endliche Ansammlung von Rasterpunkten ohne Verdeutlichung der Reihenfolge.
Der Parameter <math>t \in [0,1[</math> parametrisiert übrigens nicht die Verbindungsstrecken des Polygonzugs <math>P_n .</math></ref>

Die diskrete Funktion <math>\hat{h}_n := h_n\!\mid_{\mathcal{I}_{4^n}} </math>, d. i. die Einschränkung von <math>h_n </math> auf die diskrete Menge <math>\mathcal{I}_{4^n} </math>, ist umkehrbar und hat die Umkehrfunktion {{#if:trim|<math>\hat{k}_n </math>,}} die im Abschnitt Hilbert-Index behandelt wird. Nach Konstruktion ist ferner

<math>\hat{h}_n(t\pm 4^{-n}) \;\; \, = \;\; \,

\begin{cases} \hat{h}_n(t) \pm (2^{-n} \!\!\!\!\!\! & , \!\!\!\!\!\! & 0 & ) \\ \hat{h}_n(t) \pm (0 & , & 2^{-n} \!\!\!\!\!\! & ) \, , \end{cases} </math> woraus die Implikation

<math>|t-t^\prime| \le 4^{-n} \Longrightarrow \bigl|\hat{h}_n(t)-\hat{h}_n(t^\prime)\bigr| \le 2^{-n} </math>

(und im Limes die gleichmäßige Stetigkeit) folgt.

Datei:Hilbert Curve - 6.webm

Abb. 6: Hilbert-Polygon der 6. Iteration

Das Hilbert-Polygon <math>P_n </math> ist eine einfache Kurve mit Anfang, Ende und ohne Berührungen oder Überschneidungen. Wie in der Einleitung erwähnt, hat es die euklidische Länge <math>(4^n-1) \, 2^{-n} = 2^n - 2^{-n} </math>, die also mit <math>n </math> über alle Grenzen wächst. Alle Hilbert-Polygone derselben Iteration <math>n </math> sind einander ähnlich.

Die Animation der nebenstehenden Abb. 6 gibt einen Eindruck, wie lang die Wege in höheren Iterationen werden. Sie deutet auch an, wie das Hilbert-Polygon nach und nach den ganzen Ersten Quadranten der {{#if:trim|<math>(x,y)</math>-Ebene}} ausfüllen könnte: Wenn ein Quadrat fertig ist, dann ist der Polygonzug in der Richtung weg vom Ursprung fortzusetzen.

Die Bild- und die Definitionsmenge von <math>\hat{h}_n </math> lassen sich aufgrund ihrer Diskretheit in einfacher Weise so skalieren, dass sie ganzzahlig werden.

Bei den beiden folgenden Algorithmen t2xyR und t2xyI und beim Algorithmus xy2tR erfolgt die Auswertung (Hintereinanderausführung) der verketteten Transformationen wie bei Operatoren üblich rechts-assoziativ, also von rechts nach links.<ref group="Anmerkung">Diese Auswertungsrichtung von den niedrigrangigen Ziffern der {{#if:trim|<math>b</math>-adischen}} Darstellung zu den hochrangigen ähnelt dem Additionsverfahren abbrechender reeller Zahlen im Dezimalsystem, wie es in der Grundschule gelehrt wird.</ref> Innerhalb des Programms findet die Auswertung im rekursiven Aufstieg – also »auf dem Rückweg« (im hinteren Abschnitt) – statt, weshalb die Auswertungsrichtung als »fein zu grob« zu charakterisieren ist. Damit sich bei dieser Auswertungsrichtung überhaupt etwas ergibt, muss der »Hinweg« abgebrochen werden. Beim wie immer gearteten Abbruchkriterium (im Pseudocode t2xyR formuliert mit der Genauigkeitsvariablen eps) wird der Punkt <math>(x, y) </math>, wie in der Abb. 4 dargestellt, in dasjenige Rasterquadrat gebracht, das dem eingegebenen Teilintervall von <math>t </math> entspricht, und dieses Vorgehen wird wiederholt bei jedem iterativen Schritt zurück.

Bemerkung 2

Wie weiter oben schon bemerkt, suggeriert die Abb. 4 eine solche Auswertungsrichtung. Gleichwohl existiert eine Abhängigkeit des <math>n</math>-ten Quadrats von Teilen der {{#if:trim|<math>(n+1)</math>-sten}} oder höherer Iterationsstufe überhaupt nicht, weder hinsichtlich der Ziffern <math>\tau_\nu </math> (mit <math>\nu > n </math>) des Parameters <math>t </math> noch hinsichtlich der Ziffern <math>(\xi_\nu, \eta_\nu) </math> der Koordinaten <math>(x, y) </math> noch hinsichtlich der Ausrichtung der Quadrate. Wenn es eine Rekursion gibt, dann kann sie in der Richtung von »grob zu fein« aufgesetzt werden, bei der die Auswertung im rekursiven Abstieg erfolgt. Die hieraus hervorgehende Rekursionsformel hat den Vorteil, dass ein »Abbruchkriterium« nicht gebraucht wird. (Ein Ergebnis liegt bei einem Abbruch unmittelbar vor – einschließlich einer Angabe über die möglicherweise eingegangene Ungenauigkeit.) Sie zählt damit zu den potentiell unendlichen Verfahren und wird im Abschnitt #Explizite Rekursionsformel beispielhaft vorgestellt. Der einzige erkennbare Nachteil ist, dass die Eigenschaft der Ausrichtung eines Quadrats explizit gemacht werden muss und nicht in den Formeln für die Transformationen versteckt werden kann.

Rekursiver Algorithmus

Der nachfolgende Pseudocode t2xyR<ref>{{#ifexist:Vorlage:bibISBN/{{#invoke:URIutil|plainISBN|978-3-642-31045-4}} | {{bibISBN/{{#invoke:URIutil|plainISBN|978-3-642-31045-4}}

  |record = Vorlage:bibISBN/{{#invoke:URIutil|plainISBN|978-3-642-31045-4}}
  |format = Literatur
  |Autor = 
  |Titel = 
  |TitelErg = 
  |Band = 
  |Auflage = 
  |Kommentar= 
  |Kapitel = 
  |Seite = 
  |Seiten = 
  |Spalten = 
  |ArtikelNr = 
  |Fundstelle = 
  |DOI = 
  |Online = 
  |URL = 
  |Linktext = 
  |Format = 
  |KBytes = 
  |Abruf = 
  |Typ = 

}}{{#ifeq: 0 | 0

   | {{#invoke:TemplatePar|check
       |all= 1=
       |opt= 2= format= Autor= Titel= TitelErg= Hrsg= Sammelwerk= WerkErg= Band= Nummer= Auflage= Datum= Sprache= NummerReihe= BandReihe= HrsgReihe= Kommentar= Kapitel= Seite= Seiten= Spalten= ArtikelNr= Fundstelle= DOI= Online= URL= Linktext= Format= KBytes= Abruf= Typ=

|template=Vorlage:bibISBN |cat=Wikipedia:Vorlagenfehler/Vorlage:BibISBN}}

     }}

| {{#if:||{{#ifeq: 0 | 0 | }}}}}} S. 52.</ref> implementiert rekursiv die Abb. 4 mit <math>\mathbf{A} </math> als Ausrichtung für Zwischen- wie Endergebnis. Er nimmt als Argument einen Parameter <math>t \in \check{\mathcal{I}} </math> und eine Begrenzung eps<math>:= 2^{-n}</math> der Iterationstiefe. Zurückgegeben werden die Koordinaten der linken unteren Ecke eines Quadrates der <math>n</math>-ten Iteration.

Eingabe:	Parameter <math>t \in \check{\mathcal{I}} </math>
Ausgabe:	Koordinaten <math>x,y \in \check{\mathcal{I}} </math>
Auswertungsrichtung:	fein zu grob

<syntaxhighlight lang="d">

function t2xyR(t, eps) begin
  if eps > 1 then
    return (0, 0); // im Ergebnisquadrat die linke untere Ecke
  else
    q = floor(4*t);
    // Die Quaternärstelle q ∈ {0, 1, 2, 3} bestimmt,
    //   in welches Teilquadrat der Punkt gehört
    //   und wie er zu transformieren ist.
    r = 4*t − q;
    (x,y) = t2xyR(r, eps*2); // r ∈ I ↦ (x,y) ∈ Q
    switch q do
      case 0: return (y/2,         x/2);
      case 1: return (x/2,         y/2 + 1/2);
      case 2: return (x/2 + 1/2,   y/2 + 1/2);
      case 3: return (1−eps − y/2, 1/2−eps − x/2);
    end switch
  end if
end function

</syntaxhighlight>

{{#invoke:Vorlage:Anker|f |errCat=Wikipedia:Vorlagenfehler/Vorlage:Anker |errHide=1}}

Datei:Hilbert curve Quaternary Time vs Binary Coord.svg

Abb. 7: Die 4 Übersetzungs-
tabellen vom 4-adischen Parameter <math>{ \color{green} \tau } </math> zu den zwei 2-adischen Koordinaten <math>{ \color{red} (\xi,\eta) }</math>
– und zurück.
Pro „Ausrichtung“ eine Tabelle.

Iterativer Algorithmus mit ganzzahligen Ein-/Ausgabewerten

{{#invoke:Vorlage:Anker|f |errCat=Wikipedia:Vorlagenfehler/Vorlage:Anker |errHide=1}}Bei der folgenden iterativen Lösung ist <math>n </math> die Nummer der Iteration und <math>p := 2^n </math> die Anzahl der 1D-Teilintervalle. Zurückgegeben wird die linke untere Ecke eines Quadrats. Der folgende Pseudocode t2xyI hat ganzzahlige Ein-/Ausgabe (d. h. es wird nicht auf Einheitsintervall oder -quadrat skaliert).

Eingabe:	Parameter <math>t \in \{0,1,\dotso,p^2-1\} </math>
Ausgabe:	Koordinaten <math>x,y \in \{0,1,\dotso,p-1\} </math>
Auswertungsrichtung:	fein zu grob

{{#invoke:Vorlage:Anker|f |errCat=Wikipedia:Vorlagenfehler/Vorlage:Anker |errHide=1}} <syntaxhighlight lang="d">

function t2xyI(t, p) begin
  (x, y) = (0, 0); // im Ergebnisquadrat die linke untere Ecke
  for (m = 1; m < p; m *= 2) do // m wächst exponentiell
    rx = 1 & t/2;      // Binärziffer[1]: 0=links/1=rechts
    ry = 1 & (t ^ rx); // Binärziffer[0]
    (x, y) = rot(x, y, rx, ry, m);
    x += m * rx;
    y += m * ry;
    t /= 4; // zur nächsten Quaternärziffer
  end for
return (x, y);
end function

// Drehspiegelung eines Quadrates

function rot(x, y, rx, ry, p) begin
  if (ry == 0) then
    if (rx == 1) then
      x = p−1 − x;
      y = p−1 − y;
    end if
    // vertausche x und y
    z = x;
    x = y;
    y = z;
  end if
return (x, y);
end function

</syntaxhighlight>

Hierbei kommen die C-Operatoren ^ für bitweises XOR, & für bitweises UND, += für Inkrementieren, *=2 für Verdoppeln und /=2 für Halbieren zum Einsatz.

In der Funktion t2xyI bedeutet die Variable rx das Übereinstimmen des vorletzten Bits bei x und t; analog für ry und y mit dem letzten Bit.

Die Funktion (und ihre Umkehrung s. u.) benutzen die Funktion rot, um die Koordinaten x und y in einem Teilquadrat so zu spiegeln und zu drehen, dass die Teilstücke konsekutiv (stetig) zusammengefügt werden.

Explizite Rekursionsformel

Eingabe:	Parameter <math>t \in \check{\mathcal{I}} </math>
Ausgabe:	Koordinaten <math>x,y \in \check{\mathcal{I}} </math>
Auswertungsrichtung:	grob zu fein

Ist <math>t =: 0_4.\! \tau_1 \tau_2 \tau_3 \dotso \in \check{\mathcal{I}}</math> eine 4-adische Darstellung des Parameters, dann lässt sich die (unendliche) Folge <math>\bigl(h_n(t)\bigr)_{n\in\N} = \Bigl(\bigl(x_n(t) , y_n(t)\bigr)\Bigr)_{n\in\N} </math> auch als Rekursion<ref>T. Bially</ref> über die Quadratmittelpunkte

<math>\bigl(\dot{x}_n(t) := x_n(t) + 2^{-n-1}, \; \; \dot{y}_n(t) := y_n(t) + 2^{-n-1} \bigr) </math>

und die „absolute“ Ausrichtung <math>a_n </math> mit dem Rekursionsanfang

<math>\dot{x}_0(t) = \tfrac12 </math>	und
<math>\dot{y}_0(t) = \tfrac12 </math>	und
<math>a_0(t) = \mathbf{A} </math>	f |errCat=Wikipedia:Vorlagenfehler/Vorlage:Anker |errHide=1}}Wird hier die von einer eventuellen Vorgängerkette <math>t^\prime := \tau^\prime_1 \tau^\prime_2 \dotso \tau^\prime_{n^\prime} </math> als letzte (in Gl. RFh_a) errechnete Ausrichtung angegeben, dann ist der Funktionswert der Verkettung <math>t^\prime \circ t </math> gleich der Verkettung des Funktionswerts <math>h_{n^\prime}(t^\prime) </math> der Vorgängerkette mit dem Funktionswert <math>h_n(t) </math> dieser Ziffernkette:       <math>h_{n^\prime+n}(t^\prime \circ t) = h_{n^\prime}(t^\prime) \circ h_n(t),</math> wobei die Ergebnisse der beiden Koordinaten <math>(x,y) </math> separat zu verketten sind.</ref>

und dem Rekursionsschritt

<math>\dot{x}_n(t) </math>	<math> = \dot{x}_{n-1}(t) + 2^{-n-1} (2 X_{a_{n-1}(t), \, \tau_n} -1)</math>	(RFh_ξ),
<math>\dot{y}_n(t) </math>	<math> = \dot{y}_{n-1}(t) \ + 2^{-n-1} (2 Y_{a_{n-1}(t), \, \tau_n} -1)</math>	(RFh_η)<ref group="Anmerkung">Mit nur <math>X,Y</math> an Stelle von <math>2X-1,2Y-1</math> erhält man die linken unteren Ecken der Quadrate.</ref> und
<math>a_n(t) </math>	<math> = A_{a_{n-1}(t), \, \tau_n}</math>	(RFh_a)

für <math>n \in \N </math> schreiben. {{#invoke:Vorlage:Anker|f |errCat=Wikipedia:Vorlagenfehler/Vorlage:Anker |errHide=1}}Die drei {{#if:trim|(4×4)-Matrizen}}

<math>X :=

\left[\begin{smallmatrix}\begin{array}{rrrr}

0 & 0 & 1 & 1 \\
1 & 0 & 0 & 1 \\
1 & 1 & 0 & 0 \\
0 & 1 & 1 & 0

\end{array}\end{smallmatrix}\right]\!, \, Y := \left[\begin{smallmatrix}\begin{array}{rrrr}

0 & 1 & 1 & 0 \\
1 & 1 & 0 & 0 \\
1 & 0 & 0 & 1 \\
0 & 0 & 1 & 1

\end{array}\end{smallmatrix}\right]\!, \; A := \left[\begin{smallmatrix}\begin{array}{rrrr}

\mathbf{D} & \mathbf{A} & \mathbf{A} & \mathbf{B} \\
\mathbf{C} & \mathbf{B} & \mathbf{B} & \mathbf{A} \\
\mathbf{B} & \mathbf{C} & \mathbf{C} & \mathbf{D} \\
\mathbf{A} & \mathbf{D} & \mathbf{D} & \mathbf{C}

\end{array}\end{smallmatrix}\right] \;\; \begin{smallmatrix}\begin{array}{ll}

\leftarrow & \mathbf{A} \\
\leftarrow & \mathbf{B} \\
\leftarrow & \mathbf{C} \\
\leftarrow & \mathbf{D}

\end{array}\end{smallmatrix} \!\!\! \left. \begin{array}{c}

\, \\[13pt]
\,

\end{array}

\right\rbrace \scriptstyle \; = \; a

</math> sind äquivalent zu den vier Übersetzungstabellen der Abbildung 7. Sie werden an ihrem ersten Index, dem Zeilenindex, durch die absolute Ausrichtung <math>a_{n-1}(t) \in \mathbf{V} := \{\mathbf{A}, \mathbf{B}, \mathbf{C}, \mathbf{D} \}</math> indiziert. Das Ergebnis ist bei <math>X</math>, <math>Y</math> und <math>A</math> jeweils eine vierstellige Zeile, die zusammen genommen eine der Übersetzungstabellen darstellen. Jede Stelle (Spalte) einer solchen Zeile wird durch die Quaternärziffer <math>\tau_n \in \{0,1,2,3\}</math> indiziert. Daraus resultiert (Gl.n RFh_ξ und RFh_η) das neue Ziffernpaar <math>(\xi_n, \eta_n) </math> für den Punkt <math>(x,y)</math> und (Gl. RFh_a) die neue absolute Ausrichtung.

Die Folge <math>\bigl((\dot{x}_n,\dot{y}_n)\bigr)_{n\in\N} </math> der Quadratmittelpunkte mit <math>\dot{x}_n := 0_2.\!\xi_1 \xi_2 \dotso \xi_n + 2^{-n-1} </math> und <math>\dot{y}_n := 0_2.\!\eta_1 \eta_2 \dotso \eta_n + 2^{-n-1} </math>, steht für die 2D-Intervallschachtelung

<math>\begin{array}{lllll}

& \bigl([\dot{x}_n-2^{-n-1}, & \dot{x}_n+2^{-n-1}] & \times \; [\dot{y}_n-2^{-n-1}, & \dot{y}_n+2^{-n-1}]\bigr)_{n\in\N} \\ = & \bigl([x_n, & x_n+2^{-n}] & \times \; [y_n, & y_n+2^{-n}]\bigr)_{n\in\N} , \\ \end{array}</math> die <math>h(t) </math> zum Limes hat.

Beweis der Rekursionsformel

Die Gleichung RFh_a akkumuliert – wie in der Erläuterung zur Abb. 7 ausgeführt – die relativen Ausrichtungen<ref>{{#ifexist:Vorlage:bibISBN/{{#invoke:URIutil|plainISBN|978-3-642-31045-4}}

plainISBN|978-3-642-31045-4}}

plainISBN|978-3-642-31045-4}}

format = Literatur

Autor =

Titel =

TitelErg =

Band =

Auflage =

Kommentar=

Kapitel =

Seite =

Seiten =

Spalten =

ArtikelNr =

Fundstelle =

DOI =

Online =

URL =

Linktext =

Format =

KBytes =

Abruf =

Typ = }}{{#ifeq: 0 | 0

check

all= 1=

opt= 2= format= Autor= Titel= TitelErg= Hrsg= Sammelwerk= WerkErg= Band= Nummer= Auflage= Datum= Sprache= NummerReihe= BandReihe= HrsgReihe= Kommentar= Kapitel= Seite= Seiten= Spalten= ArtikelNr= Fundstelle= DOI= Online= URL= Linktext= Format= KBytes= Abruf= Typ=

template=Vorlage:bibISBN

cat=Wikipedia:Vorlagenfehler/Vorlage:BibISBN}} }}

{{#if:

Erläuterungen zu den Abbildungen 7 und 8

Die oberste der vier Graphiken der Abb. 7, die für die Ausrichtung <math>\mathbf{A} </math>, ist ein Auszug aus der Abb. 4. Aus der Abb. 5 kann man die Daten zur zweiten und vierten Ausrichtung <math>\mathbf{B} </math> und <math>\mathbf{D} </math> direkt ablesen; für die dritte Ausrichtung <math>\mathbf{C} </math> ergeben sie sich durch Übergang zum 4. Iterationsschritt in der Abb. 5. Da die Abb. 5 anhand der Regeln des Abschnitts #Transformation der rekursiven Teilquadrate auf das Einheitsquadrat erstellt ist, werden diese Regeln auch von der Abb. 7 (und von den Matrizen <math>X,Y,A </math> (s. o.) und den Hypermatrizen <math>T,A' </math> (s. u.)) eingehalten. Die vier Graphiken unterscheiden sich hinsichtlich des Charakteristikums Ausrichtung durch eine der Isometrien aus der Gruppe {{#if:trim|<math>V </math>.}} Anmerkungen Die Abbildung zeigt bei jeder der vier Ausrichtungen nur einen einzigen Rekursionsschritt. Das Zusammenfassen mehrerer Rekursionsschritte zu einem Schritt, also das Verbreitern der Ein- und Ausgabe auf mehr als eine Ziffer (bei beiden, 4-adischem Parameter und 2-adischen Koordinaten), ist eine reine Fleißaufgabe,<ref>T. Bially zitiert nach J. Lawder section 4.3.1 Generating State Diagrams by Hand S. 54</ref> durch die die Matrizen entsprechend vergrößert werden. Es bleibt aber bei der Anzahl vier hinsichtlich der Übersetzungstabellen, die der Anzahl <math>v </math> der Ausrichtungen entspricht. Das Verfahren bezeichnet M. Bader<ref>{{#ifexist:Vorlage:bibISBN/{{#invoke:URIutil|plainISBN|978-3-642-31045-4}}

plainISBN|978-3-642-31045-4}}

plainISBN|978-3-642-31045-4}}

format = Literatur

Autor =

Titel =

TitelErg =

Band =

Auflage =

Kommentar=

Kapitel =

Seite =

Seiten =

Spalten =

ArtikelNr =

Fundstelle =

DOI =

Online =

URL =

Linktext =

Format =

KBytes =

Abruf =

Typ = }}{{#ifeq: 0 | 0

check

all= 1=

opt= 2= format= Autor= Titel= TitelErg= Hrsg= Sammelwerk= WerkErg= Band= Nummer= Auflage= Datum= Sprache= NummerReihe= BandReihe= HrsgReihe= Kommentar= Kapitel= Seite= Seiten= Spalten= ArtikelNr= Fundstelle= DOI= Online= URL= Linktext= Format= KBytes= Abruf= Typ=

template=Vorlage:bibISBN

cat=Wikipedia:Vorlagenfehler/Vorlage:BibISBN}} }}

{{#if:

Hilbert-Index

Die Funktion <math>h_n </math> hat die Definitionsmenge <math>\check{\mathcal{I}} </math>, die Einschränkung <math>\hat{h}_n = h_n\!\mid_{\mathcal{I}_{4^n}} </math> die Definitionsmenge <math>\mathcal{I}_{4^n} </math>, beide haben die Bildmenge {{#if:trim|}}^2 </math>,}} die eine diskrete Menge ist. Die Funktion <math>\hat{h}_n </math> ist umkehrbar mit der Umkehrfunktion

<math>

\begin{array}{lllll} \hat{k}_n \; \colon & \mathcal{I}_{2^n} &\times & \mathcal{I}_{2^n} &\to & \mathcal{I}_{4^n} \\

& ( x &, & y ) &\mapsto & \hat{k}_n(x,y) := \hat{h}_n^{-1}(x,y) \; , \\

\end{array} </math> welche Hilbert-Index genannt wird. Sie hat ihrerseits die Bildmenge <math>\mathcal{I}_{4^n} </math>. Unter den Einschränkungen auf die diskreten Mengen <math>\mathcal{I}_{4^n} </math> resp. <math>{\mathcal{I}_{2^n}}^2 </math> sind die Funktionen <math>\hat{h}_n </math> wie <math>\hat{k}_n </math> umkehrbar eindeutig und es gilt <math>\hat{k}_n \circ \hat{h}_n = \operatorname{id}_{\mathcal{I}_{4^n}} </math> und <math>\hat{h}_n \circ \hat{k}_n = \operatorname{id}_{{\mathcal{I}_{2^n}}^2} </math>.<ref group="Anmerkung">Das lässt sich durch Abzählen leicht feststellen, denn bei jedem Iterationsschritt von <math>h_n </math> werden genau 4 Teilintervalle in genau 4 Teilquadrate abgebildet.</ref>

{{#invoke:Vorlage:Anker|f |errCat=Wikipedia:Vorlagenfehler/Vorlage:Anker |errHide=1}}Werden ihre Argumente <math>x_n := 0_2.\!\xi_1 \xi_2 \dotso \xi_n \in \mathcal{I}_{2^n} </math> und <math>y_n := 0_2.\!\eta_1 \eta_2 \dotso \eta_n \in \mathcal{I}_{2^n} </math> gleichermaßen als Binärbrüche entwickelt, dann kann man auch beliebige {{#if:trim|(<math>\infty </math>-stellige}}) Koordinaten <math>x =: 0_2.\! \xi_1 \xi_2 \xi_3 \dotso \in \check{\mathcal{I}}</math> und <math>y =: 0_2.\! \eta_1 \eta_2 \eta_3 \dotso \in \check{\mathcal{I}}</math> zulassen, in der zu definierenden Funktion <math>k_n </math> als erstes die Stellen rechts ab der <math>(n+1) </math>-ten Stelle abschneiden,<ref group="Anmerkung">Andere Rundungsregeln führen nur zu Verschiebungen des Ergebnisses.</ref> sodann <math>\hat{k}_n </math> ausführen, die Einschränkung auf die diskrete Menge <math>{\mathcal{I}_{2^n}}^2 </math> wieder aufheben und somit das ganze Einheitsquadrat <math>\check{\mathcal{I}}^2 = \check{\mathcal{Q}} </math> zur Definitionsmenge der Funktion

<math>

\begin{array}{lllll} k_n \; \colon & \check{\mathcal{I}} &\times & \check{\mathcal{I}} &\to & \mathcal{I}_{4^n} \; \subset \; \check{\mathcal{I}} \\ & ( x &, & y ) &\mapsto & k_n(x,y) \; , \\ \end{array} </math> erklären, so dass deren Einschränkung <math>k_n\!\mid_{{\mathcal{I}_{2^n}}^2} </math> der Funktion <math>\hat{k}_n </math> vom Eingang des Abschnitts entspricht. Somit ergibt sich für alle <math>n\in\N </math> sowohl

<math>k_n \circ h_n\!\mid_{\mathcal{I}_{4^n}} = \operatorname{id}_{\mathcal{I}_{4^n}} </math>

wie

<math>h_n \circ k_n\!\mid_{{\mathcal{I}_{2^n}}^2} = \operatorname{id}_{{\mathcal{I}_{2^n}}^2} . </math>

Die Rückabwicklung der Transformationen <math>T_0, T_1, T_2 </math> und <math>T_3</math> ist in den nachfolgenden Algorithmen im Einzelnen ausgeführt.

{{#invoke:Vorlage:Anker|f |errCat=Wikipedia:Vorlagenfehler/Vorlage:Anker |errHide=1}}

Rekursiver Algorithmus

Die Auswertungsrichtung des Algorithmus xy2tR<ref>{{#ifexist:Vorlage:bibISBN/{{#invoke:URIutil|plainISBN|978-3-642-31045-4}} | {{bibISBN/{{#invoke:URIutil|plainISBN|978-3-642-31045-4}}

  |record = Vorlage:bibISBN/{{#invoke:URIutil|plainISBN|978-3-642-31045-4}}
  |format = Literatur
  |Autor = 
  |Titel = 
  |TitelErg = 
  |Band = 
  |Auflage = 
  |Kommentar= 
  |Kapitel = 
  |Seite = 
  |Seiten = 
  |Spalten = 
  |ArtikelNr = 
  |Fundstelle = 
  |DOI = 
  |Online = 
  |URL = 
  |Linktext = 
  |Format = 
  |KBytes = 
  |Abruf = 
  |Typ = 

}}{{#ifeq: 0 | 0

   | {{#invoke:TemplatePar|check
       |all= 1=
       |opt= 2= format= Autor= Titel= TitelErg= Hrsg= Sammelwerk= WerkErg= Band= Nummer= Auflage= Datum= Sprache= NummerReihe= BandReihe= HrsgReihe= Kommentar= Kapitel= Seite= Seiten= Spalten= ArtikelNr= Fundstelle= DOI= Online= URL= Linktext= Format= KBytes= Abruf= Typ=

|template=Vorlage:bibISBN |cat=Wikipedia:Vorlagenfehler/Vorlage:BibISBN}}

     }}

| {{#if:||{{#ifeq: 0 | 0 | }}}}}} S. 58.</ref> ist entgegen der Intervallschachtelung.

Eingabe:	Koordinaten <math>x,y \in \check{\mathcal{I}} </math>
Ausgabe:	Parameter <math>t \in \check{\mathcal{I}} </math>
Auswertungsrichtung:	fein zu grob

<syntaxhighlight lang="d">

function xy2tR(x, y, eps) begin
  if eps > 1 then
    return 0; // im Ergebnisintervall der linke Rand
  end if
  eps *= 2;
  if x < 1/2 then
    if y < 1/2 then
      return ( 0 + xy2tR(2*y, 2*x, eps) )/4;
    else
      return ( 1 + xy2tR(2*x, 2*y − 1, eps) )/4;
    end if
  else
    if y >= 1/2 then
      return ( 2 + xy2tR(2*x − 1, 2*y − 1, eps) )/4;
    else
      return ( 3 + xy2tR(1−eps − 2*y, 2−eps − 2*x, eps) )/4;
    end if
  end if
end function

</syntaxhighlight>

Iterativer Algorithmus mit ganzzahligen Ein-/Ausgabewerten

Auch diese Aufgabe lässt sich iterativ programmieren. Die iterative Funktion xy2tI arbeitet in Richtung Schachtelung, in der Binär- oder Quaternärdarstellung also von hochrangigen Ziffern zu niedrigrangigen, geometrisch von einem großen Quadrat zu einem der 4 Teilquadrate. Sie benutzt die bei t2xyI eingeführte Unterfunktion rot.

Ist <math>n </math> die Nummer der Iteration, dann ist <math>p := 2^n </math> die Anzahl der 1D-Teilintervalle.

Eingabe:	Koordinaten <math>x,y \in \{0,1,\dotso,p-1\}</math>
Ausgabe:	Parameter <math>t \in \{0,1,\dotso,p^2-1\} </math>
Auswertungsrichtung:	grob zu fein

<syntaxhighlight lang="d">

function xy2tI(x, y, p) begin
  t = 0; // Summationsanfang
  for (p /= 2; p >= 1; p /= 2) do
    rx = (x & p) > 0;
    ry = (y & p) > 0;
    t += p * p * ((3 * rx) ^ ry);
    (x, y) = rot(x, y, rx, ry, p);
  end for
  return t;
end function

</syntaxhighlight>

{{#invoke:Vorlage:Anker|f |errCat=Wikipedia:Vorlagenfehler/Vorlage:Anker |errHide=1}}

Datei:Hilbert Curve. Quaternary vs Binary Coord. State Diagram.svg

Abb. 8: Die Ausrichtung <math>\in \mathbf{V} = \{\mathbf{A}, \mathbf{B}, \mathbf{C}, \mathbf{D} \} </math> bestimmt den großen Kasten. In jedem 4 kleine Kästen, wo sich Quaternärziffer <math>{ \color{green} \tau } </math> des Parameters und Binärziffern <math>{ \color{red} (\xi,\eta) }</math> der 2 Koordinaten gegen­über­stehen; eines ist Schlüssel, das andere Wert. Der Schlüssel bestimmt den kleinen Kasten und damit den Wert und die nächste Ausrichtung.
Die runden Pfeile verweisen auf den großen Kasten mit dieser Ausrichtung.

Rekursionsformel für den Hilbert-Index

Eingabe:	Koordinaten <math>x,y \in \check{\mathcal{I}} </math>
Ausgabe:	Parameter <math>t \in \check{\mathcal{I}} </math>
Auswertungsrichtung:	grob zu fein

Sind <math>x =: 0_2.\! \xi_1 \xi_2 \xi_3 \dotso \in \check{\mathcal{I}}</math> und <math>y =: 0_2.\! \eta_1 \eta_2 \eta_3 \dotso \in \check{\mathcal{I}}</math> Darstellungen der Koordinaten <math>(x,y) </math> im Binärsystem, dann lässt sich die (unendliche) Folge <math>\bigl(k_{n}(x,y) \bigr)_{n\in\N} </math> auch als Rekursion mit dem Rekursionsanfang

<math>\tau_0(x,y) = 0 </math>

und

<math>a_0(x,y) = \mathbf{A} </math>

(Start mit der initialen Ausrichtung <math>\mathbf{A}</math>)<ref group="Anmerkung" name="kVerkettung">Wird hier die von 2 eventuellen Vorgängerketten <math>x^\prime := \xi^\prime_1 \xi^\prime_2 \dotso \xi^\prime_{n^\prime} </math> und <math>y^\prime := \eta^\prime_1 \eta^\prime_2 \dotso \eta^\prime_{n^\prime} </math> als letzte (in Gl. Fk_a) errechnete Ausrichtung angegeben, dann ist das Ergebnis für die verketteten Koordinaten <math>(x^\prime \circ x, \, y^\prime \circ y) </math> gleich der Verkettung des Funktionswerts <math>k_{n^\prime}(x^\prime,y^\prime) </math> der Vorgängerkette mit dem Funktionswert dieser Ziffernkette. Fazit Bei beiden Richtungen, <math>k </math> und <math>h </math>, kann die Bildung der Ziffernkette(n) beliebig unterbrochen werden, wenn bei der Wiederaufnahme der Rekursion die zuletzt produzierte (absolute) Ausrichtung als initiale Ausrichtung eingegeben wird.</ref>

und dem Rekursionsschritt

<math>\tau_n(x,y) </math>	<math>= T_{a_{n-1}(x,y), \, \xi_n, \, \eta_n}</math>	(RFk_τ)
<math>a_n(x,y) </math>	<math>= A'_{a_{n-1}(x,y), \, \xi_n, \, \eta_n}</math>	(RFk_a)

für <math>n \in \N </math> schreiben. {{#invoke:Vorlage:Anker|f |errCat=Wikipedia:Vorlagenfehler/Vorlage:Anker |errHide=1}}Die zwei {{#if:trim|(4×2×2)-Hypermatrizen}}

<math>\begin{array}{c} T :=

\begin{bmatrix} \left[\begin{smallmatrix}\begin{array}{rr}

0 & 1 \\
3 & 2

\end{array}\end{smallmatrix}\right] \\ \left[\begin{smallmatrix}\begin{array}{rr}

2 & 1 \\
3 & 0

\end{array}\end{smallmatrix}\right] \\ \left[\begin{smallmatrix}\begin{array}{rr}

2 & 3 \\
1 & 0

\end{array}\end{smallmatrix}\right] \\ \left[\begin{smallmatrix}\begin{array}{rr}

0 & 3 \\
1 & 2\end{array}\end{smallmatrix}\right]

\end{bmatrix}, \end{array} \; \; \begin{array}{c} A' := \begin{bmatrix} \left[\begin{smallmatrix}\begin{array}{rr}

\mathbf{D} & \mathbf{A} \\
\mathbf{B} & \mathbf{A}

\end{array}\end{smallmatrix}\right] \\ \left[\begin{smallmatrix}\begin{array}{rr}

\mathbf{B} & \mathbf{B} \\
\mathbf{A} & \mathbf{C}

\end{array}\end{smallmatrix}\right] \\ \left[\begin{smallmatrix}\begin{array}{rr}

\mathbf{C} & \mathbf{D} \\
\mathbf{C} & \mathbf{B}

\end{array}\end{smallmatrix}\right] \\ \left[\begin{smallmatrix}\begin{array}{rr}

\mathbf{A} & \mathbf{C} \\
\mathbf{D} & \mathbf{D}

\end{array}\end{smallmatrix}\right] \end{bmatrix} \\ \end{array} \qquad \; \; \begin{array}{c} \begin{matrix} \left. \begin{smallmatrix}\begin{array}{rr}

\, \\
\,

\end{array}\end{smallmatrix} \right\rbrack \scriptstyle \; \leftarrow \; \mathbf{A} \\ \left. \begin{smallmatrix}\begin{array}{rr}

\, \\
\,

\end{array}\end{smallmatrix} \right\rbrack \scriptstyle \; \leftarrow \; \mathbf{B} \\ \left. \begin{smallmatrix}\begin{array}{rr}

\, \\
\,

\end{array}\end{smallmatrix} \right\rbrack \scriptstyle \; \leftarrow \; \mathbf{C} \\ \left. \begin{smallmatrix}\begin{array}{rr}

\, \\
\,

\end{array}\end{smallmatrix} \right\rbrack \scriptstyle \; \leftarrow \; \mathbf{D} \end{matrix} \!\! \left. \begin{array}{c}

\, \\[47pt]
\,

\end{array}

\right\rbrace \scriptstyle \; = \; a

\end{array} </math> sind zusammen genommen äquivalent zu den vier Übersetzungstabellen der Abbildung 7. Sie werden an ihrem ersten Index durch die absolute Ausrichtung <math>a_{n-1}(x,y) \in \mathbf{V}</math> indiziert. Das Ergebnis ist bei <math>T</math> wie bei <math>A'</math> eine {{#if:trim|(2×2)-Untermatrix.}} Jedes solche Paar von Untermatrizen stellt eine Übersetzungstabelle dar. Eine Untermatrix wird durch das Binärziffernpaar <math>(\xi_n, \eta_n) </math> indiziert. Daraus resultiert (Gl. RFk_τ) die neue Quaternärziffer <math>\tau_n</math> für den Parameter <math>t</math> und (Gl. RFk_a) die neue absolute Ausrichtung {{#if:trim|<math>a_n(x,y) </math>.}}

Beweis der Rekursionsformel für die Umkehrfunktion Hilbert-Index

Das kleine Quadrat (rechts in der Abb. 4) bekommt gemäß (Gl. RFk_τ) im großen Quadrat eine Nummer {{#if:trim|}} die der (absoluten) Ausrichtung <math>a_{n-1}(x,y) </math> des großen Quadrats sowie der Lage des kleinen Quadrats im großen Quadrat, nämlich den Ziffern {{#if:trim|<math>(\xi_n,\eta_n) </math>,}} entspricht. Erstere legt fest, welche der 4 Übersetzungstabellen in Abb. 7 anzuwenden ist, und letztere legen fest, ob das kleine Quadrat ins linke untere (bei <math>(\xi_n,\eta_n) = (0,0) </math>), ins linke obere (bei <math>(\xi_n,\eta_n) = (0,1) </math>) etc. Teilquadrat gehört, woraus die Ziffer <math>\tau_n := \tau </math> resultiert. Dies geschieht in Einklang mit den Transformationen <math>T_0 </math> bis <math>T_3 </math> aus dem Abschnitt #Transformation der rekursiven Teilquadrate auf das Einheitsquadrat, denn die Gleichung (RFk_a), die die absolute Ausrichtung rekursiv festlegt, ist eine Akkumulation<ref>{{#ifexist:Vorlage:bibISBN/{{#invoke:URIutil|plainISBN|978-3-642-31045-4}}

plainISBN|978-3-642-31045-4}}

plainISBN|978-3-642-31045-4}}

format = Literatur

Autor =

Titel =

TitelErg =

Band =

Auflage =

Kommentar=

Kapitel =

Seite =

Seiten =

Spalten =

ArtikelNr =

Fundstelle =

DOI =

Online =

URL =

Linktext =

Format =

KBytes =

Abruf =

Typ = }}{{#ifeq: 0 | 0

check

all= 1=

opt= 2= format= Autor= Titel= TitelErg= Hrsg= Sammelwerk= WerkErg= Band= Nummer= Auflage= Datum= Sprache= NummerReihe= BandReihe= HrsgReihe= Kommentar= Kapitel= Seite= Seiten= Spalten= ArtikelNr= Fundstelle= DOI= Online= URL= Linktext= Format= KBytes= Abruf= Typ=

template=Vorlage:bibISBN

cat=Wikipedia:Vorlagenfehler/Vorlage:BibISBN}} }}

{{#if:

Analysis

Im Limes, also bei exakt <math>n = \infty </math>, kommt – wie ein Blitz aus heiterem Himmel – ein neues Problem auf, nämlich der plötzliche Verlust der umkehrbaren Eindeutigkeit sowohl bei der 4- wie bei der 2-adischen Darstellung.

Darüber hinaus müssen wegen der Limites   <math>0_4.\!\overline{3} = 1 = 0_2.\!\overline{1}</math>   anstelle der halboffenen Intervalle <math>\check{\mathcal{I}} </math> und <math>\check{\mathcal{Q}} </math> ihre abgeschlossenen Hüllen <math>\bar{\check{\mathcal{I}}} = \mathcal{I} </math> und <math>\bar{\check{\mathcal{Q}}} = \mathcal{Q} </math> betrachtet werden.

Hilbert-Kurve

Mit den Hilbert-Kurven <math>H_n </math> (und den Hilbert-Polygonen <math>P_n </math>) lässt sich zu jedem positiven Abstand <math>\varepsilon > 0 </math> eine Iterationsstufe <math>n \in \N </math> angeben, so dass es zu jedem Punkt <math>(x,y) \in \mathcal{Q} </math> des Einheitsquadrats einen Punkt <math>(x_n,y_n) </math> des Rasters <math>R_n </math> gibt, der einen kleineren Abstand <math>\bigl|(x_n,y_n) - (x,y)\bigr| < \varepsilon </math> hat. Das bedeutet aber nicht die vollständige Füllung des Quadrats. Diese kann nur durch den Übergang zum Limes erreicht werden. Der Limes

<math>

\begin{array}{lllll} h \; \colon & \mathcal{I} & \to & \mathcal{Q} = & \mathcal{I} &\times & \mathcal{I} \\ & t & \mapsto & \displaystyle \lim_{n\to\infty} h_n(t) := \lim_{n\to\infty} & \bigl(x_n(t) &, & y_n(t) \bigr) & =: \; \; \bigl(x(t) , y(t) \bigr) \\ \end{array} </math> existiert immerhin, da er aus der 2D-Intervallschachtelung

<math>\Bigl(\bigl[x_n(t), x_n(t) + 2^{-n}\bigr] \times \bigl[y_n(t), y_n(t) + 2^{-n}\bigr] \Bigr)_{n\in\N} </math>

hervorgeht. Die Konvergenz ist eine gleichmäßige im folgenden Sinn: Für jedes <math>\varepsilon > 0 </math> ist <math>N := \bigl\lceil \! - \! \log_2(\varepsilon)\bigr\rceil </math> so, dass für alle Parameter <math>t \in \mathcal{I} </math> und alle <math>n \in \N </math> mit <math>n>N </math>

<math>\Bigl|\bigl(x_n(t), y_n(t)\bigr) - \bigl(x(t), y(t)\bigr)\Bigr| < 2^{-n} \le \varepsilon </math>

gilt.

Eigenschaften

1. <math>h </math> ist rechtseindeutig, somit wohldefiniert und eine Funktion.
2. <math>h \, \colon \, \mathcal{I} \to \mathcal{Q} </math> ist surjektiv.
3. <math>h </math> ist nicht injektiv.
4. <math>h </math> ist stetig, definiert also eine Kurve. Die Stetigkeit ist eine gleichmäßige.
5. Die Bilder des durch 3 geteilten Rasters <math>\mathcal{I}_{3 \cdot 4^n} </math> sind genau die Eckpunkte <math>\mathcal{I}_{2^n} \times \mathcal{I}_{2^n} </math> der entsprechenden Rasterquadrate.
6. <math>h\Biggl(\frac{\lfloor 4^n t \rfloor}{4^n}\Biggr) = h_n(t)</math> .
7. {{#invoke:Vorlage:Anker|f |errCat=Wikipedia:Vorlagenfehler/Vorlage:Anker |errHide=1}}Ist <math>\mathbf{A} </math> die initiale Ausrichtung, dann ist <math>h </math> symmetrisch zur Geraden <math>x = \tfrac12 </math>:
         Für jedes <math>t \in \mathcal{I} </math> ist <math>x(1-t) = 1-x(t) </math>   und   <math>y(1-t) = y(t) </math>.
   Bei <math>\mathbf{D} </math> als initialer Ausrichtung wäre es die Gerade <math>y = \tfrac12 </math>
         und <math>x(1-t) = x(t) </math>   und   <math>y(1-t) = 1-y(t) </math>.
8. Ist <math>h(t) = (x,y) </math>, dann ist
         <math>h\Bigl(\frac{t}4\Bigr) = \Bigl(\frac{y}2,\frac{x}2\Bigr) </math>.
9. Ist <math>t =: 0_4.\!\tau_1 \tau_2 \tau_3 \dotso \in \Q </math> rational, dann ist seine 4-adische Darstellung periodisch, bspw. <math>t =: 0_4.\!\tau_1 \tau_2 \dotso \tau_k \overline{\sigma_1 \dotso \sigma_l} </math> mit der Periodenlänge <math>l </math>. Die Koordinaten <math>(x,y) </math> von <math>h(t) \in \Q^2 </math> sind dann beide ebenfalls rational mit einer 2-adischen Periodenlänge <math>\le v l </math>, wobei <math>v = 4 </math> die Mächtigkeit der Menge <math>\mathbf{V} </math> der Ausrichtungen ist.<ref name="Wunderlich">#Wunderlich</ref>
10. <math>h </math> ist nirgends differenzierbar.<ref name="Hilbert" /><ref name="Sagan">#Sagan</ref>
11. <math>h </math> ist {{#if:trim|Maß-erhaltend:}} Für jede Punktmenge <math>S \subset \mathcal{I} </math> mit ein-dimensionalem Lebesgue-Maß <math>\mu </math> hat das Bild <math>\cup_{t\in S} h(t) </math> das {{#if:trim|<math>d </math>-dimensionale}} Lebesgue-Maß <math>\mu </math>.<ref name="Haverkort2">H. Haverkort, 2017</ref> Das bedeutet auch, dass jedes Intervall <math>\subset \mathcal{I} </math> in eine zusammenhängende (möglicherweise unendliche) Folge <math>\bigl(Q_i\bigr)_{i\in\Z} </math> von Quadraten der Rasterschachtelung abgebildet wird.

Beweise der Eigenschaften

Zu Eigsch. 1:   <math>h </math> ist Funktion. In der Tat ist <math>h </math> nicht von vornherein wohldefiniert, weil beim Übergang von einer reellen Zahl zu ihrer Quaternärentwicklung eine Weggabelung existiert: Zu einem gekürzten Bruch mit Zweierpotenz im Nenner, also zu einem Element <math>t \in E_2 := \N_0 2^{-\N_0} \, \cap \; ]0,1[ </math><ref group="Anmerkung" name="E2">Die Menge <math>E_2 </math> ist dicht in <math>\mathcal{I} </math> und hat das Maß 0.</ref>, gibt es zwei Möglichkeiten der Darstellung. Beispielsweise hat der Bruch <math>t = \tfrac12 </math> die Darstellung mit einem periodischen {{#if:trim|04. …0-Ende}} <math>\tfrac12 = \displaystyle 2 \cdot 4^{-1} + \sum_{n=2}^\infty 0 \cdot 4^{-n} = 0_4.2\overline{0} </math> (die als die »abbrechende Darstellung« bezeichnet wird, weil sie auch als endliche 4-adische Summe geschrieben werden kann) und die mit einem {{#if:trim|04. …3-Ende}} <math>\tfrac12 = \displaystyle 1 \cdot 4^{-1} + \sum_{n=2}^\infty 3 \cdot 4^{-n} = 0_4.1\overline{3} </math> . Diese Wahlmöglichkeit (Gleichheit) ist bei endlicher Stellenzahl (entspricht hier der Iterationsstufe) nicht gegeben, wo zwei verschiedene Ziffernfolgen immer verschiedene Werte haben; sie stellt aber im Fall <math>\textstyle n = \infty </math> die Forderung der Rechtseindeutigkeit an die Relation <math>h </math> in Frage. Im Folgenden wird aber gezeigt, dass sie sich nicht auf das Ergebnis von <math>h </math> auswirkt.<ref>{{#ifexist:Vorlage:bibISBN/{{#invoke:URIutil|plainISBN|978-3-642-31045-4}}

plainISBN|978-3-642-31045-4}}

plainISBN|978-3-642-31045-4}}

format = Literatur

Autor =

Titel =

TitelErg =

Band =

Auflage =

Kommentar=

Kapitel =

Seite =

Seiten =

Spalten =

ArtikelNr =

Fundstelle =

DOI =

Online =

URL =

Linktext =

Format =

KBytes =

Abruf =

Typ = }}{{#ifeq: 0 | 0

check

all= 1=

opt= 2= format= Autor= Titel= TitelErg= Hrsg= Sammelwerk= WerkErg= Band= Nummer= Auflage= Datum= Sprache= NummerReihe= BandReihe= HrsgReihe= Kommentar= Kapitel= Seite= Seiten= Spalten= ArtikelNr= Fundstelle= DOI= Online= URL= Linktext= Format= KBytes= Abruf= Typ=

template=Vorlage:bibISBN

cat=Wikipedia:Vorlagenfehler/Vorlage:BibISBN}} }}

{{#if:

plainISBN|978-3-642-31045-4}}

plainISBN|978-3-642-31045-4}}

format = Literatur

Autor =

Titel =

TitelErg =

Band =

Auflage =

Kommentar=

Kapitel =

Seite =

Seiten =

Spalten =

ArtikelNr =

Fundstelle =

DOI =

Online =

URL =

Linktext =

Format =

KBytes =

Abruf =

Typ = }}{{#ifeq: 0 | 0

check

all= 1=

opt= 2= format= Autor= Titel= TitelErg= Hrsg= Sammelwerk= WerkErg= Band= Nummer= Auflage= Datum= Sprache= NummerReihe= BandReihe= HrsgReihe= Kommentar= Kapitel= Seite= Seiten= Spalten= ArtikelNr= Fundstelle= DOI= Online= URL= Linktext= Format= KBytes= Abruf= Typ=

template=Vorlage:bibISBN

cat=Wikipedia:Vorlagenfehler/Vorlage:BibISBN}} }}

{{#if:

Einige Zahlenbeispiele

Parameter <math>t </math>

<math>0 </math>

<math>\tfrac{1}{3} </math>

<math>\tfrac{2}{3} </math>

<math>1 </math>

<math>\tfrac{2}{5} </math>

<math>\tfrac{1}{4} </math>

<math>\tfrac{1}{5}</math>

<math>\tfrac{1}{7}</math>

<math>\tfrac{1}{9}</math>

<math>\tfrac{1}{11}</math>

<math>\tfrac{1}{13}</math>

<math>\tfrac{1}{17}</math>

<math>\tfrac{1}{19}</math>

<math>h(t) </math>

<math>x(t) </math>

<math>0 </math>

<math>0 </math>

<math>1 </math>

<math>1 </math>

<math>\tfrac{1}{3} </math>

<math>0 </math>

<math>\tfrac{1}{5}</math>

<math>\tfrac{26}{63}</math>

<math>\tfrac{1}{3}</math>

<math>\tfrac{14}{33}</math>

<math>\tfrac{1}{3}</math>

<math>\tfrac{1}{5}</math>

<math>\tfrac{76}{511}</math>

<math>y(t) </math>

<math>0 </math>

<math>1 </math>

<math>1 </math>

<math>0 </math>

<math>1 </math>

<math>\tfrac{1}{2} </math>

<math>\tfrac{2}{5}</math>

<math>\tfrac{19}{63}</math>

<math>\tfrac{2}{9}</math>

<math>\tfrac{1}{11}</math>

<math>0</math>

<math>0</math>

<math>\tfrac{55}{511}</math>

Mehrfachpunkte

Parameter <math>t </math>

<math>\tfrac{1}{12} </math>

<math>\tfrac{11}{12}</math>

<math>\tfrac{1}{10}</math>

<math>\tfrac{9}{10}</math>

<math>\tfrac{3}{20}</math>

<math>\tfrac{17}{20}</math>

<math>\tfrac{9}{52}</math>

<math>\tfrac{25}{52}</math>

<math>\tfrac18 </math>

<math>\tfrac1{24} </math>

<math>\tfrac5{24} </math>

<math>\tfrac{1}{2} </math>

<math>\tfrac{1}{6} </math>

<math>\tfrac{5}{6} </math>

<math>\tfrac{5}{48}</math>

<math>\tfrac{7}{48}</math>

<math>\tfrac{41}{48}</math>

<math>\tfrac{43}{48}</math>

<math>h(t) </math>

<math>x(t) </math>

<math>\tfrac12 </math>

<math>\tfrac12 </math>

<math>\tfrac12 </math>

<math>\tfrac12 </math>

<math>\tfrac12 </math>

<math>\tfrac12 </math>

<math>\tfrac13 </math>

<math>\tfrac13 </math>

<math>\tfrac14 </math>

<math>\tfrac14 </math>

<math>\tfrac14 </math>

<math>\tfrac12 </math>

<math>\tfrac12 </math>

<math>\tfrac12 </math>

<math>\tfrac12 </math>

<math>\tfrac12 </math>

<math>\tfrac12 </math>

<math>\tfrac12 </math>

<math>y(t) </math>

<math>0 </math>

<math>0 </math>

<math>\tfrac16 </math>

<math>\tfrac16 </math>

<math>\tfrac13 </math>

<math>\tfrac13 </math>

<math>\tfrac12 </math>

<math>\tfrac12 </math>

<math>\tfrac14 </math>

<math>\tfrac14 </math>

<math>\tfrac14 </math>

<math>\tfrac12 </math>

<math>\tfrac12 </math>

<math>\tfrac12 </math>

<math>\tfrac14 </math>

<math>\tfrac14 </math>

<math>\tfrac14 </math>

<math>\tfrac14 </math>

<ref name="Rose" />

Umkehrfunktion

Da <math>h = \textstyle \lim_{n\to\infty} h_n</math> im Limes nicht injektiv ist, ist es auch nicht umkehrbar. Dies ist so, obwohl die diskreten <math>\hat{h}_n </math> für alle endlichen <math>n\in\N </math> umkehrbar sind und sowohl <math>k_n \circ \textstyle h_n\!\mid_{\mathcal{I}_{4^n}} = \operatorname{id}_{\mathcal{I}_{4^n}} </math> wie <math>h_n \circ \textstyle k_n\!\mid_{{\mathcal{I}_{2^n}}^2} = \operatorname{id}_{{\mathcal{I}_{2^n}}^2} </math> gilt. Die Nicht-Umkehrbarkeit drückt sich auch darin aus, dass der Limes

<math>

\begin{array}{lllll} k \; \colon & [0,1] & \times & [0,1] & \to & [0,1] \\ & ( x &, & y ) & \mapsto & \displaystyle \lim_{n\to\infty} k_n(x,y) \\ \end{array} </math> nicht existiert an den Punkten, wo eine der beiden Koordinaten <math>x </math> oder <math>y </math> eine {{#invoke:Vorlage:Anker|f |errCat=Wikipedia:Vorlagenfehler/Vorlage:Anker |errHide=1}}abbrechende Binärdarstellung hat, also in

<math>E_2 := \N_0 2^{-\N_0} \, \cap \; ]0,1[ </math>

liegt. Nach der im Beweis der Nicht-Injektivität von <math>h </math> gemachten Bemerkung hat <math>h </math> genau an diesen Stellen mehr als ein Urbild.

Eine Art Umkehrung <math>k </math> kann jedoch auch an diesen Stellen definiert werden durch die Vorschrift, dass die {{#if:trim|betreffende(n)}} {{#if:trim|Koordinate(n)}} <math>x </math> oder/und <math>y </math>, wenn sie bei einem Rekursionsschritt genau auf die Mitte eines Intervalls der Schachtelung fallen,

der rechten (der oberen) Intervallhälfte zuzuschlagen und damit als {{#if:trim|02. …0-Ende}}

(Vorschrift „+“ oder <math>\searrow</math>)

oder

der linken (der unteren) Intervallhälfte und somit als 02. …1-Ende

(Vorschrift „−“ oder <math>\nearrow</math>)

zu behandeln sind. Da <math>h</math> stetig ist, erfüllen die so konstruierten Urbilder <math>t</math> die Beziehung {{#if:trim|}} Es gibt somit (mindestens) vier verschiedene<ref group="Anmerkung">Es sind noch andere Funktionsvorschriften für die Umkehrfunktion denkbar. Zum Beispiel folgende:
Ist <math>(x,y)\in (E_2 \times \mathcal{I}) \cup (\mathcal{I} \times E_2) </math> ein Punkt, bei dem im Laufe der <math>n </math>-ten Iteration bspw. die Koordinate <math>x_n </math> genau auf die Intervallmitte fällt, dann sollen (nicht einheitlich wie in den vorigen Beispielen, sondern) abhängig von der absoluten Ausrichtung oder einer anderen Gegebenheit des Rasters <math>R_n </math> die restlichen Ziffern <math>\xi_\nu </math> (mit <math>\nu > n </math>) als {{#if:trim|0₂. …10-Ende}} oder eben als {{#if:trim|0₂. …01-Ende}} aufgefasst werden. Das Ergebnis an diesem Punkt entspricht sicherlich einem <math>k_{uv}(x,y) </math> für ein Paar <math>(u,v) \in \{+,-\}^2 </math>, ohne mit ihm an anderen Punkten übereinzustimmen.</ref> Funktionen

1. <math>k_{++}(x,y) := \lim_{n\to\infty,\,\xi \searrow x,\,\eta \searrow y} \; k_n(\xi,\eta) </math> ,
2. <math>k_{+-}(x,y) := \lim_{n\to\infty,\,\xi \searrow x,\,\eta \nearrow y} \; k_n(\xi,\eta) </math> ,
3. <math>k_{-+}(x,y) := \lim_{n\to\infty,\,\xi \nearrow x,\,\eta \searrow y} \; k_n(\xi,\eta) </math> und
4. <math>k_{--}(x,y) := \lim_{n\to\infty,\,\xi \nearrow x,\,\eta \nearrow y} \; k_n(\xi,\eta) </math> ,

die sich an den Stellen unterscheiden, an denen eine der beiden Koordinaten in <math>E_2 </math> liegt. An diesen Stellen sind die Funktionen <math>k_{\pm\pm} </math> auch nicht stetig.

Eine solche Funktion <math>k_{\pm\pm} </math> wird als Rechtsinverse (auch „Koretraktion“) von <math>h</math> bezeichnet.<ref group="Anmerkung">Zu jeder surjektiven Funktion gibt es Koretraktionen, und wenn sie nicht injektiv ist (wie hier), deren mehrere. Für eine Konstruktion bedarf es hier – wie gezeigt – nicht des Auswahlaxioms.</ref> {{#invoke:Vorlage:Anker|f |errCat=Wikipedia:Vorlagenfehler/Vorlage:Anker |errHide=1}}Sie erfüllt die Beziehung

<math>h \circ k_{\pm\pm} = \operatorname{id}_{\mathcal{Q}} </math> ,

die gleichbedeutend ist mit der Implikation

<math>t = k_{\pm\pm}(x,y) \; \; \Longrightarrow \; \; h(t)=(x,y) </math> .

Eigenschaften

1. Alle <math>k_{++}, k_{+-}, k_{-+}, k_{--} </math> sind Funktionen.
2. Die Lösungsmenge <math>\bigl\{t \in \mathcal{I} \mid h(t) = (x,y)\bigr\} </math> zu einem Punkt <math>(x,y) \in \mathcal{Q} </math> ist<ref name="Hilbert">#Hilbert</ref>
         <math>\bigl\{k_{++}(x,y), \; k_{+-}(x,y), \; k_{-+}(x,y), \; k_{--}(x,y)\bigr\} </math>.
   Alle Elementeanzahlen, 1, 2, 3 und 4, kommen vor.
3. Alle Funktionen <math>k_{++}, k_{+-}, k_{-+}, k_{--} </math> sind injektiv.
4. Eingeschränkt auf <math>F_2 = (\mathcal{I} \setminus E_2)^2 </math> ist <math>k </math> eindeutig, also
         <math>k_{++}(x,y) = k_{+-}(x,y) = k_{-+}(x,y) = k_{--}(x,y) </math> für <math>(x,y) \in F_2 .</math>
5. Die Urbilder der Eckpunkte
         <math>k_{++}, k_{+-}, k_{-+}, k_{--} \; \colon \; \mathcal{I}_{2^n} \times \mathcal{I}_{2^n} \to \mathcal{I}_{3 \cdot 4^n} </math>
   der Rasterquadrate liegen im entsprechenden linearen Raster geteilt durch 3.
6. Keine der Funktionen <math>k_{++}, k_{+-}, k_{-+}, k_{--} </math> ist stetig. Die Unstetigkeitsstellen sind <math>\in \bigl((E_2 \times \mathcal{I}) \cup (\mathcal{I} \times E_2)\bigr) .</math>
7. Keine der Funktionen <math>k_{++}, k_{+-}, k_{-+}, k_{--} </math> ist surjektiv.
8. Sind die Koordinaten <math>(x,y) </math> beide rational mit den beziehentlichen 2-adischen Periodenlängen <math>l_x,l_y </math>, dann ist
         <math>t := k_{\pm\pm}(x,y) \in \Q </math>
   ebenfalls rational mit einer 4-adischen Periodenlänge <math>\le v l_x l_y ,</math> wo <math>v = 4 </math> die Mächtigkeit der Menge <math>\mathbf{V} </math> der Ausrichtungen ist.<ref name="Wunderlich" />

Beweise der Eigenschaften

Zu Eigsch. 1:   <math>k_{\pm\pm} </math> ist eine Funktion. Der Limes der #Rekursionsformel für den Hilbert-Index definiert die Funktion <math>k_{++} </math>.<ref group="Anmerkung">Denn ein abbrechender 2-adischer Bruch <math>x = 0_2.\! \xi_1 \xi_2 \dotso \xi_n </math> wird »natürlicherweise« mit einem {{#if:trim|02. …0-Ende}} entwickelt. Für die Funktionen <math>k_{+-}, k_{-+}, k_{--} </math> gibt es ähnliche Rekursionsformeln.</ref> Zu Eigsch. 2:   <math>(x,y) \in \mathcal{Q} </math> hat maximal 4 Urbilder. S. Beweis von: <math>h </math> ist nicht injektiv. Zu Eigsch. 3:   <math>k_{\pm\pm} </math> ist injektiv. Eine Rechtsinverse ist injektiv. Zu Eigsch. 4:   Die Punkte <math>(x,y)\in F_2 = (\mathcal{I} \setminus E_2)^2 </math> haben nur ein Urbild {{#if:trim|<math>h^{-1}\bigl(\{(x,y)\}\bigr) </math>.}} Zu Eigsch. 5:   <math>k{\pm\pm} \; \colon \; \mathcal{I}_{2^n} \times \mathcal{I}_{2^n} \to \mathcal{I}_{3 \cdot 4^n} </math>. (Die Argumentation ist analog zur Eigsch. 5 der Hilbert-Kurve.) Zu Eigsch. 6:   <math>k_{\pm\pm} </math> ist nicht stetig. An den Mehrfachpunkten unterscheiden sich mindestens 2 der Funktionen <math>k_{++}, k_{+-}, k_{-+}, k_{--} </math>, d. h. linksseitiger oder/und rechtsseitiger Grenzwert. Also ist keine der Funktionen dort stetig. Zu Eigsch. 7:   Kein <math>k_{\pm\pm} </math> ist surjektiv. Wie gezeigt, gibt es mehrere Rechtsinversen <math>k_{\pm\pm} </math>. Gemäß Abschnitt Rechtsinverse ist davon keine surjektiv. Zu Eigsch. 8:   <math> k_{\pm\pm}\bigl((\mathcal{I} \cap \Q)^2\bigr) \subset \Q </math> . (Die Argumentation ist analog zur Eigsch. 9 der Hilbert-Kurve.) Der folgende Pseudocode xy2tQpp nimmt die ganzzahligen Zähler und Nenner xn,xd, yn,yd eines rationalen Punktes {{#if:trim|}} und produziert Zähler und Nenner tn,td des Parameters {{#if:trim|}} Die Wiederkehr einer Konstellation (a,xn,yn) und damit die 4-adische Periodenlänge von <math>t </math> wird mittels des assoziativen Datenfeldes occurs festgestellt. Auf diese Weise kommt der Pseudocode auch mit einem möglichen {{#if:trim|04. …3-Ende}} des Ergebnisses zurecht. Die Datenfelder T und A beziehen sich auf die obigen Hypermatrizen <math>T</math> und <math>A'</math>. Der Doppelstern ** ist das Zeichen für Potenzierung. function xy2tQpp(xn,xd, // 0 ≤ xn ≤ xd (> 0) yn,yd) // 0 ≤ yn ≤ yd (> 0) begin pos = 0; tp = 0; a = 0; // initiale Ausrichtung key = a+4*(xn+xd*yn); // die Konstellation (a,xn,yn) als Schlüssel while not defined(occurs[key]) do occurs[key] = pos; // die Nummer der Stelle mit (a,xn,yn) xi = floor(xn*2/xd); // Binärziffer xi: 0 ≤ xi ≤ 2 if xi > 1 then xi = 1; end if xn = xn*2 − xi*xd; // 0 ≤ xn ≤ xd yi = floor(yn*2/yd); // Binärziffer yi: 0 ≤ yi ≤ 2 if yi > 1 then yi = 1; end if yn = yn*2 − yi*yd; // 0 ≤ yn ≤ yd tp = tp*4 + T[a,xi,yi]; // obige Hypermatrix T a = A[a,xi,yi]; // obige Hypermatrix A' key = a+4*(xn+xd*yn);<ref group="Anmerkung">Wegen 0≤a<4 und 0≤xn<xd folgt aus a+4*(xn+xd*yn) = a′+4*(xn′+xd*yn′) die Gleichheit der Konstellation (a,xn,yn) = (a′,xn′,yn′).</ref> pos += 1; end while pl = pos−occurs[key]; // die 4-adische Periodenlänge von t pot = 4**pl; per = pot−1; td = per * 4**(pos−pl); // Nenner von t tn = tp div pot; // Vorperiode von t tp = tp−tn*pot; // Periode von t tn = tn*per+tp; // Zähler von t return (tn,td); end function {{#invoke:Vorlage:Anker|f |errCat=Wikipedia:Vorlagenfehler/Vorlage:Anker |errHide=1}}Ersetzt man in diesem Pseudocode die 2 Zeilen xi = floor(xn*2/xd); // Binärziffer xi: 0 ≤ xi ≤ 2 if xi > 1 then xi = 1; end if (die bei xn == xd/2 zu xi = 1 führen) durch xi = ceil(xn*2/xd−1); // Binärziffer xi: −1 ≤ xi ≤ 1 if xi < 0 then xi = 0; end if (die bei xn == xd/2 zu xi = 0 führen – bei sonst gleichem Ergebnis), dann erhält man die Funktion <math>k_{-+}</math> bspw. als xy2tQmp(xn,xd, yn,yd). Auf ähnliche Weise kommt man zu den Funktionen <math>k_{+-}</math> und {{#if:trim|<math>k_{--}</math>.}}

Einige Zahlenwerte

Punkt <math>(x,y) </math>	<math>x </math>	<math>\tfrac13 </math>	<math>0 </math>	<math>\tfrac13 </math>	<math>1 </math>	<math>\tfrac15 </math>	<math>0 </math>	<math>\tfrac15 </math>	<math>1 </math>
	<math>y </math>	<math>0 </math>	<math>\tfrac13 </math>	<math>1 </math>	<math>\tfrac13 </math>	<math>0 </math>	<math>\tfrac15 </math>	<math>1 </math>	<math>\tfrac15 </math>
Parameter <math>t </math>	<math>k_{\pm\pm}(x,y) </math>	<math>\tfrac{1}{13} </math>	<math>\tfrac{3}{13} </math>	<math>\tfrac{2}{5} </math>	<math>\tfrac{10}{13} </math>	<math>\tfrac{1}{17} </math>	<math>\tfrac{1}{51} </math>	<math>\tfrac{6}{17} </math>	<math>\tfrac{50}{51} </math>

Mehrfachpunkte

<math>\bigl(\tfrac12,0\bigr)\in E_2\!\times\!\bigl(\mathcal{I}\!\setminus\!E_2\bigr)</math>		<math>x=\tfrac{1}{2}</math>
		<math>\searrow\, =0_2.1\overline{0}</math>		<math>\nearrow\, =0_2.0\overline{1}</math>
<math>y=0</math>	<math>\searrow\!\!\!\!\!\!\nearrow\, =0_2.0</math>	<math>k_{+\pm}\bigl(\tfrac{1}{2},0\bigr)=0_4.3\overline{2}=\tfrac{11}{12}</math>	<math>a=\scriptstyle\scriptstyle\mathbf{A}\overline{\mathbf{,B}}</math>	<math>k_{-\pm}\bigl(\tfrac{1}{2},0\bigr)=0_4.0\overline{1}= \tfrac{1}{12}</math>	<math>a=\scriptstyle\mathbf{A}\overline{\mathbf{,D}}</math>

<math>\bigl(\tfrac12,\tfrac13\bigr)\in E_2\!\times\!\bigl(\mathcal{I}\!\setminus\!E_2\bigr)</math>		<math>x=\tfrac{1}{2}</math>
		<math>\searrow\, =0_2.1\overline{0}</math>		<math>\nearrow\, =0_2.0\overline{1}</math>
<math>y=\tfrac{1}{3}</math>	<math>\searrow\!\!\!\!\!\!\nearrow\, =0_2.\overline{01}</math>	<math>k_{+\pm}\bigl(\tfrac{1}{2},\tfrac{1}{3}\bigr)=0_4.3\overline{12}=\tfrac{17}{20}</math>	<math>a=\scriptstyle\scriptstyle\mathbf{A}\overline{\mathbf{,B}}</math>	<math>k_{-\pm}\bigl(\tfrac{1}{2},\tfrac{1}{3}\bigr)=0_4.0\overline{21}= \tfrac{3}{20}</math>	<math>a=\scriptstyle\mathbf{A}\overline{\mathbf{,D}}</math>

<math>\bigl(\tfrac13,\tfrac12\bigr)\in \bigl(\mathcal{I}\!\setminus\!E_2\bigr)\!\times\! E_2</math>		<math>x=\tfrac{1}{3}</math>
		<math>\searrow\!\!\!\!\!\!\nearrow\, =0_2.\overline{01}</math>
<math>y=\tfrac{1}{2}</math>	<math>\searrow\, =0_2.1\overline{0}</math>	<math>k_{\pm+}\bigl(\tfrac{1}{3},\tfrac{1}{2}\bigr)=0_4.1\overline{323010}=\tfrac{25}{52}</math>	<math>a=\scriptstyle\scriptstyle\mathbf{A}\overline{\mathbf{,A,B,B,A,D,D}}</math>
	<math>\nearrow\, =0_2.0\overline{1}</math>	<math>k_{\pm-}\bigl(\tfrac{1}{3},\tfrac{1}{2}\bigr)=0_4.0\overline{230103}= \; \tfrac{9}{52}</math>	<math>a=\scriptstyle\mathbf{A}\overline{\mathbf{,D,D,C,B,B,C}}</math>

<math>\bigl(\tfrac12,\tfrac12\bigr)\in E_2\!\times\! E_2</math>		<math>x=\tfrac{1}{2}</math>
		<math>\searrow\, =0_2.1\overline{0}</math>		<math>\nearrow\, =0_2.0\overline{1}</math>
<math>y=\tfrac{1}{2}</math>	<math>\searrow\, =0_2.1\overline{0}</math>	<math>k_{++}\bigl(\tfrac{1}{2},\tfrac{1}{2}\bigr)=0_4.2\overline{0}=</math> <math>\tfrac{1}{2}</math>	<math>a=\scriptstyle\scriptstyle\mathbf{A,A}\overline{\mathbf{,D}}</math>	<math>k_{-+}\bigl(\tfrac{1}{2},\tfrac{1}{2}\bigr)=0_4.1\overline{3}=</math> <math>\tfrac{1}{2}</math>	<math>a=\scriptstyle\mathbf{A,A}\overline{\mathbf{,B}}</math>
	<math>\nearrow\, =0_2.0\overline{1}</math>	<math>k_{+-}\bigl(\tfrac{1}{2},\tfrac{1}{2}\bigr)=0_4.3\overline{1}=\tfrac{5}{6}</math>	<math>a=\scriptstyle\mathbf{A,B}\overline{\mathbf{,B}}</math>	<math>k_{--}\bigl(\tfrac{1}{2},\tfrac{1}{2}\bigr)=0_4.0\overline{2}= \tfrac{1}{6}</math>	<math>a=\scriptstyle\mathbf{A,D}\overline{\mathbf{,D}}</math>

<math>\bigl(\tfrac14,\tfrac14\bigr)\in E_2\!\times\! E_2</math>		<math>x=\tfrac{1}{4}</math>
		<math>\searrow\, =0_2.01\overline{0}</math>		<math>\nearrow\, =0_2.00\overline{1}</math>
<math>y=\tfrac{1}{4}</math>	<math>\searrow\, =0_2.01\overline{0}</math>	<math>k_{++}\bigl(\tfrac{1}{4},\tfrac{1}{4}\bigr)=0_4.02\overline{0}=</math> <math>\tfrac{1}{8}</math>	<math>a=\scriptstyle\scriptstyle\mathbf{A,D}\overline{\mathbf{,D,A}}</math>	<math>k_{-+}\bigl(\tfrac{1}{4},\tfrac{1}{4}\bigr)=0_4.03\overline{1}= \tfrac{5}{24}</math>	<math>a=\scriptstyle\mathbf{A,D,C}\overline{\mathbf{,C}}</math>
	<math>\nearrow\, =0_2.00\overline{1}</math>	<math>k_{+-}\bigl(\tfrac{1}{4},\tfrac{1}{4}\bigr)=0_4.01\overline{3}=</math> <math>\tfrac{1}{8}</math>	<math>a=\scriptstyle\mathbf{A,D}\overline{\mathbf{,D,C}}</math>	<math>k_{--}\bigl(\tfrac{1}{4},\tfrac{1}{4}\bigr)=0_4.00\overline{2}= \; \tfrac{1}{24}</math>	<math>a=\scriptstyle\mathbf{A,D,A}\overline{\mathbf{,A}}</math>

<math>\bigl(\tfrac12,\tfrac14\bigr)\in E_2\!\times\! E_2</math>		<math>x=\tfrac{1}{2}</math>
		<math>\searrow\, =0_2.1\overline{0}</math>		<math>\nearrow\, =0_2.0\overline{1}</math>
<math>y=\tfrac{1}{4}</math>	<math>\searrow\, =0_2.01\overline{0}</math>	<math>k_{++}\bigl(\tfrac{1}{2},\tfrac{1}{4}\bigr)=0_4.31\overline{2}=\tfrac{41}{48}</math>	<math>a=\scriptstyle\scriptstyle\mathbf{A}\overline{\mathbf{,B}}</math>	<math>k_{-+}\bigl(\tfrac{1}{2},\tfrac{1}{4}\bigr)=0_4.02\overline{1}= \tfrac{7}{48}</math>	<math>a=\scriptstyle\mathbf{A}\overline{\mathbf{,D}}</math>
	<math>\nearrow\, =0_2.00\overline{1}</math>	<math>k_{+-}\bigl(\tfrac{1}{2},\tfrac{1}{4}\bigr)=0_4.32\overline{1}=\tfrac{43}{48}</math>	<math>a=\scriptstyle\mathbf{A}\overline{\mathbf{,B}}</math>	<math>k_{--}\bigl(\tfrac{1}{2},\tfrac{1}{4}\bigr)=0_4.01\overline{2}= \tfrac{5}{48}</math>	<math>a=\scriptstyle\mathbf{A}\overline{\mathbf{,D}}</math>

Darstellung als Lindenmayer-System

Die Hilbert-Kurve kann als Termersetzungssystem (Lindenmayer-System) formuliert werden.<ref>{{#ifexist:Vorlage:bibISBN/{{#invoke:URIutil|plainISBN|978-3-642-31045-4}} | {{bibISBN/{{#invoke:URIutil|plainISBN|978-3-642-31045-4}}

  |record = Vorlage:bibISBN/{{#invoke:URIutil|plainISBN|978-3-642-31045-4}}
  |format = Literatur
  |Autor = 
  |Titel = 
  |TitelErg = 
  |Band = 
  |Auflage = 
  |Kommentar= 
  |Kapitel = 
  |Seite = 
  |Seiten = 
  |Spalten = 
  |ArtikelNr = 
  |Fundstelle = 
  |DOI = 
  |Online = 
  |URL = 
  |Linktext = 
  |Format = 
  |KBytes = 
  |Abruf = 
  |Typ = 

}}{{#ifeq: 0 | 0

   | {{#invoke:TemplatePar|check
       |all= 1=
       |opt= 2= format= Autor= Titel= TitelErg= Hrsg= Sammelwerk= WerkErg= Band= Nummer= Auflage= Datum= Sprache= NummerReihe= BandReihe= HrsgReihe= Kommentar= Kapitel= Seite= Seiten= Spalten= ArtikelNr= Fundstelle= DOI= Online= URL= Linktext= Format= KBytes= Abruf= Typ=

|template=Vorlage:bibISBN |cat=Wikipedia:Vorlagenfehler/Vorlage:BibISBN}}

     }}

| {{#if:||{{#ifeq: 0 | 0 | }}}}}} S. 32.</ref>

Variablen: A, B, C, D

Terminale: ↑, →, ↓, ←

      (blaugrüne Pfeile in der Abb. 7)

Startsymbol: A

Ersetzungsregeln:

A ⇒ D ↑ A → A ↓ B

B ⇒ C ← B ↓ B → A

C ⇒ B ↓ C ← C ↑ D

D ⇒ A → D ↑ D ← C

Die Ersetzungsregeln legen fest, welche Ausrichtung (welche Variable) in der nächsten Iteration durch welche Ausrichtung verbunden durch welche Pfeile (Terminale) ersetzt werden sollen.

Weiter gefasste Konstruktionsprinzipien

Datei:Moore curve 3!.svg

Abb. 9: Moore-Polygon der ersten bis dritten Iteration.
Die Bits im Index (Schrift gedreht) auf gerader Stelle in blau, auf ungerader in rot.
Der Moore-Index eines Quadrates mit Mittelpunkt <math>(x,y) </math> findet sich am Schnittpunkt von <math>x </math>-Spalte mit <math>y </math>-Zeile. (Alle Zahlen im Binärsystem)

Die Hilbertkurve ist (bis auf Spiegelungen und Rotationen) die einzige zweidimensionale FASS-Kurve des Quadrats mit Start und Ende an zwei Ecken („vertex-gated“).<ref>{{#ifexist:Vorlage:bibISBN/{{#invoke:URIutil|plainISBN|978-3-642-31045-4}} | {{bibISBN/{{#invoke:URIutil|plainISBN|978-3-642-31045-4}}

  |record = Vorlage:bibISBN/{{#invoke:URIutil|plainISBN|978-3-642-31045-4}}
  |format = Literatur
  |Autor = 
  |Titel = 
  |TitelErg = 
  |Band = 
  |Auflage = 
  |Kommentar= 
  |Kapitel = 
  |Seite = 
  |Seiten = 
  |Spalten = 
  |ArtikelNr = 
  |Fundstelle = 
  |DOI = 
  |Online = 
  |URL = 
  |Linktext = 
  |Format = 
  |KBytes = 
  |Abruf = 
  |Typ = 

}}{{#ifeq: 0 | 0

   | {{#invoke:TemplatePar|check
       |all= 1=
       |opt= 2= format= Autor= Titel= TitelErg= Hrsg= Sammelwerk= WerkErg= Band= Nummer= Auflage= Datum= Sprache= NummerReihe= BandReihe= HrsgReihe= Kommentar= Kapitel= Seite= Seiten= Spalten= ArtikelNr= Fundstelle= DOI= Online= URL= Linktext= Format= KBytes= Abruf= Typ=

|template=Vorlage:bibISBN |cat=Wikipedia:Vorlagenfehler/Vorlage:BibISBN}}

     }}

| {{#if:||{{#ifeq: 0 | 0 | }}}}}} S. 26.</ref>

Die Hilbert-Kurve nach Moore, kurz: die Moore-Kurve (engl. Moore curve) ist eine geschlossene Form der Hilbert-Kurve. Sie hat dasselbe Grundmuster wie diese. Die Übergänge zwischen den Quadraten wenden sich jedoch sowohl nach außen als auch nach innen. Sie ist genauso raumfüllend und hat sehr ähnliche Nachbarschaftseigenschaften wie die Hilbert-Kurve. Bei den Transformationen kommen alle acht Isometrien <math>\in D_4 </math> vor.

Weitere Kurven auf ähnlicher Konstruktionsbasis wurden gefunden.<ref>X. Liu. Four alternative patterns of the Hilbert curve. Applied Mathematics and Communication, 147:741–752, 2004.</ref><ref name="Demydenko" />

Die Konstruktionsprinzipien können noch weiter – unter Aufrechterhaltung der stetigen Raumfüllung – gelockert werden. Insbesondere die Aufgabe der Selbstähnlichkeit eröffnet eine Abundanz an Möglichkeiten. Hinweise dazu finden sich im Artikel Raumfüllende Kurve.

{{#invoke:Vorlage:Anker|f |errCat=Wikipedia:Vorlagenfehler/Vorlage:Anker |errHide=1}}Ausblick auf den 3-dimensionalen Fall

Datei:Hilbert curve 3D Grundmuster.svg

Abb. 10: 3D-Hilbert-Kurve beta mit dem Grundmuster <math>\mathsf{Ca00}</math> (türkis)

Die nebenstehende Abbildung 10 zeigt Grundmuster und erste Iteration der Hilbert-Kurve beta<ref name="Haverkort1">H. Haverkort, 2016</ref> – eines von vielen Beispielen einer {{#if:trim|}} Hilbert-Kurve.

Wie im 2-dimensionalen Fall stehen die verschiedenen Ausrichtungen über Isometrien des <math>\R^d </math> in Beziehung zueinander. Wie dort bilden diese Isometrien eine Gruppe, und zwar hier: eine Untergruppe der {{#if:trim|48-elementigen}} Würfelgruppe. Das Beispiel der Abb. 10 zeigt eine Variante mit einer 24-elementigen Isometriengruppe, die zur symmetrischen Gruppe <math>S_4 </math> isomorph ist.

Es gibt im 3-dimensionalen Fall signifikant mehr Möglichkeiten für die Konstruktion einer Hilbert-Kurve, die sich durch die „Traversierung“ (engl. traversal, grün in der Abb.) charakterisieren lassen. H. Haverkort<ref name="Haverkort1" /> klassifiziert alle 3-dimensionalen Hilbert-Kurven und zählt 920 „face-continuous“ (deutsch etwa: Zellen-stetig), bei denen zwei aufeinanderfolgende Nachbarwürfel ein Quadrat (eine {{#if:trim|}} Zelle) gemeinsam haben, und insgesamt 10 694 807 verschiedene 3-dimensionale Hilbert-Kurven (p. 20), wobei er auch Grundmuster zulässt, bei denen sich die Nachbarwürfel nur an einer Kante oder Ecke berühren (Figure 13). Er weist auch darauf hin, dass es (wie im 2-dimensionalen Fall) unendlich viele Hilbert-Kurven gibt, wenn man auf Selbstähnlichkeit verzichtet.

In der Abb. 10 ist das Grundmuster des Ausgangswürfels durch den Polygonzug in der Farbe türkis dargestellt. Dieses Grundmuster bringt in der ersten Iterationsstufe die 8 Teilwürfel innerhalb des Ausgangswürfels in eine zusammenhängende Reihenfolge.

In der zweiten Iterationsstufe wiederholt sich zwar dieses Grundmuster pro Teilwürfel, für die Traversierung der Teil-Teilwürfel der zweiten Stufe bleiben dennoch sehr viele Freiheitsgrade, die die Hilbert-Kurve als Ganze charakterisieren. Im Beispiel werden sie durch den grünen Polygonzug festgelegt. Die für die Traversierung erforderlichen Drehungen, Kippungen und/oder Spiegelungen an den 7 inneren Übergangsstellen des Grundmusters kann man anhand der Abb. verifizieren. (Nachbarschaften werden durch die bei der rekursiven Einbettung anfallenden Isometrien nicht geändert.) Bei den Übergängen zwischen den Teilwürfeln (den „gates“<ref name="Haverkort1" /> S. 13) gibt es weitere Wahlmöglichkeiten. H. Haverkort klassifiziert die gezeigte Hilbert-Kurve beta als „facet-gated“ (deutsch etwa: Zellen-verbunden), weil die (Übergänge an den) Enden der Teilwürfel 0 und 7 im Innern einer Quadratseite liegen. Es gibt aber auch „edge-gated“ (deutsch etwa: Kanten-verbundene) und „vertex-gated“ (deutsch etwa: Ecken-verbundene) Hilbert-Kurven.<ref group="Anmerkung">Die 2-dimensionalen selbstähnlichen Hilbert-Kurven sind alle „vertex-gated“.</ref>

In der Abb. 10 ist in den Teilwürfeln die Transformation eingetragen, die einen Würfel, der gleich wie der Ausgangswürfel ausgerichtet ist, abhängig von der Oktalziffer <math>\tau \in \{0,1,\dotso,7\} </math> in den Teilwürfel der Nummer <math>\tau </math> einbettet. Diese Transformation hat vier Komponenten, die Isometrie (gezeigt als Funktion der Koordinaten <math>\xi,\eta,\zeta \in \{-1,1\} </math>), einen additiven Vektor, der die Parallelverschiebung, also das Zentrum des Teilwürfels der Ziffer <math>\tau </math> angibt, die Skalierung um den Faktor <math>\tfrac12 </math> und eine Angabe, in welcher Richtung <math>\in \{-1,1\} </math> das Grundmuster bei dieser Ziffer einzusetzen ist.

Nach H. Haverkort hat die Hilbert-Kurve beta als (die einzige) Zellen-verbundene (engl. facet-gated curve) hervorragende Nachbarschafts-erhaltende Eigenschaften. Bei 3 von Haverkorts 6 Kriterien („metrics“) steht sie auf Platz eins, bei den anderen 3 auf Platz zwei und ist {{#if:trim|≤4 %}} vom Optimum entfernt (section 7.3 Locality-preserving properties).

Die Faltung des Genoms ähnelt einer dreidimensionalen Hilbert-Kurve.<ref>{{#if:|{{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}| |}}}}{{#if:Brandon Keim|Brandon Keim: }}{{#if:|{{#if:The Human Genome in 3 Dimensions|[{{#invoke:Vorlage:Internetquelle|archivURL|1={{#invoke:URLutil|getNormalized|1={{{archiv-url}}}}}}} {{#invoke:Vorlage:Internetquelle|TitelFormat|titel=The Human Genome in 3 Dimensions}}]{{#if:| ({{{format}}})}}{{#if:| {{{titelerg}}}{{#invoke:Vorlage:Internetquelle|Endpunkt|titel={{{titelerg}}}}}}}}}|{{#if:http://www.wired.com/wiredscience/2009/10/fractal-genome/%7C{{#if:{{#invoke:TemplUtl%7Cfaculty%7C}}%7C{{#invoke:Vorlage:Internetquelle%7CTitelFormat%7Ctitel={{#invoke:WLink%7CgetEscapedTitle%7C1=The Human Genome in 3 Dimensions}}}}|[{{#invoke:URLutil|getNormalized|1=http://www.wired.com/wiredscience/2009/10/fractal-genome/}} {{#invoke:Vorlage:Internetquelle|TitelFormat|titel={{#invoke:WLink|getEscapedTitle|1=The Human Genome in 3 Dimensions}}}}]}}{{#if:| ({{{format}}}{{#if:Wired2009-08-10{{#if: 2013-08-28 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}}}}

          | )
          | {{#if:{{#ifeq:en|de||{{#if:en|1}}}}| ; 
              | )}}}}}}{{#if:| {{{titelerg}}}{{#invoke:Vorlage:Internetquelle|Endpunkt|titel={{{titelerg}}}}}}}}}}}{{#if:http://www.wired.com/wiredscience/2009/10/fractal-genome/%7C{{#if:{{#invoke:URLutil%7CisResourceURL%7C1=http://www.wired.com/wiredscience/2009/10/fractal-genome/}}%7C%7C}}}}{{#if:The Human Genome in 3 Dimensions|{{#if:{{#invoke:WLink|isValidLinktext|1=The Human Genome in 3 Dimensions|lines=0}}||}}}}{{#if: | In: {{#invoke:Vorlage:Internetquelle|TitelFormat|titel={{{werk}}}}}}}{{#if: Wired| Wired{{#if: 2009-08-10|,|{{#if: 2013-08-28 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: 2009-08-10| {{#if:{{#invoke:DateTime|format|2009-08-10|noerror=1}}
            |{{#invoke:DateTime|format|2009-08-10|T._Monat JJJJ}}
            |{{#invoke:TemplUtl|failure|1=Fehler bei Vorlage:Internetquelle, datum=2009-08-10|class=Zitationswartung}} }}{{#if: |,|{{#if: 2013-08-28 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: | S. {{{seiten}}}{{#if: |,|{{#if: 2013-08-28 | {{#if:{{#invoke:TemplUtl|faculty|}}|;|,}}}}}}}}{{#if: {{#invoke:TemplUtl|faculty|}}| {{#if:2009-08-10Wired|{{#if:|archiviert|ehemals}}|{{#if:|Archiviert|Ehemals}}}} {{#if:|vom|im}} Vorlage:Referrer{{#if:{{#invoke:TemplUtl|faculty|}}| (nicht mehr online verfügbar)}}{{#if: | am {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}|{{{archiv-datum}}}{{#if:203515||}}}}}}{{#if: 2013-08-28|;}}}}{{#if: 2013-08-28| {{#if:2009-08-10Wired{{#invoke:TemplUtl|faculty|}}|abgerufen|Abgerufen}} {{#switch: {{#invoke:Str|len| {{#invoke:DateTime|format| 2013-08-28 |ISO|noerror=1}} }}
       |4=im Jahr
       |7=im
       |10=am
       |#default={{#invoke:TemplUtl|failure|1=Fehler bei Vorlage:Internetquelle, abruf=2013-08-28|class=Zitationswartung}} }} {{#invoke:DateTime|format|2013-08-28|T._Monat JJJJ}}
    | {{#invoke:TemplUtl|failure|1=Vorlage:Internetquelle | abruf=2026-MM-TT ist Pflichtparameter}} }}{{#if:{{#ifeq:en|de||{{#if:en|1}}}}|{{#if:Wired2009-08-10{{#if: 2013-08-28 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}}}}
       |  (
       | {{#if: | |  (}}
       }}{{#ifeq:{{#if:en|en|de}}|de||
          {{#invoke:Multilingual|format|en|slang=!|split=[%s,]+|shift=m|separator=, }}}}{{#if: |{{#ifeq:{{#if:en|en|de}}|de||, }}{{{kommentar}}}}})}}{{#if: 2009-08-10{{#if: 2013-08-28 | {{#if:{{#invoke:TemplUtl|faculty|}}||1}} }}en|{{#if: |: {{
 #if: 
 | {{
     #ifeq: {{#if:{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|de}} | de
     | Vorlage:Str trim
     | {{#invoke:Vorlage:lang|flat}}
     }}
 | {{#ifeq: {{#if:{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|{{#if: {{#invoke:templutl|faculty|}}|de-ch|de}}|de}} | de
     | „Vorlage:Str trim“
     | {{#invoke:Text|quote
         |1={{#if: 
              | {{#invoke:Vorlage:lang|flat}}
              | {{#invoke:Vorlage:lang|flat}} }}
         |2={{#if: {{#invoke:TemplUtl|faculty|}}|de-CH|de}}
         |3=1}} }}

}}{{#if:

   |  ({{#if:  | :  }}{{#if:  | , deutsch: „“ }})
   | {{#if: 
       |  ({{#if:  | , deutsch: „“ }})
       | {{#if:  |  (deutsch: „“) }}
 }}

}}{{#if: {{{zitat}}}

   | {{#if: 
       | {{#if: {{{zitat}}}
           |  }} }}
   |  }}{{#if:  | {{#if: {{#invoke:Text|unstrip|{{{ref}}}}}
             | 
             | {{{ref}}} }}

}}|.{{#if:{{#invoke:TemplUtl|faculty|}}|{{#if:||{{#ifeq: | JaKeinHinweis |{{#switch:

   |0|=Vorlage:Toter Link/Core{{#if: http://www.wired.com/wiredscience/2009/10/fractal-genome/
       | {{#if:  | [1] }} (Seite {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. Suche im Internet Archive ){{#if: 
           | {{#if: deadurlausgeblendet | | Vorlage:Toter Link/archivebot }}
         }}
       |   (Seite {{#switch:|no|0|=|#default=dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}.)
     }}{{#switch: 
         |no|0|=
         |#default={{#if:  ||  }}
    }}{{#invoke:TemplatePar|check
         |opt      = inline= url= text= datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
    }}{{#if: http://www.wired.com/wiredscience/2009/10/fractal-genome/
      | {{#if:{{#invoke:URLutil|isWebURL|http://www.wired.com/wiredscience/2009/10/fractal-genome/}}
          || {{#if:  ||  }} 
        }}
      | {{#if: 
           | {{#if:  ||  }}
           | {{#if:  ||  }}
        }}
    }}{{#if: 
       | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
         }}
    }}{{#switch: deadurl
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=http://www.wired.com/wiredscience/2009/10/fractal-genome/ Die nachstehende Seite ist {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar]{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. (Suche im Internet Archive. )  {{#if: 
            | {{#if: deadurlausgeblendet | | Vorlage:Toter Link/archivebot }}
         }}Vorlage:Toter Link/Core{{#switch: 
          |no|0|=
          |#default= {{#if:  ||  }}
        }}{{#invoke:TemplatePar|check
         |all      = inline= url=
         |opt      = datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
       }}{{#if: http://www.wired.com/wiredscience/2009/10/fractal-genome/
       | {{#if:{{#invoke:URLutil|isWebURL|http://www.wired.com/wiredscience/2009/10/fractal-genome/}}
          || {{#if:  ||  }} 
        }}
    }}{{#if: 
         | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
           }}
    }}{{#switch: deadurl
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}[http://www.wired.com/wiredscience/2009/10/fractal-genome/ }}|{{#switch: 
   |0|=Vorlage:Toter Link/Core{{#if: http://www.wired.com/wiredscience/2009/10/fractal-genome/
       | {{#if:  | [2] }} (Seite {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. Suche im Internet Archive ){{#if: 
           | {{#if:  | | Vorlage:Toter Link/archivebot }}
         }}
       |   (Seite {{#switch:|no|0|=|#default=dauerhaft }}nicht mehr abrufbar{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}.)
     }}{{#switch: 
         |no|0|=
         |#default={{#if:  ||  }}
    }}{{#invoke:TemplatePar|check
         |opt      = inline= url= text= datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
    }}{{#if: http://www.wired.com/wiredscience/2009/10/fractal-genome/
      | {{#if:{{#invoke:URLutil|isWebURL|http://www.wired.com/wiredscience/2009/10/fractal-genome/}}
          || {{#if:  ||  }} 
        }}
      | {{#if: 
           | {{#if:  ||  }}
           | {{#if:  ||  }}
        }}
    }}{{#if: 
       | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
         }}
    }}{{#switch: 
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}|#default= https://wiki-de.moshellshocker.dns64.de/index.php?title=Wikipedia:Defekte_Weblinks&dwl=http://www.wired.com/wiredscience/2009/10/fractal-genome/ Die nachstehende Seite ist {{#switch:|no|0|=|dauerhaft }}nicht mehr abrufbar]{{#if:  | , festgestellt im {{#invoke:DateTime|format||F Y}} }}. (Suche im Internet Archive. )  {{#if: 
            | {{#if:  | | Vorlage:Toter Link/archivebot }}
         }}Vorlage:Toter Link/Core{{#switch: 
          |no|0|=
          |#default= {{#if:  ||  }}
        }}{{#invoke:TemplatePar|check
         |all      = inline= url=
         |opt      = datum= date= archivebot= bot= botlauf= fix-attempted= checked=
         |cat      = Wikipedia:Vorlagenfehler/Vorlage:Toter Link
         |errNS    = 0
         |template = Vorlage:Toter Link
         |format   = 
         |preview  = 1
       }}{{#if: http://www.wired.com/wiredscience/2009/10/fractal-genome/
       | {{#if:{{#invoke:URLutil|isWebURL|http://www.wired.com/wiredscience/2009/10/fractal-genome/}}
          || {{#if:  ||  }} 
        }}
    }}{{#if: 
         | {{#if:{{#invoke:DateTime|format||F Y|noerror=1}}
             || {{#if:  ||  }} 
           }}
    }}{{#switch: 
         |checked|deadurl|= 
         |#default=  {{#if:  ||  }}
    }}[http://www.wired.com/wiredscience/2009/10/fractal-genome/ }} }}}}}}}}}}{{#if:|
        {{#invoke:Vorlage:Internetquelle|archivBot|stamp={{{archiv-bot}}}|text={{#if:|Vorlage:Webarchiv/archiv-bot}}

}}}} {{#invoke:TemplatePar|check |all= url= titel= |opt= autor= hrsg= format= sprache= titelerg= werk= seiten= datum= abruf= zugriff= abruf-verborgen= archiv-url= archiv-datum= archiv-bot= kommentar= zitat= AT= CH= offline= |cat= {{#ifeq: 0 | 0 | Wikipedia:Vorlagenfehler/Vorlage:Internetquelle}} |template= Vorlage:Internetquelle |format=0 |preview=1 }}</ref>

Erweiterungen

Hilbert-Kurven lassen sich auch effizient für Räume, die nicht Quadrate sind, implementieren. Durch Variation der »Geschwindigkeit« können unterschiedliche Dichten berücksichtigt werden.

Auch in höheren Dimensionen lassen sich Hilbert-Kurven generieren.<ref name="Haverkort1" /><ref>Michael Trott: The Mathematica GuideBook for Programming. Springer 2004. (2.3.9 Hilbert Curves in Higher Dimensions, S. 93–97)</ref><ref>Arthur Butz, Alternative algorithm for Hilbert’s space filling curve, IEEE Trans. On Computers, vol. 20, April 1971, S. 424–442.</ref>

Siehe auch

• Sierpiński-Kurve
• Peano-Kurve
• Z-Kurve
• Quadtree

Literatur

• {{#invoke:Vorlage:Anker|f |errCat=Wikipedia:Vorlagenfehler/Vorlage:Anker |errHide=1}}Michael Bader: Space-Filling Curves - An Introduction with Applications in Scientific Computing, {{#if:trim|Vol. 9}} of Texts in Computational Science and Engineering. Springer-Verlag, 2013.
• {{#invoke:Vorlage:Anker|f |errCat=Wikipedia:Vorlagenfehler/Vorlage:Anker |errHide=1}}Nicholas J. Rose: Hilbert-Type Space-Filling Curves. Abgerufen am 21. Dezember 2017.
• {{#invoke:Vorlage:Anker|f |errCat=Wikipedia:Vorlagenfehler/Vorlage:Anker |errHide=1}}Herman Haverkort: How many three-dimensional Hilbert curves are there?, 2016. Abgerufen am 28. Juli 2018.
• {{#invoke:Vorlage:Anker|f |errCat=Wikipedia:Vorlagenfehler/Vorlage:Anker |errHide=1}}Herman Haverkort: Sixteen space-filling curves and traversals for d-dimensional cubes and simplices, 2017. Abgerufen am 1. Januar 2018.
• {{#invoke:Vorlage:Anker|f |errCat=Wikipedia:Vorlagenfehler/Vorlage:Anker |errHide=1}}Hans Sagan: Space-Filling Curves, (Springer) New York 1994.
• {{#invoke:Vorlage:Anker|f |errCat=Wikipedia:Vorlagenfehler/Vorlage:Anker |errHide=1}}Walter Wunderlich. Über Peano-Kurven. Elemente der Mathematik, 28(1):1–24, 1973.
• {{#invoke:Vorlage:Anker|f |errCat=Wikipedia:Vorlagenfehler/Vorlage:Anker |errHide=1}}Theodore Bially. Space-filling curves: Their generation and their application to bandwidth reduction. IEEE Transactions on Information Theory, IT-15(6):658–664, 1969. (Zitiert nach #Lawder)

Weblinks

Datei:Commons-logo.svg

[{{canonicalurl:Commons:{{#if:Hilbert curve|Hilbert curve|{{#invoke:WLink|getArticleBase}}}}|uselang=de}} Commons: {{#if:Hilbert-Kurve|Hilbert-Kurve|{{#if:Hilbert curve|Hilbert curve|{{#invoke:WLink|getArticleBase}}}}}}]{{#switch:1

|0|-= |X|x= |1|=  – {{#ifeq:0|14|Sammlung von|Album mit}} Bildern{{#if:

    | {{#switch: {{#invoke:TemplUtl|faculty|{{#if:|{{{video}}}|1}}}}/{{#invoke:TemplUtl|faculty|{{#if:|{{{audio}}}|1}}}}
        |1/=  und Videos
        |1/1=, Videos und Audiodateien
        |/1=  und Audiodateien}}
    | , Videos und Audiodateien
  }}

|#default=  – {{{suffix}}} }}{{#invoke:TemplatePar|check

  |opt= 1= 2= suffix= audio= video=
  |template=Vorlage:Commons
  |cat=Wikipedia:Vorlagenfehler/Schwesterprojekt

}}

• {{#invoke:Vorlage:Anker|f |errCat=Wikipedia:Vorlagenfehler/Vorlage:Anker |errHide=1}}David Hilbert: Über die stetige Abbildung einer Linie auf ein Flächenstück. Mathematische Annalen 38 (1891), 459–460 (Göttinger Digitalisierungszentrum).
• {{#invoke:Vorlage:Anker|f |errCat=Wikipedia:Vorlagenfehler/Vorlage:Anker |errHide=1}}{{#if:20050317185150

      | {{#ifeq: 20050317185150 | *
    | Vorlage:Webarchiv/Wartung/Stern{{#if: Michael Bader: Raumfüllende Kurven | {{#invoke:WLink|getEscapedTitle|Michael Bader: Raumfüllende Kurven}} | {{#invoke:Webarchiv|getdomain|http://www5.in.tum.de/lehre/vorlesungen/algowiss/ss04/vorlesung/rfk.pdf}} }} (Archivversionen)
    | {{#iferror: {{#time: j. F Y|20050317185150}}
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/Datum
         | {{#if: Michael Bader: Raumfüllende Kurven | {{#invoke:WLink|getEscapedTitle|Michael Bader: Raumfüllende Kurven}} | {{#invoke:Webarchiv|getdomain|http://www5.in.tum.de/lehre/vorlesungen/algowiss/ss04/vorlesung/rfk.pdf}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer }} vom {{#time: j. F Y|20050317185150}} im Internet Archive{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
      }}
  }}
      | {{#if:
          | {{#iferror: {{#time: j. F Y|{{{webciteID}}}}}
    | {{#switch: {{#invoke:Str|len|{{{webciteID}}}}}
       | 16= {{#if: Michael Bader: Raumfüllende Kurven | {{#invoke:WLink|getEscapedTitle|Michael Bader: Raumfüllende Kurven}} | {{#invoke:Webarchiv|getdomain|http://www5.in.tum.de/lehre/vorlesungen/algowiss/ss04/vorlesung/rfk.pdf}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer }} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{{webciteID}}}|1|10}}/86400}} }} days}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
       | 9 = {{#if: Michael Bader: Raumfüllende Kurven | {{#invoke:WLink|getEscapedTitle|Michael Bader: Raumfüllende Kurven}} | {{#invoke:Webarchiv|getdomain|http://www5.in.tum.de/lehre/vorlesungen/algowiss/ss04/vorlesung/rfk.pdf}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer}} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{#invoke:Expr|base62|{{{webciteID}}}}}|1|10}}/86400}} }} days}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
       | #default= Vorlage:Webarchiv/Wartung/webcitation{{#if:  || }}
      }}
    | c|{{{webciteID}}}}} {{#if: Michael Bader: Raumfüllende Kurven | {{#invoke:WLink|getEscapedTitle|Michael Bader: Raumfüllende Kurven}} | {{#invoke:Webarchiv|getdomain|http://www5.in.tum.de/lehre/vorlesungen/algowiss/ss04/vorlesung/rfk.pdf}} }} (Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer}} vom {{#time: j. F Y|{{{webciteID}}}}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
  }}
          | {{#if: 
              | Vorlage:Webarchiv/Today
              | {{#if:
                      | Vorlage:Webarchiv/Generisch
                      | {{#if: Michael Bader: Raumfüllende Kurven | {{#invoke:WLink|getEscapedTitle|Michael Bader: Raumfüllende Kurven}} | {{#invoke:Webarchiv|getdomain|http://www5.in.tum.de/lehre/vorlesungen/algowiss/ss04/vorlesung/rfk.pdf}} }}  
                 }}}}}}}}{{#if:
    | Vorlage:Webarchiv/archiv-bot
  }}{{#invoke:TemplatePar|check
     |all      = url=
     |opt      = text= wayback= webciteID= archive-is= archive-today= archiv-url= archiv-datum= ()= archiv-bot= format= original=
     |cat      = Wikipedia:Vorlagenfehler/Vorlage:Webarchiv
     |errNS    = 0
     |template = Vorlage:Webarchiv
     |format   = *
     |preview  = 1
  }}{{#ifexpr: {{#if:20050317185150|1|0}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}} <> 1
    | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Genau einer der Parameter 'wayback', 'webciteID', 'archive-today', 'archive-is' oder 'archiv-url' muss angegeben werden.|1}}
  }}{{#if: 
    | {{#switch: {{#invoke:Webarchiv|getdomain|{{{archiv-url}}}}}
        | web.archive.org = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von Internet Archive erkannt, bitte Parameter 'wayback' benutzen.|1}} 
        | webcitation.org = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von WebCite erkannt, bitte Parameter 'webciteID' benutzen.|1}} 
        | archive.today |archive.is |archive.ph |archive.fo |archive.li |archive.md |archive.vn = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von archive.today erkannt, bitte Parameter 'archive-today' benutzen.|1}}
      }}{{#if: 
         | {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}
             | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Wert des Parameter 'archiv-datum' ist ungültig oder hat ein ungültiges Format.|1}}
          |  }} 
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Pflichtparameter 'archiv-datum' wurde nicht angegeben.|1}}
      }}
    | {{#if: 
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Parameter 'archiv-datum' ist nur in Verbindung mit 'archiv-url' angebbar.|1}}
      }}
  }}{{#if:{{#invoke:URLutil|isHostPathResource|http://www5.in.tum.de/lehre/vorlesungen/algowiss/ss04/vorlesung/rfk.pdf}}
    || {{#if:  || }}
  }}{{#if: Michael Bader: Raumfüllende Kurven
    | {{#if: {{#invoke:WLink|isBracketedLink|Michael Bader: Raumfüllende Kurven}}
        | {{#if:  || }}
      }}
    | {{#if:  || }}Vorlage:Webarchiv/Wartung/Linktext_fehlt
  }}{{#switch: 
    |addlarchives|addlpages= {{#if:  || }}{{#if: 1 |Vorlage:Webarchiv/Wartung/Parameter}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: enWP-Wert im Parameter 'format'.|1}}
  }}{{#ifeq: {{#invoke:Str|find|http://www5.in.tum.de/lehre/vorlesungen/algowiss/ss04/vorlesung/rfk.pdf%7Carchiv}} |-1
    || {{#ifeq: {{#invoke:Str|find|{{#invoke:Str|cropleft|http://www5.in.tum.de/lehre/vorlesungen/algowiss/ss04/vorlesung/rfk.pdf%7C4}}%7Chttp}} |-1
         || {{#switch: {{#invoke:Webarchiv|getdomain|http://www5.in.tum.de/lehre/vorlesungen/algowiss/ss04/vorlesung/rfk.pdf }}
              | abendblatt.de | daserste.ndr.de | inarchive.com | webcitation.org = 
              | #default = {{#if:  || }}{{#if: 1 |Vorlage:Webarchiv/Wartung/URL}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Archiv-URL im Parameter 'url' anstatt URL der Originalquelle. Entferne den vor der Original-URL stehenden Mementobestandteil und setze den Archivierungszeitstempel in den Parameter 'wayback', 'webciteID', 'archive.today' oder 'archive-is' ein, sofern nicht bereits befüllt.|1}}
            }} 
       }}
  }} TUM Informatik (PDF-Datei; 637 kB)

• {{#invoke:Vorlage:Anker|f |errCat=Wikipedia:Vorlagenfehler/Vorlage:Anker |errHide=1}}Jonathan Lawder: Techniques for Mapping to and from Space-filling Curves, 1999.
• Java-Applet zur Konstruktion von Hilbert-Kurven
• {{#if:20071224065759

      | {{#ifeq: 20071224065759 | *
    | Vorlage:Webarchiv/Wartung/Stern{{#if: David Hilbert | {{#invoke:WLink|getEscapedTitle|David Hilbert}} | {{#invoke:Webarchiv|getdomain|http://www.cip.informatik.uni-muenchen.de/~zimmermc/sfc/zula/node6.html}} }} (Archivversionen)
    | {{#iferror: {{#time: j. F Y|20071224065759}}
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/Datum
         | {{#if: David Hilbert | {{#invoke:WLink|getEscapedTitle|David Hilbert}} | {{#invoke:Webarchiv|getdomain|http://www.cip.informatik.uni-muenchen.de/~zimmermc/sfc/zula/node6.html}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer }} vom {{#time: j. F Y|20071224065759}} im Internet Archive{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
      }}
  }}
      | {{#if:
          | {{#iferror: {{#time: j. F Y|{{{webciteID}}}}}
    | {{#switch: {{#invoke:Str|len|{{{webciteID}}}}}
       | 16= {{#if: David Hilbert | {{#invoke:WLink|getEscapedTitle|David Hilbert}} | {{#invoke:Webarchiv|getdomain|http://www.cip.informatik.uni-muenchen.de/~zimmermc/sfc/zula/node6.html}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer }} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{{webciteID}}}|1|10}}/86400}} }} days}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
       | 9 = {{#if: David Hilbert | {{#invoke:WLink|getEscapedTitle|David Hilbert}} | {{#invoke:Webarchiv|getdomain|http://www.cip.informatik.uni-muenchen.de/~zimmermc/sfc/zula/node6.html}} }} {{#ifeq:  | [] | [ | ( }}Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer}} vom {{#time: j. F Y| 19700101000000 + {{#expr: floor {{#expr: {{#invoke:Str|sub|{{#invoke:Expr|base62|{{{webciteID}}}}}|1|10}}/86400}} }} days}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
       | #default= Vorlage:Webarchiv/Wartung/webcitation{{#if:  || }}
      }}
    | c|{{{webciteID}}}}} {{#if: David Hilbert | {{#invoke:WLink|getEscapedTitle|David Hilbert}} | {{#invoke:Webarchiv|getdomain|http://www.cip.informatik.uni-muenchen.de/~zimmermc/sfc/zula/node6.html}} }} (Memento{{#if: {{#if:  | {{{archiv-bot}}} |  }} |  des Vorlage:Referrer}} vom {{#time: j. F Y|{{{webciteID}}}}} auf WebCite{{#if:  | ;  }}{{#ifeq:  | [] | ] | ) }}
  }}
          | {{#if: 
              | Vorlage:Webarchiv/Today
              | {{#if:
                      | Vorlage:Webarchiv/Generisch
                      | {{#if: David Hilbert | {{#invoke:WLink|getEscapedTitle|David Hilbert}} | {{#invoke:Webarchiv|getdomain|http://www.cip.informatik.uni-muenchen.de/~zimmermc/sfc/zula/node6.html}} }}  
                 }}}}}}}}{{#if:
    | Vorlage:Webarchiv/archiv-bot
  }}{{#invoke:TemplatePar|check
     |all      = url=
     |opt      = text= wayback= webciteID= archive-is= archive-today= archiv-url= archiv-datum= ()= archiv-bot= format= original=
     |cat      = Wikipedia:Vorlagenfehler/Vorlage:Webarchiv
     |errNS    = 0
     |template = Vorlage:Webarchiv
     |format   = *
     |preview  = 1
  }}{{#ifexpr: {{#if:20071224065759|1|0}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}}{{#if:|+1}} <> 1
    | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Genau einer der Parameter 'wayback', 'webciteID', 'archive-today', 'archive-is' oder 'archiv-url' muss angegeben werden.|1}}
  }}{{#if: 
    | {{#switch: {{#invoke:Webarchiv|getdomain|{{{archiv-url}}}}}
        | web.archive.org = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von Internet Archive erkannt, bitte Parameter 'wayback' benutzen.|1}} 
        | webcitation.org = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von WebCite erkannt, bitte Parameter 'webciteID' benutzen.|1}} 
        | archive.today |archive.is |archive.ph |archive.fo |archive.li |archive.md |archive.vn = 
          {{#if:  || }}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Im Parameter 'archiv-url' wurde URL von archive.today erkannt, bitte Parameter 'archive-today' benutzen.|1}}
      }}{{#if: 
         | {{#iferror: {{#iferror:{{#invoke:Vorlage:FormatDate|Execute}}|}}
             | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Wert des Parameter 'archiv-datum' ist ungültig oder hat ein ungültiges Format.|1}}
          |  }} 
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Pflichtparameter 'archiv-datum' wurde nicht angegeben.|1}}
      }}
    | {{#if: 
         | {{#if:  || }}Vorlage:Webarchiv/Wartung/Parameter{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Der Parameter 'archiv-datum' ist nur in Verbindung mit 'archiv-url' angebbar.|1}}
      }}
  }}{{#if:{{#invoke:URLutil|isHostPathResource|http://www.cip.informatik.uni-muenchen.de/~zimmermc/sfc/zula/node6.html}}
    || {{#if:  || }}
  }}{{#if: David Hilbert
    | {{#if: {{#invoke:WLink|isBracketedLink|David Hilbert}}
        | {{#if:  || }}
      }}
    | {{#if:  || }}Vorlage:Webarchiv/Wartung/Linktext_fehlt
  }}{{#switch: 
    |addlarchives|addlpages= {{#if:  || }}{{#if: 1 |Vorlage:Webarchiv/Wartung/Parameter}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: enWP-Wert im Parameter 'format'.|1}}
  }}{{#ifeq: {{#invoke:Str|find|http://www.cip.informatik.uni-muenchen.de/~zimmermc/sfc/zula/node6.html%7Carchiv}} |-1
    || {{#ifeq: {{#invoke:Str|find|{{#invoke:Str|cropleft|http://www.cip.informatik.uni-muenchen.de/~zimmermc/sfc/zula/node6.html%7C4}}%7Chttp}} |-1
         || {{#switch: {{#invoke:Webarchiv|getdomain|http://www.cip.informatik.uni-muenchen.de/~zimmermc/sfc/zula/node6.html }}
              | abendblatt.de | daserste.ndr.de | inarchive.com | webcitation.org = 
              | #default = {{#if:  || }}{{#if: 1 |Vorlage:Webarchiv/Wartung/URL}}{{#invoke:TemplUtl|failure| Fehler bei Vorlage:Webarchiv: Archiv-URL im Parameter 'url' anstatt URL der Originalquelle. Entferne den vor der Original-URL stehenden Mementobestandteil und setze den Archivierungszeitstempel in den Parameter 'wayback', 'webciteID', 'archive.today' oder 'archive-is' ein, sofern nicht bereits befüllt.|1}}
            }} 
       }}
  }}

• Hilbert- und Peano-Kurve
• Interaktive Demonstration der Hilbert-Kurve
• Die DNA liegt in einer dreidimensionalen Hilbert-Kurve im Zellkern vor
• Video mit 360-Grad-Flug um eine dreidimensionale Hilbert-Kurve

Anmerkungen

<references group="Anmerkung" />

Einzelnachweise

<references />