Abb. 1: Hilbert-Polygone in sieben Iterationen, dazu die Hilbert-Kurve
In der Mathematik ist die Hilbert-Kurve eine (stetige) Kurve, die, wie in der nebenstehenden animierten Abb. 1 veranschaulicht, als Grenzkurve von Polygonzügen die Fläche eines Quadrats vollständig ausfüllt. 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 entdeckt.[1] Die Möglichkeit, mit einer stetigen eindimensionalen Kurve ein zweidimensionales Gebiet komplett abdecken zu können, war den Mathematikern des neunzehnten Jahrhunderts neu (siehe auch Monsterkurve).
Die Hilbert-Kurve wird durch rekursive Iteration definiert und konstruiert. Die
-te Rekursionsstufe wird Hilbert-Kurve der
-ten Iteration[2],
,
und der die Teilquadrate verbindende Polygonzug
Hilbert-Polygon der
-ten Iteration genannt. Die Hilbert-Kurven und die Hilbert-Polygone endlicher Iterationen haben denselben Grenzwert, nämlich die Hilbert-Kurve im engeren Sinn.
Die euklidische Länge des Hilbert-Polygons
ist
, das heißt, sie wächst mit der Nummer
der Iteration über alle Grenzen. Der Limes Hilbert-Kurve hat wie das Quadrat eine Hausdorff-Dimension von exakt 2.
Mithilfe der Hilbert-Kurve endlicher Iteration kann man die Teilquadrate und mithilfe des Limes die Punkte im Quadrat in eine lineare Reihenfolge bringen, die Hilbert-Ordnung genannt wird. Mit ihr lassen sich (effiziente) Verfahren, die auf einer linearen Ordnung beruhen, ins Mehrdimensionale übertragen. Dazu gehört binäres Suchen, binärer Suchbaum, Skip-Liste und andere.
Beim direkten Zugriff steht die Hilbert-Ordnung in Konkurrenz zu einem Zugriff, bei dem die linearen Ordnungen der Dimensionen in unterschiedlicher Rangigkeit zu einer lexikographischen Ordnung hintereinander geschaltet sind – im internen Speicher über ein mehrfach indiziertes Feld resp. im externen Speicher per wahlfreien Zugriff (Random Access). Wenn sich dies gut organisieren lässt, schneidet sie etwas schlechter ab. Sie ist aber überlegen, wenn es sich um eine ungefähre Suche handelt, an die sich eine sequentielle Suche anschließt, bei der Nachbarschaftsbeziehungen (engl. clustering) vorteilhaft ausgenutzt werden können. Dies ist bei
-dimensionalen Räumen
, bei denen Nachbarschaft durch die euklidische Metrik definiert ist, häufig der Fall – beispielsweise, wenn auf geographische Merkmale eines Objekts über die Schlüssel Länge und Breite zugegriffen werden soll.
Die Hilbert-Kurve ist beliebt aufgrund ihrer guten Nachbarschaftserhaltung.[3][4] Bei der Z-Kurve ist die Rechnung geringfügig einfacher, aber die Nachbarschaftserhaltung deutlich schlechter.[5]
Die Zuordnung
der Hilbert-Kurve einer (endlichen)
-ten Iteration ist umkehrbar und kann zu beliebiger Feinheit gesteigert werden. Dieses und die gute Nachbarschaftserhaltung hat eine Vielfalt von Anwendungen der Hilbert-Kurve in der Informatik eröffnet, so in der Bildverarbeitung, Datendarstellung, im Hochleistungsrechnen[6] und in anderen Gebieten.[7]
Abb. 3a: 1. Iteration
der Hilbert-Kurve
Abb. 3b: Hilbert-Kurve
der 2. Iteration
Abb. 3c: Hilbert-Kurve
der 3. Iteration
Abb. 3d: 3D-Hilbert-Kurven, 1. bis 3. Iteration
Die Abb. 3a bis 3c aus dem definierenden Artikel[1] zeigen die drei ersten Iterationen der Hilbert-Kurve. Bei der
-ten Iteration bringen
Nummern die
Intervalle (Teilstrecken der Linie oben in den Grafiken) und die
Quadrate mit gleichen Nummern zur Entsprechung. Die verstärkten polygonalen Linien
bringen genau diese Reihenfolge der Quadrate heraus.[8]
Eine nachfolgende Iteration verfeinert – bei Intervallen wie bei Quadraten – die Schachtelung um den Faktor 4.
Die Konstruktion der Hilbert-Kurve als einer raumfüllenden Kurve
![{\displaystyle {\begin{array}{llllll}h\;\colon &{\mathcal {I}}:=[0,1]:=\{t\mid 0\leq t\leq 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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cffb38608241a5ffcc269479881891616d18e22d)
beruht auf einem rekursiven Verfahren:
- Das Verfahren beginnt mit dem (mehrdimensionalen Einheits-Intervall)
als dem zu füllenden
-dimensionalen Gebiet.
- Jedes Gebiet wird aufgeteilt in
kongruente Teilgebiete (
-dimensionale Intervalle) der halben Seitenlänge und auf der Eingabeseite ein Intervall in
gleichlange 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.[8]
- 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)[9]
- Die Spiegelungs- und Rotationsoperationen lassen sich so wählen, dass sich die
Teilkurven zu einer einzigen gerichteten Kurve zusammenfügen.
Eine Hilbert-Kurve wird wesentlich durch die Reihenfolge charakterisiert, in der die Teilgebiete hintereinander aufgesucht (traversiert) werden.
Mit wachsender Dimensionszahl
wächst die Anzahl der unterschiedlichen Hilbert-Kurven, die sich dann auch in ihrer Nachbarschaftserhaltung stark unterscheiden können.
Dieser Artikel beschränkt sich fast ausschließlich auf die Dimensionszahl
, also auf die Abbildung des Einheitsintervalls
auf das Einheitsquadrat
.
Bei dieser Dimensionszahl treten alle einschlägigen mathematischen Phänomene bereits in Erscheinung.
Während die Hilbert-Kurve (auf der Ausgabeseite) ein „Teilquadrat“ durchläuft (füllt), soll auch der Parameter
auf der Eingabeseite das ihm entsprechende Teilintervall durchlaufen. Dies entspricht der Vorgabe, dass die Hilbert-Kurve in allen Bereichen »gleich schnell« voranschreitet.
Um dies sicherzustellen, wird als Intervallschachtelung auf der Parameterseite die („4-adische“) Darstellung von
im Quaternärsystem mit
gewählt.[10] Es sei
gesetzt, so dass
[11]
ein Intervall in der
-ten Schachtelung des Parameters
ist.
Auf der Seite des Quadrats (Ausgabeseite) werden die Koordinaten
und
im Binärsystem („2-adisch“) dargestellt mit
. Die (abbrechenden) Koordinaten
mit
und
stehen dabei für das Teilquadrat, das diese Koordinaten zur linken unteren Ecke hat. Und die Folge der durch
spezifizierten Quadrate, die die Seitenlänge
und die Fläche
haben, macht eine 2D-Intervallschachtelung in der Ebene aus. Diese
D-Schachtelungen seien als die „Rasterschachtelung“
(der Hilbert-Kurve) bezeichnet.
Die
-te Iteration
der „Hilbert-Kurve“ ist eine geordnete Folge von
von (an genau einer Quadratseite mit dem Folgequadrat zusammenstoßenden) Quadraten (oder deren linken unteren Eckpunkten resp. deren Mittelpunkten). Diese Folge wird am besten durch einen gerichteten Polygonzug von Quadratmittelpunkt

zu Quadratmittelpunkt (Parameter
) verdeutlicht.
Dieser Polygonzug
enthält alles Wichtige und wird häufig als das Hilbert-Polygon (engl. auch approximating curve[12] und Hilbert pseudo curve) der
-ten Iteration bezeichnet (Beispiele finden sich in den Hilbert-Kurven der 1. bis 3. Iteration der obigen Abbildungen).
Im Folgenden wird gezeigt, wie die
Quadrate eines Rasters
sämtlich in eine Reihenfolge
gebracht werden, derart, dass sie bei wachsendem
immer kleiner werden, einander näher rücken und im Limes eine Kurve bilden.
Im Sinn des obigen Programms sei rekursiv angenommen, dass in einem Teilquadrat
ein Kurvenpunkt der selbstähnlichen Hilbert-Kurve berechnet ist. Es geht nun darum, diesen Punkt (resp. dieses Teilquadrat) so in das Quadrat
zu holen, dass alle solche Punkte zusammen genommen eine zusammenhängende Kurve (resp. eine zusammenhängende Folge von Teilquadraten des Rasters
) ergeben. Eine solche Transformation lässt sich zerlegen in:
die Verkleinerung des Quadrats linear um den Faktor , |
(Skal)
|
eine (die Hilbert-Kurve charakterisierende) Parallelverschiebung und |
(Parv)
|
eine Isometrie (= orthogonale Abbildung = Drehung und/oder Spiegelung). |
(Ausr)
|
Für die Wahl der passenden Drehungen und/oder Spiegelungen ist die Festlegung hilfreich, wo ein Quadrat einer Rasterschachtelung
von der Kurve betreten und wo es verlassen wird. Bei der Hilbert-Kurve sind dies die Ecken genau einer Quadratseite.[13] Da es auch auf die Richtung und Orientierung ankommt, werde dieses Charakteristikum eines Quadrats im Raster mit dem Begriff „Ausrichtung“ (engl. orientation[3], state[14]) versehen und die Ausrichtung „hoch—rechts—runter“ (in Koordinaten
resp. die Strecke
für „Eintritt links unten—Austritt rechts unten“) mit dem Buchstaben
gekennzeichnet.[15]
Aber auch die bloße Platzierung des Teilquadrats hängt von der Ausrichtung ab. Ist das große Quadrat
(links in der Abbildung 4) gemäß
ausgerichtet, dann wird bei der Hilbert-Kurve das Quadrat
abhängig von der Quaternärziffer
in eines der vier Teilquadrate platziert, und zwar platziert die Quaternärstelle
nach links unten,
nach links oben,
nach rechts oben und
nach rechts unten, also nach dem „Grundmuster“ (engl. base pattern[12] oder basic pattern[16])
.[17][18] Ein Grundmuster für die 3-dimensionale Hilbert-Kurve ist
(s. a. den Abschnitt Ausblick auf 3 Dimensionen).
Andere Ausrichtungen (als
, und auch Platzierungsmuster) lassen sich durch eine vorgeschaltete Isometrie aus der Diëdergruppe
des Quadrats darstellen.
Die zur Herstellung des einfachen Zusammenhangs (und damit der Stetigkeit im Limes) erforderlichen Drehungen und/oder Spiegelungen sind ebenfalls Isometrien aus
und zusammen mit der Platzierung auszuführen. Diese Kombination wird im folgenden Abschnitt unter dem Begriff „Transformation“ beschrieben.
Transformation der rekursiven Teilquadrate auf das Einheitsquadrat[Bearbeiten | Quelltext bearbeiten]
Abb. 4: Die Einbettung des Teilquadrats der
-ten Iteration rechts resp. eines seiner Punkte

in das 4 mal so große Quadrat links – in welches Teilquadrat und wie, wird von der Quaternärziffer

abhängig gemacht.
Um den Wechsel der Ausrichtung von einer Iteration zur nächsten präzise zu erfassen, sei angenommen, dass beide Quadrate, das große (links in der Abbildung 4) wie das Teilquadrat (rechts) gleich, bspw. gemäß
, ausgerichtet sind.
Die benötigten vier Transformationen[19][20] hängen von der Quaternärziffer
ab und seien mit
und
bezeichnet:
 |
|
 |
|
Alle Transformationen skalieren zunächst die übergebenen Koordinaten
des Punktes mit dem Faktor
, da die Teilquadrate die halbe Seitenlänge haben, und enthalten eine Verschiebung in das durch
(s. o.) bestimmte Teilquadrat. Zudem ist von einer Transformation je nach Lage ggf. eine (von
abhängige) Viertelrotation, Spiegelung, d. h. eine Kongruenzabbildung
durchzuführen:
- Bei
kommt die Transformation
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
.
- Die Zielquadrate bei den Transformationen
und
haben dieselbe Ausrichtung
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.
verschiebt bei
die Kurve um
in
-Richtung, also ins linke obere Teilquadrat.
verschiebt für
die Kurve diagonal ins rechte obere Teilquadrat.
Die Eintrittsecke des Teilquadrats mit
fällt mit der Austrittsecke von
und die Austrittsecke von
mit der Eintrittsecke von
zusammen.
- Die Transformation
spiegelt für
ihr Argument an der »Nebendiagonalen« (strichpunktiert in Abbildung 4), wodurch sich der Drehsinn des Quadrats ändert. Danach wird das gespiegelte Ergebnis um
in
-Richtung, also ins rechte untere Teilquadrat verschoben, so dass die Eintrittsecke rechts oben liegt – an der Stelle der Austrittsecke des vorangehenden Teilquadrats mit
– und die Austrittsecke mit der Austrittsecke des Ausgangsquadrates übereinstimmt (rechts unten).
Ersichtlich sind die Punkte
über die sie enthaltenden Quadrate in eine Reihenfolge gebracht, die der Reihenfolge der Intervalle des Parameters
entspricht – sowohl bezüglich der 4 Teilquadrate
als auch bei den Anschlüssen zwischen zwei Quadraten
.
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
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
.
Die Abbildung 4 zeigt darüber hinaus, dass ausgehend von der Ausrichtung
zwei neue (absolute) Ausrichtungen
(:= „rechts—hoch—links“) und
(:= „links—runter—rechts“) hinzukommen, und die Abbildungen 7 und 5, dass nur noch eine weitere Ausrichtung (:= „runter—links—hoch“), genannt
, fehlt, so dass es bei insgesamt vier Ausrichtungen bleibt. Sie seien im Folgenden in der Menge
zusammengefasst. Die zugehörige Gruppe
der benötigten Isometrien ist eine Untergruppe der Diedergruppe
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.
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

findet sich am Schnittpunkt von

-Spalte mit

-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 
angegeben (grün).
Der Mittelpunkt

des großen (und jedes) Quadrats ist ein
Tripelpunkt. Er hat

.
In der Abbildung 5 ist das große Quadrat, das Quadrat der
-ten Iteration (= Quadrat des Rasters
), gemäß
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
, 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.[21]
Bemerkung 1
Weil im vorstehenden Abschnitt das Quadrat der Iteration
»zeitlich« vor dem großen Quadrat
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
) 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
(s. Abschnitt #Hilbert-Polygon) eine große Rolle und wirkt sich auf die (Art der) Stetigkeit von
(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
wird im entsprechenden Abschnitt vorgestellt.
In diesem Kapitel wird mit
die endliche Iterationsstufe bezeichnet, die Einheitsintervalle
und
sind oben halboffen, und für
, bspw.
oder
, ist

eine diskrete Menge von
Elementen.
Die Zuordnung der Hilbert-Kurve
der
-ten Iteration ist

Das Bild
ist eine diskrete Menge, und zwar ist
.
Die Koordinaten
stehen dabei für linke untere Ecken von Quadraten des Rasters
.
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
Ecken die
Quadratmittelpunkte

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
der
-ten Iteration bezeichnet.[22]
Die diskrete Funktion
, d. i. die Einschränkung von
auf die diskrete Menge
, ist umkehrbar und hat die Umkehrfunktion
, die im Abschnitt Hilbert-Index behandelt wird. Nach Konstruktion ist ferner

woraus die Implikation

(und im Limes die gleichmäßige Stetigkeit) folgt.
Abb. 6: Hilbert-Polygon der 6. Iteration
Das Hilbert-Polygon
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
, die also mit
über alle Grenzen wächst. Alle Hilbert-Polygone derselben Iteration
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
-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
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.[23] 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
, wie in der Abb. 4 dargestellt, in dasjenige Rasterquadrat gebracht, das dem eingegebenen Teilintervall von
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
-ten Quadrats von Teilen der
-sten oder höherer Iterationsstufe überhaupt nicht, weder hinsichtlich der Ziffern
(mit
) des Parameters
noch hinsichtlich der Ziffern
der Koordinaten
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.
Der nachfolgende Pseudocode t2xyR
[24] implementiert rekursiv die Abb. 4 mit
als Ausrichtung für Zwischen- wie Endergebnis. Er nimmt als Argument einen Parameter
und eine Begrenzung eps
der Iterationstiefe. Zurückgegeben werden die Koordinaten der linken unteren Ecke eines Quadrates der
-ten Iteration.
Eingabe: |
Parameter
|
Ausgabe: |
Koordinaten
|
Auswertungsrichtung: |
fein zu grob
|
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
Abb. 7: Die 4 Übersetzungs-
tabellen vom 4-adischen Parameter

zu den zwei 2-adischen Koordinaten

– und zurück.
Pro „Ausrichtung“ eine Tabelle.
Iterativer Algorithmus mit ganzzahligen Ein-/Ausgabewerten[Bearbeiten | Quelltext bearbeiten]
Bei der folgenden iterativen Lösung ist
die Nummer der Iteration und
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
|
Ausgabe: |
Koordinaten
|
Auswertungsrichtung: |
fein zu grob
|
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
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.
Eingabe: |
Parameter
|
Ausgabe: |
Koordinaten
|
Auswertungsrichtung: |
grob zu fein
|
Ist
eine 4-adische Darstellung des Parameters, dann lässt sich die (unendliche) Folge
auch als Rekursion[25] über die Quadratmittelpunkte

und die „absolute“ Ausrichtung
mit dem Rekursionsanfang
 |
und
|
 |
und
|
 |
Ausrichtung am Rekursionsanfang (= initiale Ausrichtung)[26][27]
|
und dem Rekursionsschritt
 |
 |
(RFh_ξ),
|
 |
 |
(RFh_η)[28] und
|
 |
 |
(RFh_a)
|
für
schreiben. Die drei (4×4)-Matrizen
![{\displaystyle 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}](https://wikimedia.org/api/rest_v1/media/math/render/svg/2b9488ee7457bcb32bae99d2dd54277748f16123)
sind äquivalent zu den vier Übersetzungstabellen der Abbildung 7. Sie werden an ihrem ersten Index, dem Zeilenindex, durch die absolute Ausrichtung
indiziert. Das Ergebnis ist bei
,
und
jeweils eine vierstellige Zeile, die zusammen genommen eine der Übersetzungstabellen darstellen.
Jede Stelle (Spalte) einer solchen Zeile wird durch die Quaternärziffer
indiziert.
Daraus resultiert (Gl.n RFh_ξ und RFh_η) das neue Ziffernpaar
für den Punkt
und (Gl. RFh_a) die neue absolute Ausrichtung.
Die Folge
der Quadratmittelpunkte mit
und
, steht für die 2D-Intervallschachtelung
![{\displaystyle {\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 \mathbb {N} }\\=&{\bigl (}[x_{n},&x_{n}+2^{-n}]&\times \;[y_{n},&y_{n}+2^{-n}]{\bigr )}_{n\in \mathbb {N} },\\\end{array}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/5bab690035daab8d7924d74d836cb3e6382fb8b6)
die
zum Limes hat.
Beweis der Rekursionsformel
|
Die Gleichung RFh_a akkumuliert – wie in der Erläuterung zur Abb. 7 ausgeführt – die relativen Ausrichtungen[29] (Teil Ausr) zwischen Viertelquadrat und großem Quadrat und implementiert damit (zusammen mit der 2D-Intervallschachtelung (Teil Skal) der Gl.n RFh_ξ und RFh_η) die Transformationen und (Teil Parv) des Abschnitts #Transformation der rekursiven Teilquadrate auf das Einheitsquadrat.
|
Erläuterungen zu den Abbildungen 7 und 8
|
Die oberste der vier Graphiken der Abb. 7, die für die Ausrichtung , ist ein Auszug aus der Abb. 4.
Aus der Abb. 5 kann man die Daten zur zweiten und vierten Ausrichtung und direkt ablesen; für die dritte Ausrichtung 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 (s. o.) und den Hypermatrizen (s. u.)) eingehalten.
Die vier Graphiken unterscheiden sich hinsichtlich des Charakteristikums Ausrichtung durch eine der Isometrien aus der Gruppe .
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,[30] durch die die Matrizen entsprechend vergrößert werden. Es bleibt aber bei der Anzahl vier hinsichtlich der Übersetzungstabellen, die der Anzahl
der Ausrichtungen entspricht. Das Verfahren bezeichnet M. Bader[31] als recursion unrolling (dt. etwa Ab/Entrollen der Schleife). Es kann die Algorithmen wesentlich beschleunigen, weil weniger Schleifenkontrollanweisungen, Speicherzugriffe und/oder Programmaufrufe zu absolvieren sind. (Abgesehen davon können Bit-Shift-Operationen, die auf vielen Maschinen erforderlich wären, durch geschickte Wahl der Ziffernzahl eingespart werden.)
Exemplarisch für 2 Iterationen:
 |
00 |
01 |
01 |
00 |
00 |
00 |
01 |
01 |
10 |
10 |
11 |
11 |
11 |
10 |
10 |
11 |
 |
|
←  |
|
11 |
11 |
10 |
10 |
01 |
00 |
00 |
01 |
01 |
00 |
00 |
01 |
10 |
10 |
11 |
11 |
|
←
|
11 |
10 |
10 |
11 |
11 |
11 |
10 |
10 |
01 |
01 |
00 |
00 |
00 |
01 |
01 |
00 |
|
←
|
00 |
00 |
01 |
01 |
10 |
11 |
11 |
10 |
10 |
11 |
11 |
10 |
01 |
01 |
00 |
002 |
|
←
|
|
 |
00 |
00 |
01 |
01 |
10 |
11 |
11 |
10 |
10 |
11 |
11 |
10 |
01 |
01 |
00 |
00 |
 |
|
←  |
|
11 |
10 |
10 |
11 |
11 |
11 |
10 |
10 |
01 |
01 |
00 |
00 |
00 |
01 |
01 |
00 |
|
←
|
11 |
11 |
10 |
10 |
01 |
00 |
00 |
01 |
01 |
00 |
00 |
01 |
10 |
10 |
11 |
11 |
|
←
|
00 |
01 |
01 |
00 |
00 |
00 |
01 |
01 |
10 |
10 |
11 |
11 |
11 |
10 |
10 |
112 |
|
←
|
|
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
|
←  |
|
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
|
←
|
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
|
|
←
|
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
|
←
|
|
|
↑ |
↑ |
↑ |
↑ |
↑ |
↑ |
↑ |
↑ |
↑ |
↑ |
↑ |
↑ |
↑ |
↑ |
↑ |
↑ |
|
|
|
|
00 |
01 |
02 |
03 |
10 |
11 |
12 |
13 |
20 |
21 |
22 |
23 |
30 |
31 |
32 |
334 |
|
|
|
|
- Die Abbildung 8 ist eine leichte Abwandlung der Fig. 4.1 aus J. Lawder[32]. Sie zeigt im Wesentlichen dieselbe Information wie die Abbildung 7 – in der Art eines Zustandsübergangsdiagramms, bei dem der Übergang in die nächste Iterationsstufe (zum nächsten Viertelquadrat) als »Zustandsänderung« aufgefasst wird.
- Zum besseren Rechnen werden die Ausrichtungen als Restklassen
modulo 8 geschrieben, und zwar
![{\displaystyle \mathbf {A} :=[1],\,\mathbf {B} :=[3],\,\mathbf {C} :=[5],\,\mathbf {D} :=[7].}](https://wikimedia.org/api/rest_v1/media/math/render/svg/1c35adefcfd90e0befd57d041563a930e8a3272f)
Nur die primen Restklassen kommen als Ausrichtung vor. Zum Rechnen werden auch hier beide Verknüpfungen sowie des Rings gebraucht.
- Die Gruppe
lässt sich als Matrizengruppe mit
![{\displaystyle v_{1}:=\left[{\begin{smallmatrix}{\begin{array}{rr}1&0\\0&1\end{array}}\end{smallmatrix}}\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/7f3ab5869904496dd0c64d0715e8f1f26809a64c) |
als Identität |
![{\displaystyle [1]\!\to \![1],\;[3]\!\to \![3],\;[5]\!\to \![5],\;[7]\!\to \![7]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/22eb3da957d5d573ca6d64d3861de314615a60ab) |
( ),
|
![{\displaystyle v_{5}:=\left[{\begin{smallmatrix}{\begin{array}{rr}-1&0\\0&-1\end{array}}\end{smallmatrix}}\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/760bc1b27f1c77645ce4e0ff774a048734569f92) |
als Punktspiegelung |
![{\displaystyle [1]\!\to \![5],\;[3]\!\to \![7],\;[5]\!\to \![1],\;[7]\!\to \![3]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/b579be524f46aec134a0a9533dd9ba9615bad147) |
( ),
|
![{\displaystyle v_{7}:=\left[{\begin{smallmatrix}{\begin{array}{rr}0&1\\1&0\end{array}}\end{smallmatrix}}\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f553446b25687ab156a4fce84ac6570bfa396cd4) |
als Spiegelung an der Hauptdiagonalen |
![{\displaystyle [1]\!\to \![7],\;[3]\!\to \![5],\;[5]\!\to \![3],\;[7]\!\to \![1]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d759bc9e91e6bd56e4779073601beb863e3e2e95) |
( ) und
|
![{\displaystyle v_{3}:=\left[{\begin{smallmatrix}{\begin{array}{rrrr}0&-1\\-1&0\end{array}}\end{smallmatrix}}\right]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/e2c311393c6b3bcdf0e4fa1a071223176d733979) |
als Spiegelung an der Nebendiagonalen |
![{\displaystyle [1]\!\to \![3],\;[3]\!\to \![1],\;[5]\!\to \![7],\;[7]\!\to \![5]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/9af86676c642570aa8c1035ef8afd5089ea11d24) |
( )
|
schreiben.
Rechts vom -Zeichen ist die Multiplikation mit einer primen Restklasse aufgeführt, die offensichtlich ein Ergebnis liefert, das der Anwendung der Matrix gemäß (Ausr) auf die Ausrichtung entspricht.
- Ferner ergibt sich
 |
![{\displaystyle [7]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ae3ad60d04a4ab654d5432b8d207c296bc9157ba) |
![[1]](https://wikimedia.org/api/rest_v1/media/math/render/svg/83021ecdd7307a04dbb7873affcaac031e7e935a) |
![[1]](https://wikimedia.org/api/rest_v1/media/math/render/svg/83021ecdd7307a04dbb7873affcaac031e7e935a) |
![{\displaystyle [3]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f671027d56f9c24d65c03a4a26eb0d3b933f4f15) |
 |
|
![{\displaystyle \leftarrow \,\,[1]\,=\,\mathbf {A} }](https://wikimedia.org/api/rest_v1/media/math/render/svg/32f05b35f55eea9b83ad96715875da399e793cf6) |
|
![{\displaystyle [5]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/958ef87021d704de46ad116821bc677e07d9a5fe) |
![{\displaystyle [3]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f671027d56f9c24d65c03a4a26eb0d3b933f4f15) |
![{\displaystyle [3]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f671027d56f9c24d65c03a4a26eb0d3b933f4f15) |
![[1]](https://wikimedia.org/api/rest_v1/media/math/render/svg/83021ecdd7307a04dbb7873affcaac031e7e935a) |
|
|
![{\displaystyle [3]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f671027d56f9c24d65c03a4a26eb0d3b933f4f15) |
![{\displaystyle [5]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/958ef87021d704de46ad116821bc677e07d9a5fe) |
![{\displaystyle [5]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/958ef87021d704de46ad116821bc677e07d9a5fe) |
![{\displaystyle [7]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ae3ad60d04a4ab654d5432b8d207c296bc9157ba) |
|
|
![[1]](https://wikimedia.org/api/rest_v1/media/math/render/svg/83021ecdd7307a04dbb7873affcaac031e7e935a) |
![{\displaystyle [7]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ae3ad60d04a4ab654d5432b8d207c296bc9157ba) |
![{\displaystyle [7]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/ae3ad60d04a4ab654d5432b8d207c296bc9157ba) |
![{\displaystyle [5]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/958ef87021d704de46ad116821bc677e07d9a5fe) |
|
|
|
 |
 |
 |
 |
|
|
|
|
 |
 |
 |
 |
|
|
|
als neues Erscheinungsbild der Matrix .
Die (Gl. RFh_a) ist dann gleichbedeutend mit der Formel
 |
 |
für |
|
 |
für |
|
 |
für |
|
![{\displaystyle [3]\times a_{n-1}(t)}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a691af90904902a42dc62ed465ece19e7840f5a6) |
für |
|
was bedeutet, dass die Ausrichtung des dem Parameter in der -ten Iteration zugeordneten Quadrates nur
- von der Ausrichtung
und
- von der Quaternärziffer

abhängt, und dass es keine weitere, insbesondere keine umgekehrte Abhängigkeit gibt, also dass von abhinge, wie man aus der Herleitung in Abschnitt #Transformation der rekursiven Teilquadrate auf das Einheitsquadrat schließen könnte.
- Anhand der neuen Darstellung der Matrix
verifiziert man leicht, dass
![{\displaystyle A_{a,\tau }+A_{[2]-a,\,3-\tau }=[2]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a28c8ecffb005975c35cd312b4894c17deb51494) |
(Sym1)
|
für und gilt. Daraus folgt für und mit :
![{\displaystyle a_{n}(t)+a_{n}(s)=[2]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/0942950f465dbb5a8d2c7294544b068c795c2e2e) |
(Sym2).[33]
|
Denn der Induktionsanfang ist und . Ferner ist nach der Induktionsannahme und nach (Sym1)
.
Aus (Sym2) und durch Inspektion der Matrix ergibt sich
![{\displaystyle X_{a_{n-1}(t),\,\tau _{n}}+X_{a_{n-1}(s),\,\sigma _{n}}=X_{a_{n-1}(t),\,\tau _{n}}+X_{[2]-a_{n-1}(t),\,3-\tau _{n}}=1}](https://wikimedia.org/api/rest_v1/media/math/render/svg/a124141d273974fea119d5b5ab10a88c178020e2)
und genauso bei
.
- Symmetrieeigenschaft: Für jedes
ist und .
Induktionsanfang: und .
Induktionsschritt:


|
Die Funktion
hat die Definitionsmenge
, die Einschränkung
die Definitionsmenge
, beide haben die Bildmenge
, die eine diskrete Menge ist.
Die Funktion
ist umkehrbar mit der Umkehrfunktion

welche Hilbert-Index genannt wird. Sie hat ihrerseits die Bildmenge
.
Unter den Einschränkungen auf die diskreten Mengen
resp.
sind die Funktionen
wie
umkehrbar eindeutig und es gilt
und
.[34]
Werden ihre Argumente
und
gleichermaßen als Binärbrüche entwickelt, dann kann man auch beliebige (
-stellige) Koordinaten
und
zulassen, in der zu definierenden Funktion
als erstes die Stellen rechts ab der
-ten Stelle abschneiden,[35] sodann
ausführen, die Einschränkung auf die diskrete Menge
wieder aufheben und somit das ganze Einheitsquadrat
zur Definitionsmenge der Funktion

erklären, so dass deren Einschränkung
der Funktion
vom Eingang des Abschnitts entspricht.
Somit ergibt sich für alle
sowohl

wie

Die Rückabwicklung der Transformationen
und
ist in den nachfolgenden Algorithmen im Einzelnen ausgeführt.
Die Auswertungsrichtung des Algorithmus xy2tR
[36] ist entgegen der Intervallschachtelung.
Eingabe: |
Koordinaten
|
Ausgabe: |
Parameter
|
Auswertungsrichtung: |
fein zu grob
|
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
Iterativer Algorithmus mit ganzzahligen Ein-/Ausgabewerten[Bearbeiten | Quelltext bearbeiten]
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
die Nummer der Iteration, dann ist
die Anzahl der 1D-Teilintervalle.
Eingabe: |
Koordinaten
|
Ausgabe: |
Parameter
|
Auswertungsrichtung: |
grob zu fein
|
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
Abb. 8: Die Ausrichtung

bestimmt den großen Kasten. In jedem 4 kleine Kästen, wo sich Quaternärziffer

des Parameters und Binärziffern

der 2 Koordinaten gegenüberstehen; 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.
Eingabe: |
Koordinaten
|
Ausgabe: |
Parameter
|
Auswertungsrichtung: |
grob zu fein
|
Sind
und
Darstellungen der Koordinaten
im Binärsystem, dann lässt sich die (unendliche) Folge
auch als Rekursion mit dem Rekursionsanfang
 |
und
|
 |
(Start mit der initialen Ausrichtung )[37]
|
und dem Rekursionsschritt
 |
 |
(RFk_τ)
|
 |
 |
(RFk_a)
|
für
schreiben.
Die zwei (4×2×2)-Hypermatrizen
![{\displaystyle {\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}}}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4edc879ce180d90114c93d7d2457b9a56d199710)
sind zusammen genommen äquivalent zu den vier Übersetzungstabellen der Abbildung 7. Sie werden an ihrem ersten Index durch die absolute Ausrichtung
indiziert. Das Ergebnis ist bei
wie bei
eine (2×2)-Untermatrix. Jedes solche Paar von Untermatrizen stellt eine Übersetzungstabelle dar.
Eine Untermatrix wird durch das Binärziffernpaar
indiziert. Daraus resultiert (Gl. RFk_τ) die neue Quaternärziffer
für den Parameter
und (Gl. RFk_a) die neue absolute Ausrichtung
.
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 , die der (absoluten) Ausrichtung des großen Quadrats sowie der Lage des kleinen Quadrats im großen Quadrat, nämlich den Ziffern , 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 ), ins linke obere (bei ) etc. Teilquadrat gehört, woraus die Ziffer resultiert.
Dies geschieht in Einklang mit den Transformationen bis aus dem Abschnitt #Transformation der rekursiven Teilquadrate auf das Einheitsquadrat, denn die Gleichung (RFk_a), die die absolute Ausrichtung rekursiv festlegt, ist eine Akkumulation[38] der relativen Ausrichtungen, die durch jene Transformationen bewirkt werden.
|
Im Limes, also bei exakt
, 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
anstelle der halboffenen Intervalle
und
ihre abgeschlossenen Hüllen
und
betrachtet werden.
Mit den Hilbert-Kurven
(und den Hilbert-Polygonen
) lässt sich zu jedem positiven Abstand
eine Iterationsstufe
angeben, so dass es zu jedem Punkt
des Einheitsquadrats einen Punkt
des Rasters
gibt, der einen kleineren Abstand
hat. Das bedeutet aber nicht die vollständige Füllung des Quadrats.
Diese kann nur durch den Übergang zum Limes erreicht werden. Der Limes

existiert immerhin, da er aus der 2D-Intervallschachtelung
![{\displaystyle {\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 \mathbb {N} }}](https://wikimedia.org/api/rest_v1/media/math/render/svg/d8d13bcc439d83fd5584747912cfe421543ecf3d)
hervorgeht.
Die Konvergenz ist eine gleichmäßige im folgenden Sinn:
Für jedes
ist
so, dass für alle Parameter
und alle
mit

gilt.
ist rechtseindeutig, somit wohldefiniert und eine Funktion.
ist surjektiv.
ist nicht injektiv.
ist stetig, definiert also eine Kurve. Die Stetigkeit ist eine gleichmäßige.
- Die Bilder des durch 3 geteilten Rasters
sind genau die Eckpunkte
der entsprechenden Rasterquadrate.
.
- Ist
die initiale Ausrichtung, dann ist
symmetrisch zur Geraden
:
Für jedes
ist
und
.
Bei
als initialer Ausrichtung wäre es die Gerade 
und
und
.
- Ist
, dann ist
.
- Ist
rational, dann ist seine 4-adische Darstellung periodisch, bspw.
mit der Periodenlänge
. Die Koordinaten
von
sind dann beide ebenfalls rational mit einer 2-adischen Periodenlänge
, wobei
die Mächtigkeit der Menge
der Ausrichtungen ist.[39]
ist nirgends differenzierbar.[1][8]
ist Maß-erhaltend: Für jede Punktmenge
mit ein-dimensionalem Lebesgue-Maß
hat das Bild
das
-dimensionale Lebesgue-Maß
.[12] Das bedeutet auch, dass jedes Intervall
in eine zusammenhängende (möglicherweise unendliche) Folge
von Quadraten der Rasterschachtelung abgebildet wird.
Beweise der Eigenschaften
|
Zu Eigsch. 1: |
ist Funktion.
|
In der Tat ist nicht von vorne herein 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 [40], gibt es zwei Möglichkeiten der Darstellung. Beispielsweise hat der Bruch die Darstellung mit einem periodischen 04. …0-Ende

(die als die »abbrechende Darstellung« bezeichnet wird, weil sie auch als endliche 4-adische Summe geschrieben werden kann) und die mit einem 04. …3-Ende
.
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 die Forderung der Rechtseindeutigkeit an die Relation in Frage. Im Folgenden wird aber gezeigt, dass sie sich nicht auf das Ergebnis von auswirkt.[41]
- Wegen
muss gelten: . In der Tat ist wegen eine 2D-Intervallschachtelung mit dem für alle existierenden Limes .
- Für
muss wegen (mit als der Ziffer mit dem Wert ) gelten: , damit sein kann. Zunächst ist wegen eine 2D-Intervallschachtelung mit dem für alle existierenden Limes . Schließlich ist
 |
,
|
 |
und
|
 |
.
|
Zu Eigsch. 2: |
ist surjektiv.
|
Da bei jeder Iterationsstufe aus jedem Teilquadrat genau vier kleinere Teilquadrate gemacht werden, überdecken die Teilquadrate einer Iterationsstufe immer das ganze Ausgangsquadrat. Das Teilquadrat wird im Limes zum Kurvenpunkt. Somit füllt die Menge der Kurvenpunkte das ganze Ausgangsquadrat aus.
Etwas ausführlicher: Zu einem Punkt gibt es zwei 1D-Intervallschachtelungen und .
Für die Hilbert-Indizes gilt , so dass
eine 1D-Intervallschachtelung für einen Parameter ist. Für diesen gilt

Zu Eigsch. 3: |
Dennoch ist nicht injektiv.
|
( kann als surjektive und stetige (s. u.) Funktion von 1D nach 2D nach dem Satz von der Invarianz der Dimension nicht injektiv sein.)
Die oben gebildeten zwei 1D-Intervallschachtelungen sind genau dann mehrdeutig, wenn eine der beiden Koordinaten in liegt.[40]
Beispielsweise ist
 |
|
(Doppelpunkt),
|
 |
|
(Tripelpunkt)[19],
|
 |
|
(Tripelpunkt), und
|
 |
|
(Quadrupelpunkt)[19]
|
Jedes Teilquadrat enthält einen Tripel- und einen Quadrupelpunkt und damit abzählbar unendlich viele.
Die Menge der Doppelpunkte ist überabzählbar.
Zu einem Punkt gibt es maximal vier verschiedene Parameterwerte mit .[1]
Zu Bildpunkten gibt es nur ein Urbild.
Zu Eigsch. 4: |
ist stetig.
|
ist sogar Hölder-stetig[42] (was die gleichmäßige Stetigkeit[19] einschließt), und zwar zum Exponenten mit als der Dimension des Zielraums .
bildet zwei benachbarte Intervalle stets auf zwei benachbarte Quadrate (mit gemeinsamer Seite) ab. Und da alle Quadrate späterer Iterationen den früheren treu bleiben (s. Abb. 4), folgt die gleichmäßige Stetigkeit.[43]
Zu Eigsch. 5: |
.
|
Die Drittelwerte von Ganzzahlen haben in ihrer 4-adischen Darstellung 04.0-, 04.1- oder 04.2-Enden.
Durch den Algorithmus werden daraus 02.0- oder 02.1-Enden, also ganze Zahlen.
Die Division durch exakte Zweierpotenzen ändert an den periodischen Enden der Darstellungen nichts.
Zu Eigsch. 6: |
.
|
Ist , dann ist ein abbrechender 4-adischer Bruch.
Folglich sind auch die Koordinaten zwei abbrechende 2-adische Brüche.
Nimmt man für die nicht-abbrechende 4-adische Darstellung mit 0-Ende, dann werden gemäß Abb. 7 bei den Koordinaten auch nur Nullen angehängt, da die Ausrichtungen zwischen und alternieren und bei beiden Ausrichtungen aus der Ziffer die Koordinatenziffern resultieren.
Damit ist
Zu Eigsch. 7: |
und .[19]
|
Schon für alle gilt aus Symmetriegründen ; genauso . (S. a. den Beweis für denselben Sachverhalt im Abschnitt #Explizite Rekursionsformel.)
Die Eigsch. 8: |
|
ist eine direkte Folge der Transformation . Iteriert ergibt sich .
Zu Eigsch. 9: |
.
|
Der Pseudocode t2xyQ nimmt den ganzzahligen Zähler und Nenner tn,td eines rationalen Parameters  tn/td mit 0 ≤ tn ≤ td und produziert die ganzzahligen Zähler und Nenner xn,xd, yn,yd der 2 Koordinaten  (xn/xd,yn/yd)  tn/td .
Er ist eine Erweiterung des Pseudocodes b_adic im Artikel Stellenwertsystem – in der folgenden Hinsicht, dass abhängig vom Rest tn nicht nur die Ziffern des Parameters , sondern aus diesen und der Ausrichtung a sofort die 2-adischen Ziffern der Koordinaten und gebildet werden.
(Die letzteren beiden Darstellungen werden am Ende wieder in Brüche umgeformt.)
Die Wiederkehr einer Konstellation (a,tn) wird mittels des assoziativen Datenfeldes occurs festgestellt.
Die Datenfelder X , Y und A stehen für die obigen Matrizen und . Der Doppelstern ** ist das Zeichen für Potenzierung.
function t2xyQ(tn,td) begin // 0 ≤ tn ≤ td (> 0)
if tn = td then return (1,1, 0,1); end if
// Ab hier ist stets 0 ≤ tn < td.
pos = 0;
xp = 0; yp = 0;
a = 0; // initiale Ausrichtung
key = a+tn*4; // die Konstellation (a,tn) als Schlüssel
while not defined(occurs[key]) do
occurs[key] = pos; // die Nummer der Stelle mit (a,tn)[44]
ti = floor(tn*4/td); // Quaternärziffer ti: 0 ≤ ti ≤ 3
tn = tn*4 − ti*td; // 0 ≤ tn < td
xp = xp*2 + X[a,ti]; // obige Matrix X
yp = yp*2 + Y[a,ti]; // obige Matrix Y
a = A[a,ti]; // obige Matrix A
key = a+tn*4;[44]
pos += 1;
end while
pl = pos−occurs[key]; // Vielfaches der beiden 2-adischen
// Periodenlängen von x und y
pot = 2**pl;
per = pot−1;
xd = per * 2**(pos−pl); // Nenner von x und y
xn = xp div pot; // Vorperiode von x
xp = xp−xn*pot; // Periode von x
xn = xn*per+xp; // Zähler von x
yn = yp div pot; // Vorperiode von y
yp = yp−yn*pot; // Periode von y
yn = yn*per+yp; // Zähler von y
return (xn,xd, yn,xd);
end function
|
Parameter  |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
|
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
|
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
|
Mehrfachpunkte
Parameter  |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
 |
|
 |
 |
 |
 |
 |
 |
|