Z curve

Four iterations of the Z curve

The Z-curve (Lebesgue curve, English Z-order curve ) is a mapping that brings points from the multidimensional space into a linear order , the Z-order or Morton-order , an order with neighborhood-preserving properties. The Z-value of a spatial point is calculated by interlacing the binary coordinate values bit by bit .

With their help, (efficient) processes based on a linear order can be transferred to the multidimensional. This includes binary search , binary search tree , skip list , B-tree , or a B ⁺ -tree . In the latter case it is named UB-Tree (Universal B-Tree) after Rudolf Bayer .

In the case of direct access, the Morton order is in competition with an access in which the linear orders of the dimensions are connected one behind the other in different rankings to form a lexicographical order - in the internal memory via a multi-indexed field or. in the external memory via random access . If this can be organized well, it does a little worse. However, it is superior if such an access is followed by a sequential search in which neighborhood relationships can be advantageously used. The Z-curve is popular because of its good neighborhood conservation and the ease with which the Z-values ​​can be calculated. Neighborhood conservation is better for the Hilbert curve , but the calculations are more complicated.

This article deals mainly with the two-dimensional case.

Number theory

Z-curve (gray) of the third iteration
x-bits blue, y-bits red

The adjacent figure shows the Z values ​​in the two-dimensional case for integer coordinates . The bit interleaving of - and values (also Bitwise Gear cutting or Binärbruchpressung called) gives the binary values. If you connect these in their ascending numerical order, a curve ( polygon course ) is created, which is called the Z-curve. The underlying mapping is in its -th iteration with ${\displaystyle 0\leq x\leq 7,\,0\leq y\leq 7}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle z}$ ${\displaystyle n}$

${\displaystyle M_{n}\;\colon \{0,1,\dotso ,2^{n}\!\!-\!\!1\}^{2}\to \{0,1,\dotso ,4^{n}\!\!-\!\!1\}}$

designated. It can easily be extended to higher dimensions and is reversibly unambiguous ( bijective ).

In the binary representations of the Z values for there are 1 bits at most at binary places with an even number. In the base 4 system , these numbers only consist of digits 0 and 1. These numbers are called Z values ​​in the narrower sense or Moser-de Bruijn numbers . You make up the sequence A000695 in OEIS . ${\displaystyle M_{n}(x,0)}$ ${\displaystyle y=0}$

For the following, let this sequence be specified as

${\displaystyle z[\,]=\{0_{2},1_{2},100_{2},101_{2},10000_{2},10001_{2},10100_{2},10101_{2},\,\dotso \}}$ ,

where the first component is given the index 0. The sums and differences between two components can be formed using bit-wise operations ${\displaystyle z}$

${\displaystyle z[i+j]=((z[i]\lor {\overline {10}}_{2})+z[j])\land {\overline {01}}_{2}}$ and

${\displaystyle z[i-j]=((z[i]\land {\overline {01}}_{2})-z[j])\land {\overline {01}}_{2}}$if , ${\displaystyle i\geq j}$

with and with the operators for bit-wise logical AND and for bit-wise logical OR, each applied to the operands resolved into bit strings . ${\displaystyle {\overline {01}}_{2}:=\dotso {\overline {01}}0101_{2}}$ ${\displaystyle \land }$ ${\displaystyle \lor }$

A formula for generating the next element from the predecessor is ${\displaystyle z[i+1]}$ ${\displaystyle z[i]}$

${\displaystyle z[i+1]:=((z[i]\vee {\overline {10}}_{2})+1)\land {\overline {01}}_{2}}$.

Applications in computer science

Leaving out less significant bits, one can use the Z-values ​​for hash tables in which neighborhood searches are possible.

In spite of the good neighborhood preservation, an algorithm is required for the multi-dimensional area search in order to determine the next Z-value, the coordinates of which lie in the search area, starting from a point found in the data structure outside the search area.

In the example in the adjacent figure, the search area (x = 2..3, y = 2..6), a 2D interval, is displayed as a dashed rectangle. The highest Z value in it is MAX = 45. Assume that the value F = 19 is encountered in the course of the search, when searching for increasing values. The 1D interval between F and MAX (hatched area) is the superset of the part of the rectangle still to be searched. To speed up the search, we calculate the next Z value in the search area, hereinafter called BIGMIN (36 in the example). Then you only have to search through the interval between BIGMIN and MAX (values ​​shown in bold), so that the majority of the hatched area is skipped. The search for falling values ​​is analogous to this, with LITMAX, the largest Z-value in the search range, which is smaller than F. The problem and its solution were first described in 1981 by Tropf and Herzog. The solution is also used in the UB tree (“GetNextZ-address”).

By using the method hierarchically (according to the data structure used), if necessary after both rising and falling Z-values, a highly efficient multi-dimensional area search is obtained; this is useful in both commercial and technical applications, e.g. B. as a basic function for (closest) neighborhood searches.

BIGMIN source code for the Z curve and the Hilbert curve can be found in the Tropf patent.

The hierarchical application of this method, adapted to the underlying data structure and supporting both ascending and descending search direction, enables a highly efficient area search in commercial and technical applications. The Morton order is one of the few multi-dimensional access methods that have found their way into commercial database systems ( Transbase ).

Analysis

Binary fraction entanglement

The mapping "defined" by infinite iteration of the above rule and normalized to the unit interval ${\displaystyle M_{n}}$

${\displaystyle {\begin{array}{lllll}M\;\colon &[0,1]&\times &[0,1]&\to &[0,1]\\&{\Biggl (}\displaystyle \sum _{i=1}^{\infty }z_{2i}2^{-2i}&,&\displaystyle \sum _{i=1}^{\infty }z_{2i-1}2^{-2i+1}{\Biggr )}&\mapsto &\displaystyle \sum _{i=1}^{\infty }z_{i}2^{-i}\\&&&&=&\displaystyle \lim _{n\to \infty }4^{-n}\cdot M_{n}\left(2^{n}\cdot \displaystyle \sum _{i=1}^{n}z_{2i}2^{-2i},\;\;2^{n}\cdot \sum _{i=1}^{n}z_{2i-1}2^{-2i+1}\right)\\\end{array}}}$

with numbers is not initially well defined because it a reduced fraction with a power of two in the denominator, that is an element , two options are the representation. For example, the fraction is shown with a 0 ₂ ending ${\displaystyle z_{i}\in \{0,1\}}$ ${\displaystyle x\in E:=\mathbb {N} _{0}2^{-\mathbb {N} _{0}}\cap \,]0,1[}$ ${\displaystyle x={\tfrac {1}{2}}}$

${\displaystyle {\tfrac {1}{2}}=\displaystyle 1\cdot 2^{-1}+\sum _{i=2}^{\infty }0\cdot 2^{-i}=0_{2}.1{\overline {0}}}$

and those with a 1 ₂ ending

${\displaystyle {\tfrac {1}{2}}=\displaystyle 0\cdot 2^{-1}+\sum _{i=2}^{\infty }1\cdot 2^{-i}=0_{2}.0{\overline {1}}}$ .

This option (equality) is not given for finite items, but it is in the Limes , where it destroys the legal uniqueness of required for a function , since it affects the result of the entanglement. However, legal clarity can be restored, for example by one of the following provisions: ${\displaystyle n}$ ${\displaystyle \textstyle \lim _{n\to \infty }}$ ${\displaystyle M}$

Regulation A:

The binary representation of a fraction always has a 0 2 ending. This corresponds to the usual terminating representation and an approach to from above. This variant of is denoted by. ${\displaystyle w\in E}$ ${\displaystyle w}$ ${\displaystyle M}$ ${\displaystyle M_{A}}$

Regulation B:

The binary representation of 0 is 0 2 . The binary representation of a fraction always has a 1 2 ending. (If so , then the binary representation is to be used.) This corresponds to an approximation from below, i.e. a left-hand limit value formation for every function in which the binary representation is important, for example a limit . This variant of is denoted by. ${\displaystyle w\in E}$ ${\displaystyle k:=\min\{k\mid w\cdot 2^{k}\in \mathbb {Z} \}}$ ${\displaystyle w=2^{-k}\cdot {\bigl (}w\cdot 2^{k}-1+\textstyle \sum _{i=1}^{\infty }2^{-i}{\bigr )}}$ ${\displaystyle w}$ ${\displaystyle \textstyle \lim _{n\to \infty }M(x-2^{-n},y-2^{-n})}$ ${\displaystyle M}$ ${\displaystyle M_{B}}$

Each of the two rules is well-defined and is also injective . ${\displaystyle M}$

${\displaystyle M}$but is not surjective . Because with two provisions there is no archetype, as the coordinate necessarily an 0 ₂ -end and coordinate necessarily a 1 ₂ -end who would (resp. Vice versa .) The image of the unit square below is ${\displaystyle z=0_{2}.01{\overline {10}}=0_{4}.1{\overline {2}}={\tfrac {5}{12}}\in [0,1]}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle z=0_{2}.10{\overline {01}}=0_{4}.2{\overline {1}}={\tfrac {7}{12}}}$ ${\displaystyle M}$

${\displaystyle M_{A}{\bigl (}[0,1]^{2}{\bigr )}\;=\;\;\;[0,1]\;\setminus \;{\bigl (}\mathbb {N} _{0}2^{-\mathbb {N} _{0}}+\{-{\tfrac {1}{3}},{\tfrac {1}{3}}\}{\bigr )}}$	with regulation A resp.
${\displaystyle M_{B}{\bigl (}[0,1]^{2}{\bigr )}\;=\;{\Bigl (}[0,1]\;\setminus \;{\bigl (}\mathbb {N} _{0}2^{-\mathbb {N} _{0}}+\{-{\tfrac {1}{3}},{\tfrac {1}{3}}\}{\bigr )}{\Bigr )}\cup {\bigl (}{\tfrac {1}{3}}\cdot 2^{-\mathbb {N} _{0}}{\bigr )}}$	with regulation B.

In both cases it lacks a countable, dense subset of the unit interval. So it is not compact . (Nonetheless, the picture's closed shell .) ${\displaystyle M{\bigl (}[0,1]^{2}{\bigr )}=[0,1]}$

${\displaystyle M}$is also not continuous , since at the points an infinitesimal change in the argument causes a finite change in the function value. This can already be seen in the above figure "third iteration" , for example at the step of one of the -coordinate from to or at the step of one of the -coordinate from point to point , where the position number in the Z curve by more than a third (32−10 = 22> 64/3) resp. increases by more than one sixth (16−5 = 11> 64/6) of its total length (64). ${\displaystyle \in E}$ ${\displaystyle y}$ ${\displaystyle (0,11_{2})\mapsto 1010_{2}=10_{\rm {dez}}}$ ${\displaystyle (0,100_{2})\mapsto 100000_{2}=32}$ ${\displaystyle x}$ ${\displaystyle (11_{2},0)\mapsto 101_{2}=5}$ ${\displaystyle (100_{2},0)\mapsto 10000_{2}=16}$

Careful consideration

If the binary representation of a number does not contain a 1, then it is the 0, and there is no option to represent it with a 1 2 ending in such a way that the same numerical value 0 comes out. ${\displaystyle \in [0,1[}$ To examine the continuity at a point , one can use the differences between two one-sided limit values. Because if and only if these are all 0 , the function is continuous at the point . Is not yet a breaking off binary fraction, then vote the unilateral limits of agreement and is continuous at . However, if, for example, there is a terminating binary fraction , then the left-hand limit value corresponds to a 1 2 end of , while the right-hand limit value corresponds to a 0 2 end of . ${\displaystyle (x,y)\in \,]0,1[^{2}}$ ${\displaystyle (x,y)}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle M(x,y)}$ ${\displaystyle M}$ ${\displaystyle (x,y)}$ ${\displaystyle x}$ ${\displaystyle \in E}$ ${\displaystyle x}$ ${\displaystyle x}$ First, will a Binärbruchverschränkung for examined with not abbrechendem and abbrechendem with and . ${\displaystyle M(x,y)}$ ${\displaystyle (x,y)\,\in \;\,]0,1[\,\times E}$ ${\displaystyle x\in \,]0,1[}$ ${\displaystyle y=0_{2}.y_{1}\dotso y_{n-1}y_{n}y_{n+1}}$ ${\displaystyle y_{n}=1}$ ${\displaystyle y_{n+1}=0}$ ${\displaystyle y}$with 0 2 ending ${\displaystyle y_{n-1}}$ ${\displaystyle x_{n-1}}$ ${\displaystyle 1}$ ${\displaystyle x_{n}}$ ${\displaystyle 0}$ ${\displaystyle x_{n+1}}$ ${\displaystyle 0}$ ${\displaystyle x_{n+2}}$ ${\displaystyle y}$with 1 2 ending ${\displaystyle y_{n-1}}$ ${\displaystyle x_{n-1}}$ ${\displaystyle 0}$ ${\displaystyle x_{n}}$ ${\displaystyle 1}$ ${\displaystyle x_{n+1}}$ ${\displaystyle 1}$ ${\displaystyle x_{n+2}}$ Carryovers   ${\displaystyle \scriptstyle 0}$   ${\displaystyle \scriptstyle 0}$   ${\displaystyle \scriptstyle 1}$   ${\displaystyle \scriptstyle 1}$   ${\displaystyle \scriptstyle 1}$   ${\displaystyle \scriptstyle 1}$   ${\displaystyle \scriptstyle 1}$   ${\displaystyle \scriptstyle {\overline {1}}}$ difference ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle 0}$ ${\displaystyle 1}$ The first line contains the entangled binary digits of , if represented with 0 2 end, the second for the same represented with 1 2 end , the third contains the carries of the binary subtraction and the fourth line contains the jump height , i.e. i. the difference "breaking off " of the first two lines in the Limes, ie ${\displaystyle M(x,y)}$ ${\displaystyle y}$ ${\displaystyle y}$ ${\displaystyle y}$ ${\displaystyle \lim _{\eta \searrow y}M(x,\eta )-\lim _{\eta \nearrow y}M(x,\eta )=M_{A}(x,y)-M_{B}(x,y)=0_{2}.00..{\overline {01}}=0_{4}.0.{\overline {1}}={\frac {4^{-n+1}}{3}}={\frac {2^{-2n+2}}{3}}}$ . For with terminating at and and with not terminating is analogous ${\displaystyle (x,y)\in E\times \,]0,1[}$ ${\displaystyle x=0_{2}.x_{1}\dotso x_{n-1}x_{n}x_{n+1}}$ ${\displaystyle x_{n}=1}$ ${\displaystyle x_{n+1}=0}$ ${\displaystyle y\in \,]0,1[}$ ${\displaystyle x}$with 0 2 ending ${\displaystyle y_{n}}$ ${\displaystyle 1}$ ${\displaystyle y_{n+1}}$ ${\displaystyle 0}$ ${\displaystyle y_{n+2}}$ ${\displaystyle 0}$ ${\displaystyle x}$with 1 2 ending ${\displaystyle y_{n}}$ ${\displaystyle 0}$ ${\displaystyle y_{n+1}}$ ${\displaystyle 1}$ ${\displaystyle y_{n+2}}$ ${\displaystyle 1}$ Carryovers   ${\displaystyle \scriptstyle 0}$   ${\displaystyle \scriptstyle 1}$   ${\displaystyle \scriptstyle 1}$   ${\displaystyle \scriptstyle 1}$   ${\displaystyle \scriptstyle 1}$   ${\displaystyle \scriptstyle {\overline {1}}}$ difference ${\displaystyle 0}$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle 0}$ ${\displaystyle 1}$ ${\displaystyle 0}$ The "terminating " difference is in the Limes ${\displaystyle x}$ ${\displaystyle \lim _{\xi \searrow x}M(\xi ,y)-\lim _{\xi \nearrow x}M(\xi ,y)=M_{A}(x,y)-M_{B}(x,y)=0_{2}.00....{\overline {10}}=0_{4}.0..{\overline {2}}={\frac {4^{-n+1}}{2\cdot 3}}={\frac {2^{-2n+1}}{3}}}$ . Is , then the jump heights add up. ${\displaystyle (x,y)\in E\times E}$

Space-filling

The "reverse function"

${\displaystyle {\begin{array}{lllll}U\,\colon &\;[0,1]&\to &[0,1]&\times &[0,1]\\&\displaystyle \sum _{i=1}^{\infty }z_{i}2^{-i}&\mapsto &{\Biggl (}\displaystyle \sum _{i=1}^{\infty }z_{2i}2^{-2i}&,&\displaystyle \sum _{i=1}^{\infty }z_{2i-1}2^{-2i+1}{\Biggr )}\end{array}}}$

with is - like the above for the same reason of the lack of legal uniqueness due to ambiguous binary representability - initially not well-defined . As there, the right uniqueness can be established by the rule that a fraction is to be expanded either only with the 0 ₂ end (rule A) or only with the 1 ₂ end (rule B). Depending on whether the variant is denoted by with or with . Each of the two regulations is well-defined. It maps the unit interval surjectively ( "space-filling" ) onto the unit square . ${\displaystyle z_{i}\in \{0,1\}}$ ${\displaystyle M}$ ${\displaystyle z\in E}$ ${\displaystyle U}$ ${\displaystyle U_{A}}$ ${\displaystyle U_{B}}$ ${\displaystyle U}$ ${\displaystyle [0,1]}$ ${\displaystyle [0,1]^{2}}$

But it is not injective because the points from have several archetypes. For example, the point has both ${\displaystyle (E\times [0,1])\,\cup \,([0,1]\,\times E)}$ ${\displaystyle ({\tfrac {1}{2}},{\tfrac {1}{3}})\in E\times [0,1]}$

${\displaystyle {\tfrac {23}{60}}}$because of as well ${\displaystyle U({\tfrac {23}{60}})=U(0_{4}.1{\overline {20}})=U(0_{2}.01{\overline {1000}})=(0_{2}.10,0_{2}.{\overline {01}})=({\tfrac {1}{2}},{\tfrac {1}{3}})}$

${\displaystyle {\tfrac {13}{60}}}$ because of ${\displaystyle U({\tfrac {13}{60}})=U(0_{4}.0{\overline {31}})=U(0_{2}.00{\overline {1101}})=(0_{2}.0{\overline {1}},0_{2}.{\overline {01}})=({\tfrac {1}{2}},{\tfrac {1}{3}})}$

to the original image. The reverse of this corresponds exactly to the two one-sided limit values ${\displaystyle U}$ ${\displaystyle (x,y)=({\tfrac {1}{2}},{\tfrac {1}{3}})}$

${\displaystyle \lim _{\xi \searrow x}M(\xi ,y)=M_{A}(0_{2}.10,0_{2}.{\overline {01}})=0_{2}.01{\overline {1000}}=0_{4}.1{\overline {20}}={\tfrac {23}{60}}}$ and

${\displaystyle \lim _{\xi \nearrow x}M(\xi ,y)=M_{B}(0_{2}.0{\overline {1}},0_{2}.{\overline {01}})=0_{2}.00{\overline {1101}}=0_{4}.0{\overline {31}}={\tfrac {13}{60}}}$ .

Something different is the case in the previous section Binärbruchverschränkung mentioned points and , neither of pixels nor are. Is under ${\displaystyle {\tfrac {5}{12}}}$ ${\displaystyle {\tfrac {7}{12}}}$ ${\displaystyle M_{A}}$ ${\displaystyle M_{B}}$ ${\displaystyle U}$

${\displaystyle U({\tfrac {5}{12}})=U(0_{2}.01{\overline {10}})=(0_{2}.1,0_{2}.0{\overline {1}})=({\tfrac {1}{2}},{\tfrac {1}{2}})}$ and

${\displaystyle U({\tfrac {7}{12}})=U(0_{2}.10{\overline {01}})=(0_{2}.0{\overline {1}},0_{2}.1)=({\tfrac {1}{2}},{\tfrac {1}{2}})}$ ,

whereas the one-sided limit values ​​of at the point ${\displaystyle M}$ ${\displaystyle (x,y)=({\tfrac {1}{2}},{\tfrac {1}{2}})}$

${\displaystyle \lim _{\xi \searrow x,\,\eta \searrow y}M(\xi ,\eta )=M_{A}(0_{2}.1{\overline {0}},0_{2}.1{\overline {0}})=0_{2}.11{\overline {00}}={\tfrac {3}{4}}}$ and

${\displaystyle \lim _{\xi \nearrow x,\,\eta \nearrow y}M(\xi ,\eta )=M_{B}(0_{2}.0{\overline {1}},0_{2}.0{\overline {1}})=0_{2}.00{\overline {11}}={\tfrac {1}{4}}}$

are.

${\displaystyle U}$is not continuous at one point because the left-hand limit value ( at the 1 ₂ end ) and the right- hand limit value ( at the 0 ₂ end ) differ in the result (see table with examples). ${\displaystyle z\in E}$ ${\displaystyle \lim _{n\to \infty }U(z-2^{-n})=U_{B}(z)}$ ${\displaystyle \lim _{n\to \infty }U(z+2^{-n})=U_{A}(z)}$

The sum of all "jump sizes" of the discontinuities (see table) grows exponentially with the number of iterations, because per iteration (see figure "Four iterations" ) the size of the jumps decreases by a factor of 2, but the number of jumps by the factor 4 increases.

Table with examples

Explanation of the columns in the table The exponent correlates with the iteration number ( ) of the figure "Four iterations" . ${\displaystyle l}$ ${\displaystyle =\lfloor {\tfrac {l}{2}}\rfloor +1}$ To the z-values , there are (at least) a discontinuity of - or coordinate . The column contains the smallest associated z-value, the others are odd multiples of this and are only counted (in the Number column ). For the purposes of the next column , the x bits are colored blue and the y bits are colored red. ${\displaystyle z=2^{-l}}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle l}$ ${\displaystyle U_{A}(z)}$ ${\displaystyle U_{A}(z)}$is also the right-hand limit value . ${\displaystyle \textstyle \lim _{\zeta \searrow z}U(\zeta )}$ The next column shows the same z-value but with the 1 2 end . Here, too, the x bits are colored blue and the y bits are colored red. According to this coloring, the bits in the column are -end in - and coordinate divided. ${\displaystyle U({\overline {1}}_{2}}$ ${\displaystyle )}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle \textstyle \lim _{\zeta \nearrow z}U(\zeta )=U_{B}(z)}$brings the left-hand limit value (one of its coordinates is , the other is greater). ${\displaystyle =U_{A}(z)}$ Direction indicates which coordinate is changing. For example, ↑ means that the coordinate changes at this point with an infinitesimal increase , namely decreasing and in the figures "four iterations" and "third iteration" upwards. ${\displaystyle y}$ ${\displaystyle z}$ Width contains the Euclidean distance between the two limit values. Number contains the number of discontinuities (in the unit square) with this direction and width. The contribution to the total sum of the jump distances is the product of the distance times the number. ${\displaystyle l}$   ${\displaystyle z}$ ${\displaystyle =2^{-l}}$ ${\displaystyle U_{A}(z)}$ ${\displaystyle {\overline {1}}_{2}}$-The End   ${\displaystyle U({\overline {1}}_{2}}$-The End ${\displaystyle )}$ ${\displaystyle U_{B}(z)}$ RICH tung WEI te arrival number accession contract ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle y}$ 1 ${\displaystyle 0_{2}.{\color {red}1}{\color {blue}0}}$ ${\displaystyle (0,}$ ${\displaystyle 0_{2}.1)}$ ${\displaystyle 0_{2}.{\color {red}0}{\color {blue}1}{\color {red}1}{\overline {\color {blue}1}}}$ ${\displaystyle (0_{2}.\!{\overline {1}},}$ ${\displaystyle 0_{2}.0{\overline {1}})}$ ${\displaystyle (1,}$ ${\displaystyle 0_{2}.1)}$ ← ${\displaystyle 1}$ 1   1 2 ${\displaystyle 0_{2}.{\color {red}0}{\color {blue}1}}$ ${\displaystyle (0_{2}.1,}$ ${\displaystyle 0)}$ ${\displaystyle 0_{2}.{\color {red}0}{\color {blue}0}{\color {red}1}{\color {blue}1}{\color {red}1}{\overline {\color {blue}1}}}$ ${\displaystyle (0_{2}.0{\overline {1}},}$ ${\displaystyle 0_{2}.0{\overline {1}})}$ ${\displaystyle (0_{2}.1,}$ ${\displaystyle 0_{2}.1)}$ ↑ ${\displaystyle 0_{2}.1}$ 2 +1 3 ${\displaystyle 0_{2}.{\color {red}0}{\color {blue}0}{\color {red}1}{\color {blue}0}}$ ${\displaystyle (0,}$ ${\displaystyle 0_{2}.01)}$ ${\displaystyle 0_{2}.{\color {red}0}{\color {blue}0}{\color {red}0}{\color {blue}1}{\color {red}1}{\overline {\color {blue}1}}}$ ${\displaystyle (0_{2}.0{\overline {1}},}$ ${\displaystyle 0_{2}.00{\overline {1}})}$ ${\displaystyle (0_{2}.1,}$ ${\displaystyle 0_{2}.01)}$ ← ${\displaystyle 0_{2}.1}$ 4th +2 4th ${\displaystyle 0_{2}.{\color {red}0}{\color {blue}0}{\color {red}0}{\color {blue}1}}$ ${\displaystyle (0_{2}.01,}$ ${\displaystyle 0)}$ ${\displaystyle 0_{2}.{\color {red}0}{\color {blue}0}{\color {red}0}{\color {blue}0}{\color {red}1}{\color {blue}1}{\color {red}1}{\overline {\color {blue}1}}}$ ${\displaystyle (0_{2}.00{\overline {1}},}$ ${\displaystyle 0_{2}.00{\overline {1}})}$ ${\displaystyle (0_{2}.01,}$ ${\displaystyle 0_{2}.01)}$ ↑ ${\displaystyle 0_{2}.01}$ 8th +2 ${\displaystyle 2k}$ ${\displaystyle 0_{2}.{\color {red}.}{\color {blue}.}{\color {red}0}{\color {blue}1}}$ ${\displaystyle (2^{-k},}$ ${\displaystyle 0)}$ ${\displaystyle 0_{2}.{\color {red}.}{\color {blue}.}{\color {red}0}{\color {blue}0}{\color {red}1}{\color {blue}1}{\color {red}1}{\overline {\color {blue}1}}}$ ${\displaystyle (0_{2}.{\color {blue}.}{\color {blue}0}{\overline {\color {blue}1}},}$ ${\displaystyle 0_{2}.{\color {red}.}{\color {red}0}{\overline {\color {red}1}})}$ ${\displaystyle (2^{-k},}$ ${\displaystyle 2^{-k})}$ ↑ ${\displaystyle 2^{-k}}$ ${\displaystyle 2^{2k-1}}$ ${\displaystyle 2^{k-1}}$ 5 ${\displaystyle 0_{2}.{\color {red}0}{\color {blue}0}{\color {red}0}{\color {blue}0}{\color {red}1}{\color {blue}0}}$ ${\displaystyle (0,}$ ${\displaystyle 0_{2}.001)}$ ${\displaystyle 0_{2}.{\color {red}0}{\color {blue}0}{\color {red}0}{\color {blue}0}{\color {red}0}{\color {blue}1}{\color {red}1}{\overline {\color {blue}1}}}$ ${\displaystyle (0_{2}.00{\overline {1}},}$ ${\displaystyle 0_{2}.000{\overline {1}})}$ ${\displaystyle (0_{2}.01,}$ ${\displaystyle 0_{2}.001)}$ ← ${\displaystyle 0_{2}.01}$ 16 +4 ${\displaystyle 2k\!+\!1}$ ${\displaystyle 0_{2}.{\color {red}.}{\color {blue}.}{\color {red}.}{\color {blue}.}{\color {red}1}{\color {blue}0}}$ ${\displaystyle (0,}$ ${\displaystyle 2^{-k-1})}$ ${\displaystyle 0_{2}.{\color {red}.}{\color {blue}.}{\color {red}.}{\color {blue}.}{\color {red}0}{\color {blue}1}{\color {red}1}{\overline {\color {blue}1}}}$ ${\displaystyle (0_{2}.{\color {blue}.}{\color {blue}.}{\color {blue}1}{\overline {\color {blue}1}},}$ ${\displaystyle 0_{2}.{\color {red}.}{\color {red}.}{\color {red}0}{\overline {\color {red}1}})}$ ${\displaystyle (2^{-k},}$ ${\displaystyle 2^{-k-1})}$ ← ${\displaystyle 2^{-k}}$ ${\displaystyle 2^{2k}}$ ${\displaystyle 2^{k}}$ Tab. 1: The jump widths depending on the exponent ${\displaystyle U}$ ${\displaystyle l}$ Other values: ${\displaystyle {\begin{array}{lllll}M_{A}(2^{-k},&0)&=2^{-2k}&\qquad \qquad &U_{A}(2^{-2k})&=(2^{-k},&0)\\M_{B}(2^{-k},&0)&=2^{-2k}/3&&U_{B}(2^{-2k}/3)&=(2^{-k},&0)\\M_{A}(0,&2^{-k})&=2^{-2k+1}&&U_{A}(2^{-2k+1})&=(0,&2^{-k})\\M_{B}(0,&2^{-k})&=2^{-2k+1}/3&&U_{B}(2^{-2k+1}/3)&=(0,&2^{-k})\\M_{A}(2^{-k},&2^{-k})&=2^{-2k}\cdot 3&&U_{A}(2^{-2k}\cdot 3)&=(2^{-k},&2^{-k})\\M_{B}(2^{-k},&2^{-k})&=2^{-2k}&&U_{B}(2^{-2k})&=(2^{-k},&2^{-k})\\M_{A}(2^{-k},&2^{-k-1})&=2^{-2k+1}\cdot 3&&U_{A}(2^{-2k+1}\cdot 3)&=(2^{-k},&2^{-k-1})\\M_{B}(2^{-k},&2^{-k-1})&=2^{-2k-1}&&U_{B}(2^{-2k-1})&=(2^{-k},&2^{-k-1})\\M_{A}(2^{-k-1},&2^{-k})&=2^{-2k-2}\cdot 9&&U_{A}(2^{-2k-2}\cdot 9)&=(2^{-k-1},&2^{-k})\\M_{B}(2^{-k-1},&2^{-k})&=2^{-2k-2}\cdot 3&&U_{B}(2^{-2k-2}\cdot 3)&=(2^{-k-1},&2^{-k})\\\end{array}}}$ Other limits compared for ${\displaystyle x=y={\tfrac {1}{2}}}$ ${\displaystyle {\begin{array}{lllllll}&&&&&&U_{A}({\tfrac {1}{4}})&=({\tfrac {1}{2}},0)\\\displaystyle \lim _{\xi \nearrow x,\,\eta \nearrow y}M(\xi ,\eta )&=M_{B}({\tfrac {1}{2}},{\tfrac {1}{2}})&=M(0_{2}.0{\overline {1}},0_{2}.0{\overline {1}})&=0_{2}.00{\overline {11}}&=\displaystyle {\tfrac {1}{4}}&\qquad &U_{B}({\tfrac {1}{4}})&=({\tfrac {1}{2}},{\tfrac {1}{2}})\\\displaystyle \lim _{\xi \searrow x,\,\eta \nearrow y}M(\xi ,\eta )&&=M(0_{2}.1{\overline {0}},0_{2}.0{\overline {1}})&=0_{2}.01{\overline {10}}&=\displaystyle {\tfrac {5}{12}}&&U({\tfrac {5}{12}})&=({\tfrac {1}{2}},{\tfrac {1}{2}})\\\displaystyle \lim _{\xi \nearrow x,\,\eta \searrow y}M(\xi ,\eta )&&=M(0_{2}.0{\overline {1}},0_{2}.1{\overline {0}})&=0_{2}.10{\overline {01}}&=\displaystyle {\tfrac {7}{12}}&&U({\tfrac {7}{12}})&=({\tfrac {1}{2}},{\tfrac {1}{2}})\\&&&&&&U_{B}({\tfrac {3}{4}})&=({\tfrac {1}{4}},{\tfrac {1}{2}})\\\displaystyle \lim _{\xi \searrow x,\,\eta \searrow y}M(\xi ,\eta )&=M_{A}({\tfrac {1}{2}},{\tfrac {1}{2}})&=M(0_{2}.1{\overline {0}},0_{2}.1{\overline {0}})&=0_{2}.11{\overline {00}}&=\displaystyle {\tfrac {3}{4}}&&U_{A}({\tfrac {3}{4}})&=({\tfrac {1}{2}},{\tfrac {1}{2}})\\\end{array}}}$

Because of the discontinuity of , the image set of is not a curve . But since it lies in the plane, so it is two-dimensional, and with increasing argument always a discontinuity only in the - or the coordinate jumps, their two edges (left-sided and right-sided limit) of discontinuity by a parallel to the axis of the jumping Connect coordinates as the figure “Four iterations” suggests (and as indicated in the figure “Third iteration (example)” ). This creates a continuous mapping , the image of which is called the Z-curve . The continuity implies that left-hand and right-hand limits are the same; with the result that legal clarity exists even without a decision in favor of rule A or rule B. is continuous and surjective, but not injective. Since the finite iterations are nevertheless injective and thus self-evasive, the Z curve belongs to the FASS curves , which in turn are a real subset of the space-filling curves. ${\displaystyle U}$ ${\displaystyle U}$ ${\displaystyle U}$ ${\displaystyle z}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle Z}$ ${\displaystyle Z}$

Explicit wording

Third iteration Z-curve. In three exemplary jumps , connecting stretches that make it steady are added, which cross the parallel axis in the Limes. ${\displaystyle l=2,3,4}$ The following gives an explicit formula for the continuous Z function. In order to accommodate the connecting lines in the definition set (and image set), the argument is written ternary, i.e. base 3 and with the digits 0, 1, 2. The binary fraction entanglement only takes place with digits 0 and 1. The first occurrence of the number 2 is given the meaning that the following numbers, interpreted as a ternary number, parameterize the connecting route between the adjacent left-hand and right-hand limit values ​​in a straight line. ${\displaystyle z}$ The line connecting the point of discontinuity in the first iteration runs from point to point and has a length of 1. It can be found in the table below in the three rows with (see also figure “Third iteration (example)” ). To fill the area of ​​the unit square, one can simply start from the interval , because there is no need to allow a 2 for the first ternary digit . ${\displaystyle (1,{\tfrac {1}{2}})}$ ${\displaystyle (0,{\tfrac {1}{2}})}$ ${\displaystyle l=2}$ ${\displaystyle [0,{\tfrac {2}{3}}]}$ ${\displaystyle z_{1}}$ So be and with and a ternary representation . Further be ${\displaystyle z\in [0,{\tfrac {2}{3}}]}$ ${\displaystyle \textstyle \sum _{i=1}^{\infty }z_{i}3^{-i}:=z}$ ${\displaystyle z_{i}\in \{0,1,2\}}$ ${\displaystyle z_{1}\neq 2}$ ${\displaystyle l(z):={\begin{cases}\nexists i\;(z_{i}\!=\!2):&\infty \\\exists i\;(z_{i}\!=\!2):&\min\{i\;|\;z_{i}\!=\!2\}\end{cases}}}$ the smallest index with a digit 2 (consequently ) and ${\displaystyle l(z)\geq 2}$ ${\displaystyle w(z):=1-\sum _{i=1}^{\infty }z_{l(z)+i}3^{-i}\quad \in [0,1]}$     (only required if ). ${\displaystyle l(z)<\infty }$ Besides, be ${\displaystyle V_{x}(z):=\sum _{i=1}^{(l(z)-1)/2}z_{2i}2^{-2i}}$ (digits only ${\displaystyle z_{2i}\;\;\in \{0,1\}}$ with an even index ${\displaystyle 2i\quad \;\;\leq l(z)-1}$) and ${\displaystyle V_{y}(z):=\;\;\;\sum _{i=1}^{l(z)/2}z_{2i-1}2^{-2i+1}}$ (digits only ${\displaystyle z_{2i-1}\in \{0,1\}}$ with odd index ${\displaystyle 2i-1\leq l(z)-1}$) and finally ${\displaystyle v_{x}(z):=2^{-{\big \lfloor }{\tfrac {l(z)-1}{2}}{\big \rfloor }}}$ and ${\displaystyle v_{y}(z):=2^{-{\big \lfloor }{\tfrac {l(z)}{2}}{\big \rfloor }}}$     (only required if ). ${\displaystyle l(z)<\infty }$ Then the function ${\displaystyle Z\,\colon }$ ${\displaystyle [0,{\tfrac {2}{3}}]\qquad \qquad \to }$ ${\displaystyle [0,1]}$ ${\displaystyle \times \;[0,1]}$ ${\displaystyle \displaystyle z=:\sum _{i=1}^{\infty }z_{i}3^{-i}\;\mapsto {\begin{cases}\\\\\\\\\end{cases}}}$ ${\displaystyle l(z)=\infty :}$ ${\displaystyle {\bigl (}V_{x}(z)}$ ${\displaystyle ,V_{y}(z){\bigr )}}$ ${\displaystyle l(z)<\infty :{\begin{cases}\\\\\\\end{cases}}}$ ${\displaystyle 2\mid l(z):}$   ${\displaystyle {\bigl (}V_{x}(z)+v_{x}(z)\cdot w(z)}$ ${\displaystyle ,V_{y}(z)+v_{y}(z){\bigr )}}$ ${\displaystyle 2\nmid l(z):}$ ${\displaystyle {\bigl (}V_{x}(z)+v_{x}(z)}$ ${\displaystyle ,V_{y}(z)+v_{y}(z)\cdot w(z){\bigr )}}$ the steadily added iteration of the curve number in the figures "Four iterations" and "third iteration" , the Z curve in the narrower sense. This is surjective, but not injective. ${\displaystyle \infty }$ Some examples: ${\displaystyle l}$   RICH tung ${\displaystyle z}$   ${\displaystyle Z(z)}$ ${\displaystyle \to [0,1]^{2}}$ ${\displaystyle x}$ ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle y}$ ∞ ${\displaystyle 0_{3}.\!{\color {red}0}{\color {blue}0}{\overline {{\color {red}1}{\color {blue}1}}}}$ ${\displaystyle (0_{2}.\!{\color {blue}0}{\overline {\color {blue}1}},}$ ${\displaystyle 0_{2}.\!{\color {red}0}{\overline {\color {red}1}})}$ ${\displaystyle ({\tfrac {1}{2}},}$ ${\displaystyle {\tfrac {1}{2}})}$ ∞ ${\displaystyle 0_{3}.\!{\color {red}0}{\color {blue}1}{\overline {{\color {red}1}{\color {blue}0}}}}$ ${\displaystyle (0_{2}.\!{\color {blue}1}{\overline {\color {blue}0}},}$ ${\displaystyle 0_{2}.\!{\color {red}0}{\overline {\color {red}1}})}$ ${\displaystyle ({\tfrac {1}{2}},}$ ${\displaystyle {\tfrac {1}{2}})}$ ∞ ${\displaystyle 0_{3}.\!{\color {red}1}{\color {blue}0}{\overline {{\color {red}0}{\color {blue}1}}}}$ ${\displaystyle (0_{2}.\!{\color {blue}0}{\overline {\color {blue}1}},}$ ${\displaystyle 0_{2}.\!{\color {red}1}{\overline {\color {red}0}})}$ ${\displaystyle ({\tfrac {1}{2}},}$ ${\displaystyle {\tfrac {1}{2}})}$ ∞ ${\displaystyle 0_{3}.\!{\color {red}1}{\color {blue}1}{\overline {{\color {red}0}{\color {blue}0}}}}$ ${\displaystyle (0_{2}.\!{\color {blue}1}{\overline {\color {blue}0}},}$ ${\displaystyle 0_{2}.\!{\color {red}1}{\overline {\color {red}0}})}$ ${\displaystyle ({\tfrac {1}{2}},}$ ${\displaystyle {\tfrac {1}{2}})}$ ∞ ${\displaystyle 0_{3}.\!{\color {red}0}{\color {blue}1}{\color {red}1}{\overline {\color {blue}1}}}$ ${\displaystyle (0_{2}.\!{\overline {\color {blue}1}},}$ ${\displaystyle 0_{2}.\!{\color {red}0}{\overline {\color {red}1}})}$ ${\displaystyle (1,}$ ${\displaystyle {\tfrac {1}{2}})}$ 2 ← ${\displaystyle 0_{3}.\!{\color {red}0}20{\overline {0}}}$ ${\displaystyle (0+2^{0}\cdot (1-0_{3}.\!{\overline {0}}),}$ ${\displaystyle 0_{2}.\!{\color {red}0}+2^{-1})}$ ${\displaystyle (1,}$ ${\displaystyle {\tfrac {1}{2}})}$ 2 ← ${\displaystyle 0_{3}.\!{\color {red}0}21{\overline {1}}}$ ${\displaystyle (0+2^{0}\cdot (1-0_{3}.\!{\overline {1}}),}$ ${\displaystyle 0_{2}.\!{\color {red}0}+2^{-1})}$ ${\displaystyle ({\tfrac {1}{2}},}$ ${\displaystyle {\tfrac {1}{2}})}$ 2 ← ${\displaystyle 0_{3}.\!{\color {red}0}22{\overline {2}}}$ ${\displaystyle (0+2^{0}\cdot (1-0_{3}.\!{\overline {2}}),}$ ${\displaystyle 0_{2}.\!{\color {red}0}+2^{-1})}$ ${\displaystyle (0,}$ ${\displaystyle {\tfrac {1}{2}})}$ ∞ ${\displaystyle 0_{3}.\!{\color {red}1}{\color {blue}0}{\color {red}0}{\overline {\color {blue}0}}}$ ${\displaystyle (0_{2}.\!{\overline {\color {blue}0}},}$ ${\displaystyle 0_{2}.\!{\color {red}1}{\overline {\color {red}0}})}$ ${\displaystyle (0,}$ ${\displaystyle {\tfrac {1}{2}})}$ ∞ ${\displaystyle 0_{3}.\!{\color {red}1}{\color {blue}0}{\color {red}1}{\color {blue}1}{\overline {\color {red}1}}}$ ${\displaystyle (0_{2}.\!{\color {blue}0}{\overline {\color {blue}1}},}$ ${\displaystyle 0_{2}.\!{\overline {\color {red}1}})}$ ${\displaystyle ({\tfrac {1}{2}},}$ ${\displaystyle 1)}$ 3 ↑ ${\displaystyle 0_{3}.\!{\color {red}1}{\color {blue}0}20{\overline {0}}}$ ${\displaystyle (0_{2}.\!{\color {blue}0}+2^{-1},}$ ${\displaystyle 0_{2}.\!{\color {red}1}+2^{-1}\cdot (1-0_{3}.\!{\overline {0}}))}$ ${\displaystyle ({\tfrac {1}{2}},}$ ${\displaystyle 1)}$ 3 ↑ ${\displaystyle 0_{3}.\!{\color {red}1}{\color {blue}0}21{\overline {1}}}$ ${\displaystyle (0_{2}.\!{\color {blue}0}+2^{-1},}$ ${\displaystyle 0_{2}.\!{\color {red}1}+2^{-1}\cdot (1-0_{3}.\!{\overline {1}}))}$ ${\displaystyle ({\tfrac {1}{2}},}$ ${\displaystyle {\tfrac {3}{4}})}$ 3 ↑ ${\displaystyle 0_{3}.\!{\color {red}1}{\color {blue}0}22{\overline {2}}}$ ${\displaystyle (0_{2}.\!{\color {blue}0}+2^{-1},}$ ${\displaystyle 0_{2}.\!{\color {red}1}+2^{-1}\cdot (1-0_{3}.\!{\overline {2}}))}$ ${\displaystyle ({\tfrac {1}{2}},}$ ${\displaystyle {\tfrac {1}{2}})}$ ∞ ${\displaystyle 0_{3}.\!{\color {red}1}{\color {blue}1}{\color {red}0}{\color {blue}0}{\overline {\color {red}0}}}$ ${\displaystyle (0_{2}.\!{\color {blue}1}{\overline {\color {blue}0}},}$ ${\displaystyle 0_{2}.\!{\color {red}1}{\overline {\color {red}0}})}$ ${\displaystyle ({\tfrac {1}{2}},}$ ${\displaystyle {\tfrac {1}{2}})}$ ∞ ${\displaystyle 0_{3}.\!{\color {red}0}{\color {blue}1}{\color {red}0}{\color {blue}1}{\color {red}1}{\overline {\color {blue}1}}}$ ${\displaystyle (0_{2}.\!{\overline {\color {blue}1}},}$ ${\displaystyle 0_{2}.\!{\color {red}00}{\overline {\color {red}1}})}$ ${\displaystyle (1,}$ ${\displaystyle {\tfrac {1}{4}})}$ 4th ← ${\displaystyle 0_{3}.\!{\color {red}0}{\color {blue}1}{\color {red}0}20{\overline {0}}}$ ${\displaystyle (0_{2}.\!{\color {blue}1}+2^{-1}\cdot (1-0_{3}.\!{\overline {0}}),}$ ${\displaystyle 0_{2}.\!{\color {red}00}+2^{-2})}$ ${\displaystyle (1,}$ ${\displaystyle {\tfrac {1}{4}})}$ 4th ← ${\displaystyle 0_{3}.\!{\color {red}0}{\color {blue}1}{\color {red}0}21{\overline {1}}}$ ${\displaystyle (0_{2}.\!{\color {blue}1}+2^{-1}\cdot (1-0_{3}.\!{\overline {1}}),}$ ${\displaystyle 0_{2}.\!{\color {red}00}+2^{-2})}$ ${\displaystyle ({\tfrac {3}{4}},}$ ${\displaystyle {\tfrac {1}{4}})}$ 4th ← ${\displaystyle 0_{3}.\!{\color {red}0}{\color {blue}1}{\color {red}0}22{\overline {2}}}$ ${\displaystyle (0_{2}.\!{\color {blue}1}+2^{-1}\cdot (1-0_{3}.\!{\overline {2}}),}$ ${\displaystyle 0_{2}.\!{\color {red}00}+2^{-2})}$ ${\displaystyle ({\tfrac {1}{2}},}$ ${\displaystyle {\tfrac {1}{4}})}$ ∞ ${\displaystyle 0_{3}.\!{\color {red}0}{\color {blue}1}{\color {red}1}{\color {blue}0}{\color {red}0}{\overline {\color {blue}0}}}$ ${\displaystyle (0_{2}.\!{\color {blue}1}{\overline {\color {blue}0}},}$ ${\displaystyle 0_{2}.\!{\color {red}01}{\overline {\color {red}0}})}$ ${\displaystyle ({\tfrac {1}{2}},}$ ${\displaystyle {\tfrac {1}{4}})}$ Tab. 2: Image points of , including 3 connecting lines with the exponents ${\displaystyle Z}$ ${\displaystyle l=2,3,4}$

See also

• Space-filling curve
• Area Quadtree

Web links

• Michael Bader: Space-filling curves ( Memento from March 17, 2005 in the Internet Archive ; PDF; 637 kB) TUM Informatik

Remarks

1. ↑ Strictly speaking, this mapping is not, but at most its reversal is a space-filling curve .
2. ↑ In the literature, it is a convention to put the bits to the left of the bits. This creates the characteristic Z-shape when (as in the first two figures) grows to the right and down. ${\displaystyle y}$ ${\displaystyle x}$ ${\displaystyle x}$ ${\displaystyle y}$
3. ↑ The injectivity is lost with (more precisely: im ). The problems with the right uniqueness that also occur have the same cause ( see below ). ${\displaystyle n=\infty }$ ${\displaystyle \textstyle \lim _{n\to \infty }M_{n}}$
4. ↑ The points of the Cantor set contain only digits 0 and 2 in their classical representation for base 3 .
5. ↑ In order to avoid ambiguity or confusion with the comma in the notations for intervals or coordinate pairs, the point is used below as a separator for the positions with negative exponents. We follow M. Bader in this regard as well as in the placement of the base as a prefix for this point.
6. ↑ ^{a b} This reason for discontinuity applies completely regardless of the decision whether rule A or rule B.
7. ↑ Continuous and bijective is only possible with the same dimension ( theorem of the invariance of the dimension ).
8. ↑ There are room-filling curves that are constant from the start in the Limes, such as the Hilbert curve and the Peano curve . In this respect, the continuity of the Z curve, which has been improved here, indicates a neighborhood behavior that can be improved.

Individual evidence

1. ↑ Volker Gaede, Oliver Guenther: Multidimensional access methods . (PDF) In: ACM Computing Surveys . 30, No. 2, 1998, pp. 170-231. doi : 10.1145 / 280277.280279 .
2. ^ GM Morton: A Computer Oriented Geodetic Data Base; and a New Technique in File Sequencing . In: IBM (Ed.): Technical Report . , Ottawa, Canada 1966.
3. ↑ ^{a b} Frank Ramsak, Volker Markl, Robert Fenk, Martin circles, Klaus Elhardt, Rudolf Bayer: Integrating the UB tree into a Database System Kernel Archived from the original on March 4, 2016. In: Int. Conf. on Very Large Databases (VLDB) . 2000, pp. 263-272.
4. ↑ ^{a b} Jeyarajan Thiyagalingam, Olav Beckmann, Paul HJ Kelly: Is Morton layout competitive for large two-dimensional arrays yet? . In: Concurrency and Computation: Practice and Experience . 18, No. 11, September 2006, pp. 1509-1539. doi : 10.1002 / cpe.v18: 11 .
5. ^ H. Tropf, H. Herzog: Multidimensional Range Search in Dynamically Balanced Trees . (PDF) In: Angewandte Informatik , 2/1981, pp. 71–77.
6. ↑ Patent US7321890 : Database and method for organizing data elements. Registered on February 18, 2004 , published on January 22, 2008 , inventor: Hermann Tropf (expired). ‌
7. ↑ Is Morton layout competitive for large two-dimensional arrays yet? ( Memento from October 15, 2006 in the Internet Archive )
8. ↑ ^{a b} for is ${\displaystyle x\notin E\wedge y\notin E}$

   ${\displaystyle M_{B}(x,y)=\textstyle \lim _{n\to \infty }M(x-2^{-n},y)=\lim _{n\to \infty }M(x+2^{-n},y)=M_{A}(x,y)=M(x,y)}$ such as

   ${\displaystyle M_{B}(x,y)=\textstyle \lim _{n\to \infty }M(x,y-2^{-n})=\lim _{n\to \infty }M(x,y+2^{-n})=M_{A}(x,y)=M(x,y)}$ .

9. ↑ Michael Bader: Space-Filling Curves. An Introduction to Applications in Scientific Computing (= Timothy J. Barth, Michael Griebel, David E. Keyes, Risto M. Nieminen, Dirk Roose, Tamar Schlick [Eds.]: Texts in Computational Science and Engineering . Volume 9 ). 1st edition. Springer-Verlag, 2013, ISBN 978-3-642-31045-4 , ISSN  1611-0994 , doi : 10.1007 / 978-3-642-31046-1 (English, 278 pages). P. 96.