Hilbert-Kurve

aus Wikipedia, der freien Enzyklopädie
Wechseln zu: Navigation, Suche
Abb. 1: Das Hilbert-Polygon in sieben Iterationen, als achtes die Hilbert-Kurve

In der Mathematik ist die Hilbert-Kurve eine (stetige) Kurve, die – durch Wiederholung ihres Konstruktionsverfahrens – jedem beliebigen Punkt einer quadratischen Fläche beliebig nahekommt und im Limes die Fläche vollständig ausfüllt. Die Hilbert-Kurve ist eine sogenannte FASS-Kurve, somit eine raumfüllende Kurve. Sie 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 lässt sich durch Rekursion definieren und konstruieren. Die -te Rekursionsstufe wird Hilbert-Polygon der -ten Iteration, , genannt. Dessen euklidische Länge ist , das heißt, sie wächst exponentiell mit . Der Limes hat aufgrund der Eigenschaft, raumfüllend zu sein, eine Hausdorff-Dimension von exakt 2.

Das Hilbert-Polygon (die Hilbert-Kurve) bringt die Punkte im Quadrat in eine lineare Reihenfolge, die Hilbert-Ordnung genannt wird. Mit ihrer Hilfe 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.

Abb. 2: Farbkodierte Entfernungstabelle von Orten auf dem Hilbert-Polygon 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 vorteilhaft ausgenutzt werden können. Dies ist bei mehrdimensionalen 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. Bei der Z-Kurve ist die Rechnung geringfügig einfacher, aber die Nachbarschaftserhaltung deutlich schlechter.

Mit der Entwicklung von Parallelrechnern haben raumfüllende Kurven wie die Hilbert-Kurve eine Anwendungsmöglichkeit erhalten, indem man sie zur Bestimmung der Lastverteilung der einzelnen Prozessoren des Parallelrechners nutzt.

Konstruktionsverfahren[Bearbeiten | Quelltext bearbeiten]

Iterationsschritte[Bearbeiten | Quelltext bearbeiten]

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

beruht auf einem rekursiven Verfahren:

  1. Das zu füllende -dimensionale Gebiet wird aufgeteilt in kongruente Teilgebiete, die die halbe Seitenlänge des („großen“) Ausgangsgebiets besitzen.
  2. 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)
  3. Die Spiegelungs- und Rotationsoperatoren sind so zu wählen, dass sich die Teilkurven zu einer einzigen gerichteten Kurve zusammenfügen.

In diesem Artikel beschränken wir uns vorwiegend auf die Dimensionszahl 2, also auf die Abbildung des Einheitsintervalls auf das Einheitsquadrat .

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

Um dies sicherzustellen, wird als Intervallschachtelung auf der Parameterseite (Eingabeseite) die Darstellung von im Quaternärsystem mit gewählt.[2] Es sei gesetzt, so dass das -te Intervall in der Schachtelung des Parameters

ist. Auf der Seite des Quadrats (Ausgabeseite) werden die Koordinaten und im Binärsystem dargestellt mit . Die Koordinaten mit und stehen dabei für das Teilquadrat, dessen linke untere Ecke (oder auch dessen Mittelpunkt) sie bedeuten, 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 1D-, 2D- und D-Schachtelungen seien als die „Rasterschachtelung“ (der Hilbert-Kurve) bezeichnet.

Die (endliche) -te Rekursionsstufe der Hilbert-Kurve wird Hilbert-Polygon (engl. manchmal Hilbert pseudo curve) der -ten Iteration genannt (Beispiele sind die „Hilbert-Kurven“ der 1. bis 3. Iteration in den obigen Abbildungen). Obwohl eigentlich eine geordnete Folge von Quadraten, wird das Hilbert-Polygon als ein gerichteter Polygonzug von Quadratmittelpunkt zu Quadratmittelpunkt dargestellt mit Anfang, Ende und ohne Berührungen oder Überschneidungen. Alle Hilbert-Polygone derselben Iteration lassen sich durch eine Ähnlichkeitsabbildung ineinander überführen.

Offener Polygonzug[Bearbeiten | Quelltext bearbeiten]

Im Folgenden wird gezeigt, wie die Quadratmittelpunkte eines Rasters in eine Reihenfolge gebracht werden können, derart, dass sie bei wachsendem einander immer näher rücken und im Limes eine Kurve bilden, die das ganze Einheitsquadrat ausfüllt.

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 so in das Quadrat zu holen, dass alle solche Punkte zusammen genommen einen einfach-zusammenhängenden Polygonzug (eine zusammenhängende Folge von Quadraten des Rasters ) und im Limit eine stetige Kurve ergeben. Diese Transformation hat zwei Teile:

  1. die naheliegende Skalierung (um den Faktor ) und Verschiebung und
  2. die etwas kompliziertere Drehung und/oder Spiegelung.

Für die passende Wahl der Drehungen und/oder Spiegelungen ist die Festlegung unerlässlich, 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.[3] Da es auch auf die Richtung ankommt, werde dieses Charakteristikum eines Quadrats im Raster mit dem Begriff „Ausrichtung“ versehen und die Ausrichtung „hoch-rechts-runter“[4] (resp. die Strecke für „Eintritt links unten-Austritt rechts unten“) mit dem Buchstaben gekennzeichnet.

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 wird der Quaternärstelle das Teilquadrat links unten zugewiesen, der dasjenige links oben, der rechts oben und der Quaternärstelle das Teilquadrat rechts unten, also nach dem Muster mit nach rechts und nach oben.[5]

Andere Ausrichtungen (als ) lassen sich durch eine vorgeschaltete Isometrie (Kongruenzabbildung) aus der Diedergruppe des Quadrats leicht bewältigen.

Die zur Herstellung des einfach-zusammenhängenden Polygonzuges (und damit der im Limit stetigen Hilbert-Kurve) 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 Ite-
ration rechts resp. eines seiner Punkte (violett) 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 in den Griff zu bekommen, sei angenommen, dass beide Quadrate, das große (links in der Abbildung 4) wie das Teilquadrat (rechts), gemäß ausgerichtet sind. Andere Ausrichtungen (als ) lassen sich auf beiden Seiten durch vorgeschaltete Kongruenzabbildungen aus leicht beherrschen.

Die benötigten vier Transformationen[6][7] 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 ins (durch , s. o.) spezifizierte Teilquadrat. Zudem ist von einer Transformation je nach Lage ggf. eine Viertelrotation, Spiegelung, d. h. eine Kongruenzabbildung durchzuführen:

  • die Transformation spiegelt bei ihr Argument an der »Hauptdiagonalen« (strichpunktiert in Abbildung 4). Der Eintrittspunkt ins Teilquadrat (links unten) bleibt erhalten.
    (Alle Übertritte von einem Quadrat zum nächsten sind in der Abbildung 6 als kurze blaugrüne Pfeile dargestellt.)
    Der Austrittspunkt dieses Teilquadrats ist nachher links oben und führt zum nächsten Teilquadrat mit .
  • die Zielquadrate bei den Transformationen und haben dieselbe Ausrichtung mit Eintrittspunkt links unten und Austrittspunkt 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 Transformation spiegelt für ihr Argument an der »Nebendiagonalen« (strichpunktiert in Abbildung 4). Danach wird das gespiegelte Ergebnis um in -Richtung, also ins rechte untere Teilquadrat verschoben, so dass der Austrittspunkt (rechts unten) mit dem des Ausgangsquadrates übereinstimmt.

Ersichtlich sind die Quadratmittelpunkte des neuen Rasters in eine Reihenfolge gebracht, die der der zugehörigen -Werte entspricht.

Die Abbildung 4 zeigt ferner, dass ausgehend von der Ausrichtung zwei neue Ausrichtungen („rechts-hoch-links“) und („links-runter-rechts“) hinzukommen, und die Abbildung 6, dass nur noch eine weitere Ausrichtung, genannt , fehlt, so dass es bei insgesamt vier Ausrichtungen bleibt. Die zugehörige Untergruppe der benötigten Isometrien (aus 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.

Da der Übertritt von einem Quadrat zum nachfolgenden Nachbarquadrat immer nur über eine gemeinsame Quadratseite (und nicht diagonal über eine Ecke, s. kurze blaugrüne Pfeile in der Abbildung 6) geschieht, ergeben sich beim Polygonzug ausschließlich Kanten gleicher Länge (der Seitenlänge), 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 .

Der Rekursionsanfang ist in den obigen Abbildungen 1 und 3 zufällig gemäß ausgerichtet. Da die Ausrichtung des Rekursionsanfangs eine besondere Rolle spielt, sei sie als die „primäre Ausrichtung“ bezeichnet. Sind wir sicher, dass das Polygon als Ganzes diese Ausrichtung hat, dann ist die Ausrichtung eines bestimmten Teilquadrats seine „absolute“ Ausrichtung, die Ausrichtung eines Quadrats gegenüber seinem Vorgängerquadrat dagegen eine „relative“, die durch ein Element angegeben werden kann.

Bemerkung

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 die niedrigeren Ranges (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 Abbildung 6 für alle vier vorkommenden Varianten explizit gemacht.

Diskrete Mathematik[Bearbeiten | Quelltext bearbeiten]

Hilbert-Polygon[Bearbeiten | Quelltext bearbeiten]

Die Zuordnung des Hilbert-Polygons der -ten Iteration ist

Das Bild ist (bei endlichem ) eine diskrete Menge, und zwar

mit .

Das oder die entsprechenden Quadratmittelpunkte sind genau die Knotenpunkte des Hilbert-Polygons der -ten Iteration. Die Verbindungsstrecken zwischen diesen Knotenpunkten gehören nicht zum Bild . Dennoch sind sie üblicherweise in den zeichnerischen Darstellungen enthalten, weil sie die wichtige Reihenfolge der Knotenpunkte aufzeigen. Bei Quadratmittelpunkten können mehrere Iterationsstufen in einer Grafik besser auseinander gehalten werden, und kommen Symmetrien deutlicher heraus.

Eingeschränkt auf die Menge ist umkehrbar und hat die Umkehrfunktion , die im Abschnitt Hilbert-Index behandelt wird.

Bild- und Definitionsmenge lassen sich wegen ihrer Diskretheit in einfacher Weise so skalieren, dass sie ganzzahlig werden.

Bei den beiden folgenden Algorithmen t2xyR und t2xyI erfolgt die entscheidende Rechnung (d. i. die Anwendung der vier Transformationen und ) im rekursiven Aufstieg (»auf dem Rückweg«), der von den niedrigrangigen Ziffern der Quaternärdarstellung zu den hochrangigen, geometrisch von einem (kleinen) Quadrat zum es enthaltenden (großen) Quadrat führt. Damit sich überhaupt etwas ergibt, muss der »Hinweg« abgebrochen werden. M. Bader[8] begründet das Abbruchkriterium (im Pseudocode t2xyR formuliert mit der Genauigkeitsvariablen eps) über die abbrechende Quaternärentwicklung, die mit einer unendlichen Ziffernfolge mit dem Periode-04-Ende gleichgesetzt wird. Der Limes des exemplarischen 04-Endes

ist leicht zu bilden, und wird als Berechtigung genommen, die Rekursion in t2xyR vor der -sten Stufe mit dem Rückgabewert abzubrechen. Der dabei entstandene Fehler beträgt auf der Parameterseite maximal eps2 und auf der Koordinatenseite maximal eps.

Es gibt aber eine wesentlich wirkungsmächtigere Überlegung:
Eine Abhängigkeit des -ten Quadrats von Teilen der -sten oder höherer Iterationsstufe existiert ü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 Arbeit im rekursiven Abstieg getan wird. Diese Vorgehensweise hat nebenbei den großen Vorteil, dass die Zahl der Rekursionsschritte – wie bei Rekursionsformeln üblich – offen bleiben kann, ein »Abbruchkriterium« im obigen Sinn also nicht gebraucht wird. (Das Ergebnis liegt nach einem Abbruch unmittelbar vor, sowohl auf der Parameterseite wie auf der Koordinatenseite, – 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 vorgestellt.

Rekursiver Algorithmus[Bearbeiten | Quelltext bearbeiten]

Der nachfolgende rekursive Pseudocode[9] nimmt als Argument einen Parameter t und eine Begrenzung eps der Iterationstiefe. Zurückgegeben wird ein Quadratmittelpunkt.

 function t2xyR(t, eps) begin
   if eps > 1 then
     return(0, 0); // Ergebnis von h(0)
   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

Iterativer Algorithmus mit ganzzahligen Ein-/Ausgabewerten[Bearbeiten | Quelltext bearbeiten]

Bei der folgenden iterativen Lösung ist die Tiefe der Iteration und p ihre „Breite“, eine Zweierpotenz. Zurückgegeben wird ein Quadratmittelpunkt. Der folgende Pseudocode hat ganzzahlige Ein-/Ausgabe (d. h. es wird nicht auf Einheitsintervall oder -quadrat skaliert).

 function t2xyI(t, p) begin
   (x, y) = (0, 0); // Ergebnis von h(0)
   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 wird Gebrauch gemacht von den C-Operatoren ^ für bitweises XOR, & für bitweises UND, += für Inkrementieren, *=2 für Verdoppeln und /=2 für Halbieren.

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.

Hilbert-Index[Bearbeiten | Quelltext bearbeiten]

Die Funktion hat die Bildmenge , die eine diskrete Menge ist. Schränkt man auf die diskrete Menge ein, dann kann man bei ungeänderter Bildmenge die Umkehrfunktion

Abb. 5: Hilbert-Polygon der ersten bis dritten Iteration.
Die Bits im Index (Schrift gedreht) auf gerader Stelle in blau, auf ungerader in rot.
Der Hilbert-Index eines Teilquadrates mit Mittelpunkt findet sich am Schnittpunkt von -Spalte mit -Zeile.
Blass in den Quadratmittelpunkten die „Ausrichtung“. (Alle Zahlen im Binärsystem)

genannt Hilbert-Index, bilden. Sie hat ihrerseits die Bildmenge . Unter den Einschränkungen auf die diskreten Mengen resp. sind die Funktionen wie umkehrbar eindeutig und es gilt und .[10]

Werden ihre Argumente und gleichermaßen als Binärbrüche entwickelt, dann kann man auch beliebige (-stellige) Koordinaten und zulassen, die Einschränkung auf die diskrete Menge aufheben und das ganze Einheitsquadrat zur Definitionsmenge erklären.

Die Definition von ist dann

so dass der Definition vom Anfang des Abschnittes entspricht.

Die Rückabwicklung der Transformationen und ist in den nachfolgenden Algorithmen ausgeführt.

Beide Algorithmen xy2tR[11] und xy2tI arbeiten in Richtung Schachtelung, von einem großen Quadrat zu einem der 4 Teilquadrate. Beide geben den linken Rand des Parameterintervalls zurück.

 function xy2tR(x, y, eps) begin
   if eps > 1 then
     return(0);
   end if
   eps *= 4;
   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(3 + xy2tR(2*x - 1, 2*y - 1, eps) )/4;
     else
       return(2 + xy2tR(1 - 2*y, 2 - 2*x, eps) )/4;
     end if
   end if
 end function

Auch diese Aufgabe lässt sich iterativ programmieren. Die iterative Funktion xy2tI arbeitet wie xy2tR 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 p ihre „Breite“, eine Zweierpotenz.

 function xy2tI(x, y, p) begin
   t = 0; // nur Ausgabe
   for (p /= 2; p > 0; 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

Analysis[Bearbeiten | Quelltext bearbeiten]

Im Limes, also bei , kommt – wie ein Blitz aus heiterem Himmel – ein neues Problem auf, nämlich der plötzliche Verlust der umkehrbaren Eindeutigkeit sowohl bei der 4- als auch bei der 2-adischen Darstellung.

Hilbert-Kurve[Bearbeiten | Quelltext bearbeiten]

Mit den Hilbert-Polygonen lässt sich zu jedem positiven Abstand eine Iterationsstufe angeben, so dass es zu jedem Punkt (oder jeder Punktmenge) des Einheitsquadtrats einen Punkt (oder Punkte) des Polygons gibt, der geringeren Abstand (die geringere Abstände) als hat (haben). Das reicht aber nicht für eine vollständige Füllung des Quadrats. Diese kann nur durch einen Übergang zum Limes erreicht werden. Der Limes

existiert immerhin, da er aus der 2D-Intervallschachtelung

hervorgeht.

Eigenschaften[Bearbeiten | Quelltext bearbeiten]

  1. ist rechtseindeutig, somit wohldefiniert und eine Funktion.
  2. ist surjektiv.
  3. ist nicht injektiv.
  4. ist stetig, definiert also eine Kurve.
  5. Ist die primäre Ausrichtung, dann ist symmetrisch zur Geraden :
          Für jedes ist   und   .
    Bei als primärer Ausrichtung wäre es die Gerade
          und   und   .
  6. ist nirgends differenzierbar.[1][12]
  7. ist Maß-erhaltend: Für jede Punktmenge mit ein-dimensionalem Lebesgue-Maß hat das Bild das -dimensionale Lebesgue-Maß .[13]
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 Viererpotenz im Nenner, also zu einem Element , gibt es zwei Möglichkeiten der Darstellung. Beispielsweise hat der Bruch die Darstellung mit einem Periode-04-Ende

(die als die »abbrechende Darstellung« bezeichnet wird) und die mit einem 34-Ende

.

Diese Wahlmöglichkeit (Gleichheit) ist bei endlicher Stellenzahl nicht gegeben, im Limes aber sehr wohl, wo sie die für die Funktion erforderliche Rechtseindeutigkeit von gefährdet. Es kann aber gezeigt werden, dass sie sich auf das Ergebnis von nicht auswirkt.

  1. Wegen muss gelten:
          .
    In der Tat ist wegen eine 2D-Intervallschachtelung mit dem für alle existierenden Limes .
  2. Für muss wegen (mit als der Ziffer für ) gelten:
          ,
    damit sein kann.
    In der Tat ist wegen eine 2D-Intervallschachtelung mit dem für alle existierenden Limes . Ferner ist
,
und
.

Zu Eigsch. 2:   ist surjektiv.

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 1D-Intervallschachtelungen sind genau dann mehrdeutig, wenn eine der beiden Koordinaten in liegt. Beispielsweise ist

,
(Ein Tripelpunkt)[6] und
(Ein Quadrupelpunkt !)[6]

Jedes Teilquadrat enthält einen Quadrupelpunkt.[6]

Zu einem Punkt gibt es maximal vier Parameter mit .[1]

Zu Bildpunkten mit gibt es nur ein Urbild.

Zu Eigsch. 4:   ist stetig.

ist sogar Hölder-stetig[14] (was die gleichmäßige Stetigkeit[6] 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.[15]

Zu Eigsch. 5:     und   .[6]

Schon für alle gilt aus Symmetriegründen . Genauso . (S. a. den Beweis für denselben Sachverhalt im Abschnitt #Explizite Rekursionsformel.)

Explizite Rekursionsformel[Bearbeiten | Quelltext bearbeiten]

Ist eine Darstellung des Parameters im Quaternärsystem, dann lässt sich die (unendliche) Folge auch als Rekursion[16] über die Quadratmittelpunkte

und die „absolute“ Ausrichtung mit dem Rekursionsanfang

und
und
(Start mit der primären Ausrichtung )[17]

und dem Rekursionsschritt

(RFh_x),
(RFh_y)[18] und
(RFh_a)

für schreiben. Die drei (4×4)-Matrizen

Abb. 6: Die 4 Übersetzungs-
tabellen vom 4-adischen Parameter zu den zwei 2-adischen Koordinaten
– und zurück.
Pro „Ausrichtung“ eine Tabelle.

sind äquivalent zu den vier Übersetzungstabellen der Abbildung 6. Sie werden an erster Stelle, den Zeilen, 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_x und RFh_y) das neue Ziffernpaar für den Punkt und die neue absolute Ausrichtung (Gl. RFh_a).

Erläuterungen zur Abbildung 6  

Die oberste der vier Grafiken der Abb. 6, die für die Ausrichtung , ist ein Extrakt aus der Abb. 4.

Aus der Abb. 5 kann man die Angaben für die zweite (Ausrichtung ) und die vierte (Ausrichtung ) direkt ablesen. Für die dritte (Ausrichtung ) muss man zum 4. Iterationsschritt in der Abb. 5 übergehen.

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. 6 eingehalten.

Die vier Grafiken unterscheiden sich hinsichtlich des Charakteristikums Ausrichtung durch eine der Isometrien aus der Untergruppe .

Bemerkung

Die Abbildung zeigt (bei jeder der vier Ausrichtungen) nur einen einzigen Rekursionsschritt. Das Zusammenfassen mehrerer Rekursionsschritte, 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 – und vergrößert die Grafiken wie die von ihnen abgeleiteten Matrizen entsprechend. Es bleibt aber bei der Anzahl vier hinsichtlich der Übersetzungstabellen, die der Elementeanzahl der Untergruppe entspricht. Das Verfahren bezeichnet M. Bader[19] als recursion unrolling (dt. etwa Ab/Entrollen der Schleife). Es kann die Algorithmen wesentlich beschleunigen, weil weniger Programmaufrufe und Schleifenkontrollanweisungen durchlaufen werden müssen.

Die Folge der Quadratmittelpunkte mit und , steht für die 2D-Intervallschachtelung

auf Seiten der Quadrate, mit der die Lage des Punktes bis zum beliebig scharf eingegrenzt wird.

Beweis der Rekursionsformel  
  • Mit den (Gl.n RFh_x und RFh_y) wird der neue Punkt entsprechend der absoluten Ausrichtung des großen Quadrats (4 ganz große Buchstaben in der Abb. 6) auf das Viertelquadrat mit der Quaternärziffer eingegrenzt. Dort geht die 2D-Intervallschachtelung weiter. Die relative Ausrichtung zwischen Viertelquadrat und großem Quadrat entspricht (einschließlich der Transformationen und ) den Regeln des Abschnitts #Transformation der rekursiven Teilquadrate auf das Einheitsquadrat. Die im abhängig von auszuwählenden Teilquadrat eingetragenen Ziffern verlängern die zwei Binärdarstellungen und der Koordination um jeweils eine Stelle.
    Die (Gl. RFh_a) akkumuliert die relativen Ausrichtungen[20] und implementiert damit die relative Ausrichtung zwischen und des Abschnitts #Transformation der rekursiven Teilquadrate auf das Einheitsquadrat. Sie ist gleichbedeutend mit der Formel
    für
    für
    für
    für ,

    in der zum Rechnen gesetzt ist. Das bedeutet, dass die Abhängigkeit der -ten Ausrichtung von konzentriert werden kann auf

    1. die -te Ausrichtung und
    2. die -te Quaternärziffer von

    und dass es keine umgekehrte Abhängigkeit gibt, also dass von abhinge, wie man fälschlicherweise aus der Herleitung in Abschnitt #Transformation der rekursiven Teilquadrate auf das Einheitsquadrat schließen könnte.

    Des Weiteren sind die 4 dortigen Transformationen bis in den 4 Tabellen völlig aufgegangen.[21]

  • Für alle ist
    mit mit . Denn es ist und . Der Induktionsschritt ergibt und das Nachschauen der viermal vier Fälle mit in der Matrix ergibt die Behauptung.
    Analog ist
    und
    .
  • Symmetrieeigenschaft: Für jedes ist   und   .
    Induktionsanfang:   und   .
    Induktionsschritt:

Einige Zahlenbeispiele[Bearbeiten | Quelltext bearbeiten]

Parameter
Mehrfachpunkte
Parameter

[6]

Umkehrfunktion[Bearbeiten | Quelltext bearbeiten]

Erstens ist festzuhalten, dass wegen der fehlenden Injektivität nicht umkehrbar ist.

Obwohl die Einschränkung für jedes invertierbar ist, existiert zweitens der Limes

mit nicht, wenn eine der beiden Koordinaten oder eine abbrechende Binärdarstellung hat, also in liegt. Nach der im beim Beweis der Nicht-Injektivität von gemachten Bemerkung sind dies dieselben Stellen, zu denen es mehr als ein Urbild gibt.

Sie können eindeutig gemacht werden durch die Vorschrift, dass die betreffende(n) Koordinate(n) resp. , wenn sie bei irgendeinem Rekursionsschritt genau auf die Mitte eines Intervalls fallen, stets der rechten (oberen) Intervallhälfte zugeschlagen werden (Vorschrift „+“, und damit als 02-Ende behandelt werden) – oder der linken (unteren) Intervallhälfte (Vorschrift „–“, und somit als 32-Ende). Es gibt also (mindestens) vier verschiedene Funktionen

  1. ,
  2. ,
  3. und
  4. ,

die sich an Stellen unterscheiden, wo eine der beiden Koordinaten in liegt. An diesen Stellen sind die Funktionen auch nicht stetig.

[22]

Eigenschaften[Bearbeiten | Quelltext bearbeiten]

  1. Alle sind Funktionen.
  2. Ist für ein Paar , dann ist .
  3. Zu einem Punkt gibt es maximal 4 verschiedene Parameterwerte mit .[1]
  4. Alle Funktionen sind injektiv.
  5. Ist , dann ist .
  6. Keine Funktion ist surjektiv.
  7. Keine Funktion ist stetig.
Beweise der Eigenschaften  
Zu Eigsch. 1:   ist eine Funktion.

Man übersetze den obigen rekursiven Algorithmus xy2tR in eine (unendliche) Rekursionsformel, entferne also eps und die Abfragen darauf aus dem Rekursionsschema. Die Abfragen auf die Intervallmitte führen zu einem Ergebnis, das gegen konvergiert.

Zu Eigsch. 2:   Ist , dann ist .

Ist eine Darstellung des Parameters im Quaternärsystem, dann lässt sich die Folge

mit bilden, die die einzige ist mit . Sie hat den Grenzwert

.
Zu Eigsch. 3:   Es gibt maximal 4 Punkte mit .

Ist , dann gibt es ein Paar mit .

Zu Eigsch. 4:   ist injektiv.

Ist , dann ist .

Zu Eigsch. 5:   Die Punkte mit

haben nur ein Urbild .

Zu Eigsch. 6:   Kein ist surjektiv.

Beim Quadrupelpunkt ist

,
,
und
.

Zu , bspw. , gibt es keinen Punkt mit .

Denn wäre , dann wäre nach Eigsch. 2   . Da nun , würde folgen. Es ist aber und nicht . Es geht also nicht!
Entsprechendes gilt für die anderen .

Zu Eigsch. 7:   ist nicht stetig.

An den Mehrfachpunkten unterscheiden sich die Funktionen , d. h. linksseitige und rechtsseitige Grenzwerte. Also ist keine der Funktionen dort stetig.

Rekursionsformel für die Umkehrfunktion[Bearbeiten | Quelltext bearbeiten]

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 primären Ausrichtung )

und dem Rekursionsschritt

(RFk_) und
(RFk_b)

für schreiben. Die (4×2×2)-Tensoren

sind zusammen genommen äquivalent zu den vier Übersetzungstabellen der Abbildung 6. Sie werden an erster Stelle, den Zeilen, durch die absolute Ausrichtung indiziert. Das Ergebnis ist bei wie bei eine (2×2)-Untermatrix, die zusammen eine der Übersetzungstabellen darstellen. Jede wird ihrerseits durch das Binärziffernpaar indiziert. Daraus resultiert (Gl. RFk_) die neue Quaternärziffer für den Parameter und die neue absolute Ausrichtung (Gl. RFk_b).

Ist eine der Koordinaten , dann lässt sich durch entsprechende Wahl ihrer Binärdarstellung steuern, ob der links- oder der rechtsseitige Limes genommen werden soll.

Beweis der Rekursionsformel für die Umkehrfunktion  

Das kleine Quadrat (rechts in der Abb. 4) bekommt gemäß (Gl. RFk_) im großen Quadrat eine Nummer , die seiner (absoluten) Ausrichtung und seiner Lage im großen Quadrat, den Ziffern , entspricht. Erstere legt fest, welche der 4 Übersetzungstabellen in Abb. 6 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_b), die die absolute Ausrichtung rekursiv festlegt, ist eine Akkumulation[23] der relativen Ausrichtungen, die durch jene Transformationen bewirkt werden.

Einige Zahlenwerte[Bearbeiten | Quelltext bearbeiten]

Punkt
Parameter
Mehrfachpunkte
Punkt
Parameter

Zahlentheorie[Bearbeiten | Quelltext bearbeiten]

Parameter
  1. .
  2. Ist ein abbrechender Quaternärbruch, so ist .
  3. Ist ein gekürzter Bruch mit einer quaternären Periodenlänge , also , so sind die Koordinaten von beide rational mit einer binären Periodenlänge , also mit als dem Gruppenexponenten der Untergruppe .[24]
  4. Sind die Koordinaten rational mit den beziehentlichen binären Periodenlängen , dann ist mit .[24]
Beweise der zahlentheorischen Eigenschaften  
Zu Eigsch. 1:   .
Zu Eigsch. 2:   Ist , so ist .
Zu Eigsch. 3:   .

Sei eine Periode der Länge , dann ist eine ganze Zahl.

Nach der expliziten Rekursionsformel hängt ein neues Ziffernpaar nur von ab. Wegen gibt es von diesen Konstellationen maximal Stück, so dass sie wiederkehren müssen. Kehrt eine Konstellation (ihre Nummer sei ) zum ersten Mal (etwa bei der Nummer ) wieder, liegt eine schon mal dagewesene Ursache vor, so dass sich die Wirkungen, die Ziffern und genauso , wiederholen müssen, nämlich alle mal, und ist ein Teiler von . Daraus folgt für geeignetes sowohl wie , also .

Zu Eigsch. 4:   .

Die Argumentation ist analog zu der von Eigsch. 3.

Darstellung als Lindenmayer-System[Bearbeiten | Quelltext bearbeiten]

Abb. 7: Hilbert-Polygon der 6. Iteration

Die Hilbert-Kurve kann als Termersetzungssystem (Lindenmayer-System) formuliert werden.[25]

Variablen: A, B, C, D
Terminale: ↑, →, ↓, ←
      (blaugrüne Pfeile in der Abb. 6)
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.

Die Abbildung 7 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.

Erweiterungen[Bearbeiten | Quelltext bearbeiten]

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.[13][26][27] Somit ist es möglich, mit einer stetigen eindimensionalen Kurve, einen z.B. dreidimensionalen Raum vollständig abzudecken. Die Faltung des Genoms ähnelt einer dreidimensionalen Hilbert-Kurve.[28]

Moore-Kurve[Bearbeiten | Quelltext bearbeiten]

Abb. 8: 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 findet sich am Schnittpunkt von -Spalte mit -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.[29]

Die Hilbert-Kurve nach Moore, kurz: die Moore-Kurve (engl. Moore curve) ist eine geschlossene Form der Hilbert-Kurve. Sie ist genauso raumfüllend und hat sehr ähnliche Nachbarschaftseigenschaften wie die Hilbert-Kurve.

Einzelnachweise[Bearbeiten | Quelltext bearbeiten]

  1. a b c d #Hilbert
  2. 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 (2 oder 4) als Präfix bei diesem Punkt.
    Wie üblich bedeutet bei einer b-adischen Entwicklung ein Strich über den letzten Ziffern eine unendliche Wiederholung dieser Zifferngruppe, eine Periode.
  3. 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.
  4. Michael Bader: Space-Filling Curves. An Introduction with Applications in Scientific Computing (= Timothy J. Barth, Michael Griebel, David E. Keyes, Risto M. Nieminen, Dirk Roose, Tamar Schlick [Hrsg.]: Texts in Computational Science and Engineering. Band 9). 1. Auflage. Springer-Verlag, 2013, ISBN 978-3-642-31045-4, ISSN 1611-0994, doi:10.1007/978-3-642-31046-1 (englisch, 278 S.). S. 31.
  5. Im Gegensatz dazu hat die nicht-stetige Z-Kurve die parallele Ordnung , bei der die Winkel (0,1,2) und (1,2,3) beliebig spitz werden können.
  6. a b c d e f g #Rose
  7. Michael Bader: Space-Filling Curves. An Introduction with Applications in Scientific Computing (= Timothy J. Barth, Michael Griebel, David E. Keyes, Risto M. Nieminen, Dirk Roose, Tamar Schlick [Hrsg.]: Texts in Computational Science and Engineering. Band 9). 1. Auflage. Springer-Verlag, 2013, ISBN 978-3-642-31045-4, ISSN 1611-0994, doi:10.1007/978-3-642-31046-1 (englisch, 278 S.). S. 49.
  8. Michael Bader: Space-Filling Curves. An Introduction with Applications in Scientific Computing (= Timothy J. Barth, Michael Griebel, David E. Keyes, Risto M. Nieminen, Dirk Roose, Tamar Schlick [Hrsg.]: Texts in Computational Science and Engineering. Band 9). 1. Auflage. Springer-Verlag, 2013, ISBN 978-3-642-31045-4, ISSN 1611-0994, doi:10.1007/978-3-642-31046-1 (englisch, 278 S.). S. 50.
  9. Michael Bader: Space-Filling Curves. An Introduction with Applications in Scientific Computing (= Timothy J. Barth, Michael Griebel, David E. Keyes, Risto M. Nieminen, Dirk Roose, Tamar Schlick [Hrsg.]: Texts in Computational Science and Engineering. Band 9). 1. Auflage. Springer-Verlag, 2013, ISBN 978-3-642-31045-4, ISSN 1611-0994, doi:10.1007/978-3-642-31046-1 (englisch, 278 S.). S. 52f.
  10. Das ist leicht zu erkennen, weil in beiden Richtungen bei jedem Rekursionsschritt es genau vier Folgequadrate gibt, die das Ausgangsquadrat ausfüllen, und keines weniger.
  11. Michael Bader: Space-Filling Curves. An Introduction with Applications in Scientific Computing (= Timothy J. Barth, Michael Griebel, David E. Keyes, Risto M. Nieminen, Dirk Roose, Tamar Schlick [Hrsg.]: Texts in Computational Science and Engineering. Band 9). 1. Auflage. Springer-Verlag, 2013, ISBN 978-3-642-31045-4, ISSN 1611-0994, doi:10.1007/978-3-642-31046-1 (englisch, 278 S.). S. 58.
  12. #Sagan
  13. a b #Haverkort
  14. Michael Bader: Space-Filling Curves. An Introduction with Applications in Scientific Computing (= Timothy J. Barth, Michael Griebel, David E. Keyes, Risto M. Nieminen, Dirk Roose, Tamar Schlick [Hrsg.]: Texts in Computational Science and Engineering. Band 9). 1. Auflage. Springer-Verlag, 2013, ISBN 978-3-642-31045-4, ISSN 1611-0994, doi:10.1007/978-3-642-31046-1 (englisch, 278 S.). S. 167f.
  15. Bemerkung zur einfachen Stetigkeit: Die beiden Möglichkeiten der Intervallschachtelungen (der Quaternärbruchdarstellungen) liefern so etwas wie einen linksseitigen und einen rechtsseitigen Grenzwert für an der Stelle . Die Stetigkeit von stellt sicher, dass diese beiden Grenzwerte gleich sind.
  16. T. 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 Michael Bader: Space-Filling Curves. An Introduction with Applications in Scientific Computing (= Timothy J. Barth, Michael Griebel, David E. Keyes, Risto M. Nieminen, Dirk Roose, Tamar Schlick [Hrsg.]: Texts in Computational Science and Engineering. Band 9). 1. Auflage. Springer-Verlag, 2013, ISBN 978-3-642-31045-4, ISSN 1611-0994, doi:10.1007/978-3-642-31046-1 (englisch, 278 S.). S. 63.)
  17. mit als Symmetrieachse. In der Literatur findet sich auch die Symmetrieachse , wohin man mit als primärer Ausrichtung kommt.
  18. Mit nur an Stelle von erhält man die linken unteren Ecken der Quadrate.
  19. Michael Bader: Space-Filling Curves. An Introduction with Applications in Scientific Computing (= Timothy J. Barth, Michael Griebel, David E. Keyes, Risto M. Nieminen, Dirk Roose, Tamar Schlick [Hrsg.]: Texts in Computational Science and Engineering. Band 9). 1. Auflage. Springer-Verlag, 2013, ISBN 978-3-642-31045-4, ISSN 1611-0994, doi:10.1007/978-3-642-31046-1 (englisch, 278 S.). S. 60.
  20. Michael Bader: Space-Filling Curves. An Introduction with Applications in Scientific Computing (= Timothy J. Barth, Michael Griebel, David E. Keyes, Risto M. Nieminen, Dirk Roose, Tamar Schlick [Hrsg.]: Texts in Computational Science and Engineering. Band 9). 1. Auflage. Springer-Verlag, 2013, ISBN 978-3-642-31045-4, ISSN 1611-0994, doi:10.1007/978-3-642-31046-1 (englisch, 278 S.). S. 63.
  21. Es gibt in der -ten Iteration Teilquadrate der Ausrichtung , Teilquadrate der Ausrichtungen und und Teilquadrate der Ausrichtung .
  22. Es sind aber noch andere Funktionsvorschriften für die Umkehrfunktion denkbar. Zum Beispiel folgende:
    Ist ein Punkt, bei dem im Laufe der -ten Iteration bspw. die Koordinate 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 die restlichen Ziffern (mit ) als 102-Ende oder eben als 012-Ende aufgefasst werden. Das Ergebnis an diesem Punkt entspricht sicherlich einem für ein Paar , ohne mit ihm an anderen Punkten übereinstimmen zu müssen.
  23. Michael Bader: Space-Filling Curves. An Introduction with Applications in Scientific Computing (= Timothy J. Barth, Michael Griebel, David E. Keyes, Risto M. Nieminen, Dirk Roose, Tamar Schlick [Hrsg.]: Texts in Computational Science and Engineering. Band 9). 1. Auflage. Springer-Verlag, 2013, ISBN 978-3-642-31045-4, ISSN 1611-0994, doi:10.1007/978-3-642-31046-1 (englisch, 278 S.). S. 63.
  24. a b #Wunderlich
  25. Michael Bader: Space-Filling Curves. An Introduction with Applications in Scientific Computing (= Timothy J. Barth, Michael Griebel, David E. Keyes, Risto M. Nieminen, Dirk Roose, Tamar Schlick [Hrsg.]: Texts in Computational Science and Engineering. Band 9). 1. Auflage. Springer-Verlag, 2013, ISBN 978-3-642-31045-4, ISSN 1611-0994, doi:10.1007/978-3-642-31046-1 (englisch, 278 S.). S. 32.
  26. Michael Trott: The Mathematica GuideBook for Programming. Springer 2004. (2.3.9 Hilbert Curves in Higher Dimensions, S. 93–97)
  27. Arthur Butz, Alternative algorithm for Hilbert’s space filling curve, IEEE Trans. On Computers, vol. 20,‎ April 1971, S. 424-442.
  28. Brandon Keim: The Human Genome in 3 Dimensions. Wired, 10. August 2009, abgerufen am 28. August 2013 (englisch).
  29. Michael Bader: Space-Filling Curves. An Introduction with Applications in Scientific Computing (= Timothy J. Barth, Michael Griebel, David E. Keyes, Risto M. Nieminen, Dirk Roose, Tamar Schlick [Hrsg.]: Texts in Computational Science and Engineering. Band 9). 1. Auflage. Springer-Verlag, 2013, ISBN 978-3-642-31045-4, ISSN 1611-0994, doi:10.1007/978-3-642-31046-1 (englisch, 278 S.). S. 26.

Literatur[Bearbeiten | Quelltext bearbeiten]

Weblinks[Bearbeiten | Quelltext bearbeiten]

 Commons: Hilbert-Kurve – Album mit Bildern, Videos und Audiodateien

Siehe auch[Bearbeiten | Quelltext bearbeiten]