Z-Kurve

Iterationen 1, 2, 3 und 4 der Z-Kurve

Die Z-Kurve (Lebesgue-Kurve, Vorlage:EnS) ist eine Abbildung, die Punkte aus dem mehrdimensionalen Raum in eine lineare Ordnung, die Z-Ordnung oder Morton-Ordnung, bringt, eine Ordnung mit nachbarschaftserhaltenden Eigenschaften: Wenn zwei Raumpunkte im Mehrdimensionalen nah beisammen liegen, liegen mit hoher Wahrscheinlichkeit auch ihre Z-Werte nah beisammen. Der Z-Wert eines Raumpunktes wird durch bitweises Verschränken der binären Koordinatenwerte berechnet.

Mit Hilfe der Z-Ordnung lassen sich (effiziente) Verfahren, die auf einer linearen Ordnung beruhen, ins Mehrdimensionale übertragen. Dazu gehört Binäres Suchen, Binärer Suchbaum, Skip-Liste, B-Baum, oder ein B⁺-Baum.

Für eine effiziente mehrdimensionale Bereichssuche ist ein Algorithmus erforderlich, um, ausgehend von einem in der Datenstruktur außerhalb des Suchbereichs angetroffenen Punkt, den nächstmöglichen Z-Wert im Suchbereich zu bestimmen (BIGMIN/LITMAX)

Die Z-Ordnung ist beliebt aufgrund ihrer guten Nachbarschaftserhaltung und der einfachen Berechenbarkeit der Z-Werte. Bei der Hilbert-Kurve ist die Nachbarschaftserhaltung besser, doch sind die Rechnungen komplizierter.

Anwendungen finden sich bei der Nachbarschaftssuche in Datenbanken, bei diversen technischen Anwendungen, sowie – zur besseren Nutzung der Speicherhierarchie – in der linearen Algebra.

Zahlentheorie

Z-Kurve (grau) der dritten Iteration
x-Bits blau, y-Bits rot

Die nebenstehende Abbildung zeigt die Z-Werte im zweidimensionalen Fall für ganzzahlige Koordinaten $0\le x\le 7,0\le y\le 7$. Das bitweise Verschränken der Vorlage:Nowrap und Vorlage:Nowrap (auch bitweises Verzahnen oder Binärbruchpressung genannt) ergibt die binären Vorlage:Nowrap Verbindet man diese in ihrer aufsteigenden numerischen Reihenfolge, dann entsteht eine Kurve (Polygonzug), die Z-Kurve genannt wird. Die zugrunde liegende Abbildung sei in ihrer Vorlage:Nowrap Iteration durch

$\begin{array}{ccc}{M}_n:& (\{0,1,\dots ,2^n-1\}\cdot 2^{-n}{)}^2& \to \{0,1,\dots ,4^n-1\}\cdot 4^{-n}\\ & (\sum _{i=1}^n{z}_{2i-1}{2}^{-i},\sum _{i=1}^n{z}_{2i}{2}^{-i})& \mapsto \sum _{i=1}^{2n}{z}_i{2}^{-i}\end{array}$

spezifiziert. Sie lässt sich leicht auf höhere Dimensionen erweitern und ist umkehrbar eindeutig (bijektiv).

In den binären Darstellungen der Z-Werte $M_n(x,0)$ für $y=0$ gibt es 1-Bits höchstens an Binärstellen mit geradem Index. Im System zur Basis 4 bestehen diese Zahlen also nur aus Ziffern 0 und Vorlage:Nowrap Diese Zahlen heißen Z-Werte im engeren Sinn oder Moser-de Bruijn-Zahlen. Sie machen die Vorlage:OEIS aus.

Fürs Folgende sei diese Folge angegeben als

$z[]=\{0_2,1_2,100_2,101_2,10000_2,10001_2,10100_2,10101_2,\dots \}$ ,

wobei der ersten Komponente der Index 0 gegeben wird. Summen und Differenzen zweier Vorlage:Nowrap lassen sich bilden durch die bitweisen Operationen

$z[i+j]=((z[i]\vee {\overline{10}}_2)+z[j])\wedge {\overline{01}}_2$ und

$z[i-j]=((z[i]\wedge {\overline{01}}_2)-z[j])\wedge {\overline{01}}_2$ falls $i\ge j$ ,

mit ${\overline{01}}_2:=\dots \overline{01}0101_2$ und mit den Operatoren $\wedge$ für bitweises logisches UND und $\vee$ für bitweises logisches ODER, jeweils angewendet auf die in Bitketten aufgelösten Operanden.

Eine Formel zum Erzeugen des Folgeelements $z[i+1]$ aus dem Vorgänger $z[i]$ ist

$z[i+1]:=((z[i]\vee {\overline{10}}_2)+1)\wedge {\overline{01}}_2$.

Anwendungen in der Informatik

Nachbarschaftssuche

Rechteckiger Suchbereich

Durch Bitverschränken werden die Datenbankeinträge in eine (möglicherweise sehr lange) Folge von Bits umgewandelt. Die Bitfolgen werden als Binärzahlen interpretiert, und die Datenbankeinträge werden nach den Binärwerten sortiert oder indiziert, wobei eine beliebige eindimensionale Datenstruktur verwendet wird, wie in der Einleitung erwähnt. Jedoch ist bei der Abfrage eines mehrdimensionalen Suchbereichs in diesen Daten eine binäre Suche nicht wirklich effizient. Trotz der guten Nachbarschaftserhaltung ist für die mehrdimensionale Bereichssuche ein Algorithmus erforderlich, um, ausgehend von einem in der Datenstruktur außerhalb des Suchbereichs angetroffenen Punkt, den nächstmöglichen Z-Wert zu bestimmen, dessen Koordinaten im Suchbereich liegen.

Im Beispiel der nebenstehenden Abbildung ist der Suchbereich (x=2..3, y=2..6), ein 2D-Intervall, als gestricheltes Rechteck angezeigt. Der höchste Z-Wert darin ist MAX=45. Angenommen, im Laufe der Suche wird der Wert F=19 angetroffen, bei Suche nach steigenden Werten. Das 1D-Intervall zwischen F und MAX (schraffiertes Gebiet) ist Obermenge des noch zu durchsuchenden Teils des Rechtecks. Um die Suche zu beschleunigen, wird der nächstmögliche Z-Wert im Suchbereich berechnet, im Folgenden BIGMIN genannt (36 im Beispiel). Dann muss nur das Intervall zwischen BIGMIN und MAX durchsucht werden (fett gezeichnete Werte), dadurch wird der Großteil des schraffierten Gebiets übersprungen. Die Suche nach fallenden Werten ist analog dazu, mit LITMAX, dem größten Z-Wert im Suchbereich, der kleiner ist als F. Das Problem und seine Lösung wurde zuerst im Jahr 1981 von Tropf und Herzog beschrieben. Zur Entwicklungsgeschichte nach der Veröffentlichung siehe

Die Methode wurde später auch in UB-Bäumen verwendet.

Indem man die Methode hierarchisch (entsprechend der verwendeten Datenstruktur) einsetzt, ggf. nach sowohl steigenden als auch fallenden Z-Werten, erhält man eine hocheffiziente mehrdimensionale Bereichssuche; dies ist nützlich sowohl in kommerziellen als auch technischen Anwendungen, z. B. als Grundfunktion für (Nächste-)Nachbarschaftssuchen.

Eine ausführliche Erläuterung des LITMAX/BIGMIN-Berechnungsalgorithmus, zusammen mit Pascal-Quellcode (3D, leicht an nD anzupassen) und Hinweisen zum Umgang mit Fließkommadaten und möglicherweise negativen Daten, wird bereitgestellt 2021 von Tropf. Hier wird die Bitverschränkung nicht explizit durchgeführt; die Datenstruktur hat nur Zeiger auf die ursprünglichen (unsortierten) Datensätze. Mit einer allgemeinen Datensatz-Vergleichsfunktion (größer-kleiner-gleich, im Sinne des Z-Wertes) werden Komplikationen mit Bitfolgen vermieden, deren Länge die Computerwortlänge übersteigt, und der Code kann leicht an eine beliebige Anzahl von Dimensionen und jede Datensatz-Schlüsselwortlänge angepasst werden.

Die Methode wird verwendet in diversen technischen Anwendungen unterschiedlicher Bereiche und in Datenbanksystemen und ist eine der wenigen mehrdimensionalen Zugriffsmethoden, die Eingang in kommerzielle Datenbanken gefunden haben.

Der Ansatz hängt nicht von der gewählten eindimensionalen Datenstruktur ab. Die freie Wahl der Struktur macht es einfacher, die Methode in bestehende Datenbanken zu integrieren. Dies steht im Gegensatz beispielsweise zu R-Bäumen, bei denen besondere Vorkehrungen erforderlich sind. So können z. B. für dynamische Daten fallbewährte, balancierte Strukturen verwendet werden, bei denen die Beibehaltung des Baumgleichgewichts beim Einfügen oder Löschen O(log n) Zeit benötigt.

Nutzung der Speicherhierarchie

Moderne Mikroprozessoren bieten eine umfangreiche Speicherhierarchie. Auf hoher Ebene sind die Speicher schnell und ausschließlich einem einzelnen Kern zugewiesen, aber klein. Wenn der Datenzugriff eine hohe Lokalität aufweist, können übermäßige Datenübertragungen zwischen den verschiedenen Ebenen der Speicherhierarchie vermieden werden.

So können Matrizen in der linearen Algebra auch anhand von einer raumfüllenden Kurve durchwandert werden. Herkömmliche Schleifen durchwandern eine Matrix zeilenweise. Das Durchwandern mit der Z-Kurve ermöglicht einen effizienten Zugriff auf den Speicher.

Analysis

Binärbruchverschränkung

Bemerkung zur Notation

Um Undeutlichkeiten oder Verwechslungen mit dem Komma der Notationen für Intervalle oder Koordinatenpaare zu vermeiden, wird im Folgenden als Trennzeichen zu den Stellen mit negativen Exponenten der Punkt verwendet. Wir folgen diesbezüglich M. Bader wie auch in der Platzierung der Basis als Präfix bei diesem Punkt.

Ferner verwenden wir zur Kennzeichnung offener reeller Intervalle die umgekehrten eckigen Klammern $]0,1[,$ da die runden zur Kennzeichnung der Vorlage:Nowrap benötigt werden.

Die durch unendliche Iteration der obigen Vorschrift $M_n$ „definierte“ und auf das Einheitsintervall normalisierte Abbildung

$\begin{array}{cccccc}M:& [0,1[& \times & [0,1[& \to & [0,1[\\ & (\sum _{i=1}^{\mathrm{\infty }}{z}_{2i-1}{2}^{-i}& ,& \sum _{i=1}^{\mathrm{\infty }}{z}_{2i}{2}^{-i})& \mapsto & \sum _{i=1}^{\mathrm{\infty }}{z}_i{2}^{-i}\\ & & & & =& \underset{n\to \mathrm{\infty }}{\lim }{M}_n(\sum _{i=1}^n{z}_{2i-1}{2}^{-i},\sum _{i=1}^n{z}_{2i}{2}^{-i})\end{array}$

mit Ziffern $z_i\in \{0,1\}$ ist zunächst nicht wohldefiniert, weil es zu einem gekürzten Bruch mit Zweierpotenz im Nenner, also zu einem Element

$x\in E:=\mathbb{N}{2}^{-\mathbb{N}}\cap ]0,1[$

mit abbrechender Binärdarstellung, zwei Möglichkeiten der Darstellung gibt.

Beispielsweise hat der Bruch $x=\frac{1}{2}$ die Darstellung mit einem Vorlage:Nowrap

$\frac{1}{2}=1\cdot 2^{-1}+\sum _{i=2}^{\mathrm{\infty }}0\cdot 2^{-i}=0_2.1\bar{0}$

und die mit einem Vorlage:Nowrap

$\frac{1}{2}=0\cdot 2^{-1}+\sum _{i=2}^{\mathrm{\infty }}1\cdot 2^{-i}=0_2.0\bar{1}$ .

Diese Wahlmöglichkeit (Gleichheit) ist bei endlichem $n$ nicht gegeben, im Limes $\underset{n\to \mathrm{\infty }}{\lim }$ aber sehr wohl, wo sie die für die Funktion $M$ erforderliche Rechtseindeutigkeit verletzt, da sie sich auf das Ergebnis der Verschränkung auswirkt. Die Rechtseindeutigkeit lässt sich aber, beispielsweise durch eine der folgenden Vorschriften, herstellen:

Vorschrift ↓:

Die Binärdarstellung eines Bruchs $w\in E$ hat immer ein Vorlage:Nowrap Das entspricht der üblichen abbrechenden Darstellung und einer Annäherung an $w$ von oben her. Diese Variante von $M$ sei mit $M_{\downarrow }$ bezeichnet.

Vorschrift ↑:

Die Binärdarstellung von 0 ist immer Vorlage:Oberstrich2. Der Binärdarstellung eines (abbrechenden) Bruchs $w\in E$ wird immer mit einem Vorlage:Nowrap ausgestattet. (Ist bspw. $k:=\min \{k\mid w\cdot 2^k\in \mathbb{Z}\}$ die Zahl der Binärstellen rechts vom Binärpunkt, dann ist die zum Index $k$ gehörige Binärziffer $z_k=1$ und die Binärdarstellung $w=2^{-k}\cdot (w\cdot 2^k-1+{\sum }_{i=1}^{\mathrm{\infty }}{2}^{-i})$ zu nehmen.) Das entspricht einer Annäherung an $w$ von unten her, also einer linksseitigen Grenzwertbildung bei jeder Funktion, bei der es auf die Binärdarstellung ankommt, beispielsweise einem Limes $\underset{n\to \mathrm{\infty }}{\lim }M(x-2^{-n},y-2^{-n})$. Diese Variante von $M$ sei mit $M_{\uparrow }$ bezeichnet.

Durch jede der beiden Vorschriften wird $M$ wohldefiniert und ist auch injektiv.

$M$ ist aber nicht surjektiv. Vorlage:AnkerDenn bei beiden Vorschriften gibt es bspw. zu Brüchen wie $z=0_2.01\overline{10}=0_4.1\bar{2}=\frac{5}{12}\in [0,1[$ kein Urbild, da hierfür die Vorlage:Nowrap zwingend ein Vorlage:Nowrap und die Vorlage:Nowrap zwingend ein Vorlage:Nowrap haben müsste (resp. umgekehrt bei Vorlage:Nowrap.) Das Bild des Einheitsquadrates ist jeweils

$M_{\downarrow }([0,1{[}^2)=[0,1[\setminus (\mathbb{N}{2}^{-\mathbb{N}}+\{-\frac{1}{3},\frac{1}{3}\})$	bei Vorschrift ↓ resp.
$M_{\uparrow }([0,1{[}^2)=([0,1[\setminus (\mathbb{N}{2}^{-\mathbb{N}}+\{-\frac{1}{3},\frac{1}{3}\}))\cup (\frac{1}{3}\cdot 2^{-\mathbb{N}})$	bei Vorschrift ↑.

Ihm fehlt in beiden Fällen zum Einheitsintervall eine abzählbare dichte Teilmenge. Somit ist es nicht kompakt. (Gleichwohl ist die abgeschlossene Hülle beider Bilder das abgeschlossene Intervall Vorlage:Nowrap

Weder $M_{\downarrow }$ noch $M_{\uparrow }$ ist stetig, da an den Punkten $\in E$ eine infinitesimale Änderung des Arguments eine endliche Änderung des Funktionswerts bewirkt. Das kann man schon in der obigen Abbildung „dritte Iteration“ erkennen, beispielsweise am Einserschritt der Vorlage:Nowrap von $(000_2,011_2)\mapsto 001010_2=10_{\mathrm{d}\mathrm{e}\mathrm{z}}$ zu $(000_2,100_2)\mapsto 100000_2=32$ oder am Einserschritt der Vorlage:Nowrap von Punkt $(011_2,000_2)\mapsto 000101_2=5$ zu Punkt $(100_2,0)\mapsto 010000_2=16$, wo die Positionsnummer in der Z-Kurve um mehr als ein Drittel (32−10=22 > 64/3) resp. um mehr als ein Sechstel (16−5=11 > 64/6) ihrer Gesamtlänge (64) zunimmt.

Genaue Überlegung

Enthält die Binärdarstellung einer Zahl $\in [0,1[$ keine 1, dann handelt es sich um die 0, und es gibt keine Wahlmöglichkeit, diese mit einem Vorlage:Nowrap so darzustellen, dass derselbe Zahlenwert 0 herauskommt. Für die Untersuchung der Stetigkeit an einem Punkt $(x,y)\in ]0,1{[}^2$ kann man die koordinatenweisen Differenzen der einseitigen Grenzwerte heranziehen. Denn genau dann, wenn beide Differenzen 0 sind, ist die Funktion am Punkt $(x,y)$ stetig. Ist weder $x$ noch $y$ ein abbrechender Binärbruch, dann stimmen die einseitigen Grenzwerte von $M(x,y)$ überein und $M$ ist stetig bei $(x,y)$. Ist aber beispielsweise $x$ ein abbrechender Binärbruch $\in E$, dann entspricht der linksseitige Grenzwert einem Vorlage:Nowrap von $x$, während der rechtsseitige Grenzwert einem Vorlage:Nowrap von $x$ entspricht. Vorlage:AnkerZunächst werde eine Binärbruchverschränkung $M(x,y)$ für $(x,y)\in ]0,1[\times E$ untersucht mit nicht abbrechendem $x\in ]0,1[$ und abbrechendem $y=0_2.y_1\dots y_{k-1}{y}_k{y}_{k+1}$ mit $y_k=1$ und Vorlage:Nowrap $y$ mit Vorlage:Oberstrich2-Ende $y_{k-1}$ $x_{k-1}$ $1$ $x_k$ $0$ $x_{k+1}$ $0$ $x_{k+2}$ $y$ mit Vorlage:Oberstrich2-Ende $y_{k-1}$ $x_{k-1}$ $0$ $x_k$ $1$ $x_{k+1}$ $1$ $x_{k+2}$ Überträge   $0$   $0$   $1$   $1$   $1$   $1$   $1$   $\bar{1}$ Differenz $0$ $0$ $0$ $1$ $0$ $1$ $0$ $1$ Die erste Zeile enthält die verschränkten Binärziffern von $M(x,y)$, wenn $y$ mit Vorlage:Oberstrich2-Ende dargestellt wird, die zweite für dasselbe $y$ dargestellt mit Vorlage:Nowrap, die dritte enthält die Überträge der binären Subtraktion und die vierte Zeile enthält die Sprunghöhe, d. i. die Differenz »abbrechendes $y$« der ersten beiden Zeilen im Limes, also $\underset{\eta \downarrow y}{\lim }M(x,\eta )-\underset{\eta \uparrow y}{\lim }M(x,\eta )=M_{\downarrow }(x,y)-M_{\uparrow }(x,y)=0_2.00..\overline{01}=0_4.0.\bar{1}=\frac{4^{-k+1}}{3}=\frac{2^{-2k+2}}{3}.$ Für $(x,y)\in E\times ]0,1[$ mit abbrechendem $x=0_2.x_1\dots x_{k-1}{x}_k{x}_{k+1}$ bei $x_k=1$ und $x_{k+1}=0$ und mit nicht abbrechendem $y\in ]0,1[$ ist analog $x$ mit Vorlage:Oberstrich2-Ende $y_k$ $1$ $y_{k+1}$ $0$ $y_{k+2}$ $0$ $x$ mit Vorlage:Oberstrich2-Ende $y_k$ $0$ $y_{k+1}$ $1$ $y_{k+2}$ $1$ Überträge   $0$   $1$   $1$   $1$   $1$   $\bar{1}$ Differenz $0$ $0$ $1$ $0$ $1$ $0$ Die Differenz »abbrechendes $x$« ist im Limes $\underset{\xi \downarrow x}{\lim }M(\xi ,y)-\underset{\xi \uparrow x}{\lim }M(\xi ,y)=M_{\downarrow }(x,y)-M_{\uparrow }(x,y)=0_2.00....\overline{10}=0_4.0..\bar{2}=\frac{4^{-k+1}}{2\cdot 3}=\frac{2^{-2k+1}}{3}.$ Ist $(x,y)\in E\times E$, dann addieren sich die Sprunghöhen.

Raumfüllend

Zur Berechnung der (x,y)-Koordinaten der Z-Kurve aus den verschränkten Bits eines z-Werts, im Beispiel 2479

Die „Umkehrfunktion“

$\begin{array}{cccccc}U:& [0,1[& \to & [0,1[& \times & [0,1[\\ & \sum _{i=1}^{\mathrm{\infty }}{z}_i{2}^{-i}& \mapsto & (\sum _{i=1}^{\mathrm{\infty }}{z}_{2i-1}{2}^{-i}& ,& \sum _{i=1}^{\mathrm{\infty }}{z}_{2i}{2}^{-i})\end{array}$

mit $z_i\in \{0,1\}$ ist – wie das obige $M$ aus demselben Grund der fehlenden Rechtseindeutigkeit infolge mehrdeutiger binärer Darstellbarkeit – zunächst nicht wohldefiniert. Wie dort lässt sich die Rechtseindeutigkeit durch die Vorschrift herstellen, dass ein Bruch $z\in E$ entweder immer nur mit Vorlage:Nowrap (Vorschrift ↓) oder immer nur mit Vorlage:Nowrap (Vorschrift ↑) zu expandieren ist. Je nachdem sei die Variante von $U$ mit $U_{\downarrow }$ oder mit $U_{\uparrow }$ bezeichnet. Durch jede der beiden Vorschriften wird $U$ wohldefiniert. Sie bildet das Einheitsintervall $[0,1[$ surjektiv („raumfüllend“) auf das Einheitsquadrat $[0,1{[}^2$ ab.

$U$ ist aber nicht injektiv, denn die Punkte aus $(E\times [0,1[)\cup ([0,1[\times E)$ haben mehrere Urbilder. Beispielsweise hat der Punkt $(\frac{1}{2},\frac{1}{3})\in E\times [0,1[$ sowohl

$\frac{23}{60}$ wegen $U(\frac{23}{60})=U(0_4.1\overline{20})=U(0_2.01\overline{1000})=(0_2.10,0_2.\overline{01})=(\frac{1}{2},\frac{1}{3})$ als auch

$\frac{13}{60}$ wegen $U(\frac{13}{60})=U(0_4.0\overline{31})=U(0_2.00\overline{1101})=(0_2.0\bar{1},0_2.\overline{01})=(\frac{1}{2},\frac{1}{3})$

zum $U$-Urbild. Die Umkehrung davon entspricht mit $(x,y)=(\frac{1}{2},\frac{1}{3})$ genau den zwei einseitigen Grenzwerten

$\underset{\xi \downarrow x}{\lim }M(\xi ,y)=M_{\downarrow }(0_2.10,0_2.\overline{01})=0_2.01\overline{1000}=0_4.1\overline{20}=\frac{23}{60}$ und

$\underset{\xi \uparrow x}{\lim }M(\xi ,y)=M_{\uparrow }(0_2.0\bar{1},0_2.\overline{01})=0_2.00\overline{1101}=0_4.0\overline{31}=\frac{13}{60}$ .

Etwas anders liegt der Fall bei den im vorigen Abschnitt Binärbruchverschränkung erwähnten Punkten $\frac{5}{12}$ und Vorlage:Nowrap die weder Bildpunkte von $M_{\downarrow }$ noch von $M_{\uparrow }$ sind. Unter $U$ ist

$U(\frac{5}{12})=U(0_2.01\overline{10})=(0_2.1,0_2.0\bar{1})=(\frac{1}{2},\frac{1}{2})$ und

$U(\frac{7}{12})=U(0_2.10\overline{01})=(0_2.0\bar{1},0_2.1)=(\frac{1}{2},\frac{1}{2})$ ,

wogegen die einseitigen Grenzwerte von $M$ am Punkt $(x,y)=(\frac{1}{2},\frac{1}{2})$

$\underset{\xi \downarrow x,\eta \downarrow y}{\lim }M(\xi ,\eta )=M_{\downarrow }(0_2.1\bar{0},0_2.1\bar{0})=0_2.11\overline{00}=\frac{3}{4}$ und

$\underset{\xi \uparrow x,\eta \uparrow y}{\lim }M(\xi ,\eta )=M_{\uparrow }(0_2.0\bar{1},0_2.0\bar{1})=0_2.00\overline{11}=\frac{1}{4}$

sind.

$U$ ist nicht stetig an einem Punkt $z\in E$, weil linksseitiger Grenzwert Vorlage:Nowrap am Vorlage:Nowrap und rechtsseitiger Vorlage:Nowrap am Vorlage:Nowrap sich im Ergebnis unterscheiden (siehe Tabelle mit Beispielen).

Die Summe aller „Sprungweiten“ der Unstetigkeitsstellen (siehe Tabelle) wächst exponentiell mit der Zahl der Iterationen, da pro Iteration (siehe Abbildung „Vier Iterationen“) die Weite der Sprünge zwar mit dem Faktor 2 abnimmt, die Anzahl der Sprünge jedoch mit dem Faktor 4 zunimmt.

Tabelle mit Beispielen

Erläuterung zu den Spalten der Tabelle Der Exponent $l$ in der ersten Spalte korreliert mit der Iterationsnummer $\lceil \frac{l+1}{2}\rceil$ in der Abbildung „Vier Iterationen“, nämlich $l=1$ mit Iteration 1 und $l=2,3$ mit Iteration 2. Zu einem (binär abbrechenden) z-Wert $z=2^{-l}$ gibt es eine Unstetigkeitsstelle der Vorlage:Nowrap oder Vorlage:Nowrap. Die Spalte enthält den kleinsten zu $l$ gehörigen z-Wert; andere z-Werte, die ungerade Vielfache davon sind, sind ebenfalls Unstetigkeitsstellen; sie werden in der Spalte Anzahl gezählt. Für die Zwecke der nächsten Spalte $U_{\downarrow }(z)$ sind die x-Bits blau und die y-Bits rot eingefärbt. $U_{\downarrow }(z)$ ist gleichzeitig der rechtsseitige Grenzwert $\underset{\zeta \downarrow z}{\lim }U(\zeta )$. Die nächste Spalte zeigt denselben z-Wert, aber mit dem Vorlage:Nowrap. Auch hier sind die x-Bits blau und die y-Bits rot eingefärbt. Entsprechend dieser Einfärbung sind die Bits in der Spalte Vorlage:Nowrap in $x$- und Vorlage:Nowrap aufgeteilt. $\underset{\zeta \uparrow z}{\lim }U(\zeta )=U_{\uparrow }(z)$ bringt den linksseitigen Grenzwert (eine seiner Koordinaten ist $=U_{\downarrow }(z)$, die andere größer). Richtung gibt an, welche Koordinate sich ändert. Beispielsweise bedeutet ↑, dass sich die Vorlage:Nowrap an dieser Stelle bei infinitesimal wachsendem $z$ ändert, und zwar fallend und in den Abbildungen „Vier Iterationen“ und „dritte Iteration“ nach oben. Weite enthält die euklidische Distanz der beiden Grenzwerte. Anzahl enthält die Anzahl von Unstetigkeitsstellen (im Einheitsquadrat) mit dieser Richtung und Weite. Der Beitrag zur Gesamtsumme der Sprungweiten ist das Produkt von Weite mal Anzahl. $l$   $z=2^{-l}$ (Vorlage:Oberstrich2-Ende) $U_{\downarrow }(z)$ $z$ mit Vorlage:Oberstrich2-Ende $U({\bar{1}}_2$-Ende$)$ $U_{\uparrow }(z)$ Rich- tung Wei- te An- zahl Bei- trag $x,$ $y$ $x,$ $y$ $x,$ $y$ 1 $0_2.1$ $(0,$ $0_2.1)$ $0_2.011\bar{1}$ $(0_2.\bar{1},$ $0_2.0\bar{1})$ $(1,$ $0_2.1)$ ← $1$ 1   1 2 $0_2.01$ $(0_2.1,$ $0)$ $0_2.0011\bar{1}$ $(0_2.0\bar{1},$ $0_2.0\bar{1})$ $(0_2.1,$ $0_2.1)$ ↑ $0_2.1$ 2 +1 3 $0_2.001$ $(0,$ $0_2.01)$ $0_2.00011\bar{1}$ $(0_2.0\bar{1},$ $0_2.00\bar{1})$ $(0_2.1,$ $0_2.01)$ ← $0_2.1$ 4 +2 $2k-1$ $0_2...1$ $(0,$ $2^{-k})$ $0_2...011\bar{1}$ $(0_2..\bar{1},$ $0_2..0\bar{1})$ $(2^{-k+1},$ $2^{-k})$ ← $2^{-k+1}$ $2^{2k-2}$ $2^{k-1}$ 4 $0_2.0001$ $(0_2.01,$ $0)$ $0_2.000011\bar{1}$ $(0_2.00\bar{1},$ $0_2.00\bar{1})$ $(0_2.01,$ $0_2.01)$ ↑ $0_2.01$ 8 +2 $2k$ $0_2...01$ $(2^{-k},$ $0)$ $0_2...00111\bar{1}$ $(0_2..0\bar{1},$ $0_2..0\bar{1})$ $(2^{-k},$ $2^{-k})$ ↑ $2^{-k}$ $2^{2k-1}$ $2^{k-1}$ Tab. 1: Die Sprungweiten von $U$ in Abhängigkeit vom Exponenten $l$ Weitere Werte: $\begin{array}{ccccccc}{M}_{\downarrow }(2^{-k},& 0)& =2^{-2k}& ⟺& U_{\downarrow }(2^{-2k})& =(2^{-k},& 0)\\ M_{\uparrow }(2^{-k},& 0)& =2^{-2k}/3& ⟺& U_{\uparrow }(2^{-2k}/3)& =(2^{-k},& 0)\\ M_{\downarrow }(0,& 2^{-k})& =2^{-2k+1}& ⟺& U_{\downarrow }(2^{-2k+1})& =(0,& 2^{-k})\\ M_{\uparrow }(0,& 2^{-k})& =2^{-2k+1}/3& ⟺& U_{\uparrow }(2^{-2k+1}/3)& =(0,& 2^{-k})\\ M_{\downarrow }(2^{-k},& 2^{-k})& =2^{-2k}\cdot 3& ⟺& U_{\downarrow }(2^{-2k}\cdot 3)& =(2^{-k},& 2^{-k})\\ M_{\uparrow }(2^{-k},& 2^{-k})& =2^{-2k}& ⟺& U_{\uparrow }(2^{-2k})& =(2^{-k},& 2^{-k})\\ M_{\downarrow }(2^{-k},& 2^{-k-1})& =2^{-2k+1}\cdot 3& ⟺& U_{\downarrow }(2^{-2k+1}\cdot 3)& =(2^{-k},& 2^{-k-1})\\ M_{\uparrow }(2^{-k},& 2^{-k-1})& =2^{-2k-1}& ⟺& U_{\uparrow }(2^{-2k-1})& =(2^{-k},& 2^{-k-1})\\ M_{\downarrow }(2^{-k-1},& 2^{-k})& =2^{-2k-2}\cdot 9& ⟺& U_{\downarrow }(2^{-2k-2}\cdot 9)& =(2^{-k-1},& 2^{-k})\\ M_{\uparrow }(2^{-k-1},& 2^{-k})& =2^{-2k-2}\cdot 3& ⟺& U_{\uparrow }(2^{-2k-2}\cdot 3)& =(2^{-k-1},& 2^{-k})\end{array}$ Weitere Limites gegenübergestellt für $x=y=\frac{1}{2}$ $\begin{array}{cccc}\underset{\xi \uparrow x,\eta \uparrow y}{\lim }M(\xi ,\eta )=M_{\uparrow }(\frac{1}{2},\frac{1}{2})& =M(0_2.0\bar{1},0_2.0\bar{1})=0_2.00\overline{11}=\frac{1}{4};& U_{\downarrow }(\frac{1}{4})=(\frac{1}{2},0);& U_{\uparrow }(\frac{1}{4})=(\frac{1}{2},\frac{1}{2})\\ \underset{\xi \downarrow x,\eta \uparrow y}{\lim }M(\xi ,\eta )& =M(0_2.1\bar{0},0_2.0\bar{1})=0_2.01\overline{10}=\frac{5}{12};& U_{\downarrow }(\frac{5}{12})=(\frac{1}{2},\frac{1}{2})=& U_{\uparrow }(\frac{5}{12})\\ \underset{\xi \uparrow x,\eta \downarrow y}{\lim }M(\xi ,\eta )& =M(0_2.0\bar{1},0_2.1\bar{0})=0_2.10\overline{01}=\frac{7}{12};& U_{\downarrow }(\frac{7}{12})=(\frac{1}{2},\frac{1}{2})=& U_{\uparrow }(\frac{7}{12})\\ \underset{\xi \downarrow x,\eta \downarrow y}{\lim }M(\xi ,\eta )=M_{\downarrow }(\frac{1}{2},\frac{1}{2})& =M(0_2.1\bar{0},0_2.1\bar{0})=0_2.11\overline{00}=\frac{3}{4};& U_{\downarrow }(\frac{3}{4})=(\frac{1}{2},\frac{1}{2});& U_{\uparrow }(\frac{3}{4})=(\frac{1}{4},\frac{1}{2})\end{array}$

Z-Kurve der dritten Iteration.
Bei drei beispielhaften Sprüngen $l=1,2,3$ sind stetig machende Verbindungsstrecken als Pfeile hinzugefügt, die im Limes achsenparallel die entsprechende waagrechte Vorlage:Nowrap (bei ungeradem $l$) oder die senkrechte Vorlage:Nowrap (bei geradem $l$) überqueren.

Wegen der Unstetigkeit von $U$ ist die Bildmenge von $U$ keine Kurve. Da sie aber in der Ebene liegt, also zweidimensional ist, und $U$ bei wachsendem Argument $z$ an einer Unstetigkeitsstelle immer nur in der Vorlage:Nowrap oder der Vorlage:Nowrap springt, lassen sich die beiden Ränder (linksseitiger und rechtsseitiger Grenzwert) der Unstetigkeitsstelle durch eine Parallele zur Achse der springenden Koordinate verbinden, wie es die Abbildung „Vier Iterationen“ nahelegt (und wie es in der Abbildung „dritte Iteration (Beispiel)“ andeutungsweise ausgeführt ist). Dadurch entsteht eine stetige Abbildung $Z$, deren Bild Z-Kurve genannt wird. Die Stetigkeit impliziert, dass linksseitige und rechtsseitige Grenzwerte gleich sind; mit der Folge, dass Rechtseindeutigkeit auch ohne Entscheidung für Vorschrift ↓ oder Vorschrift ↑ besteht. $Z$ ist stetig und surjektiv, aber nicht injektiv. Da die endlichen Iterationen gleichwohl injektiv und damit selbst-ausweichend sind, gehört die Z-Kurve zu den FASS-Kurven, die ihrerseits eine echte Teilmenge der raumfüllenden Kurven sind.

Siehe auch

• Raumfüllende Kurve
• Bereichsquaternärbaum (Quadtree)

Weblinks

• Vorlage:AnkerMichael Bader: Vorlage:Webarchiv TUM Informatik