# Courbe de Hilbert

La courbe de Hilbert est une courbe continue remplissant un carré. Elle a été décrite pour la première fois par le mathématicien allemand David Hilbert en 1891.
Comme elle couvre un carré, sa dimension de Hausdorff et sa dimension topologique sont égales à 2. On la considère cependant comme faisant partie des fractales.
La longueur euclidienne de H$_n$ (la courbe approchée continue obtenue à la n-ième itération) est $2^{n}-{1 \over 2^{n}}$ ; elle croit donc exponentiellement avec n.
Pour le parcours des bases de données multi-dimensionnelles, la courbe de Hilbert a été proposée à la place de la courbe de Lebesgue parce qu'elle a un comportement préservant mieux la localité.

## Construction géométrique

Hilbert définit la fonction $f:[0,1]\to [0,1]^{2}$ comme limite de fonctions $f_{n}:[0,1]\to [0,1]^{2}$ donnant les approximations successives de la courbe de Hilbert.
* À l'étape 0, le graphe H$_0$ se limite à un seul point, disposé au centre du carré $[0,1]\times [0,1]$. Ce point est à la fois point initial et point final de H$_0$. Le centre du carré de coordonnées (1/2, 1/2) est l'image par une fonction f$_0$ de l'intervalle $[0,1]$ tout entier.
* À l'étape 1, on coupe en quatre parties égales l'intervalle $[0,1]$ et on fait correspondre à chaque intervalle de la subdivision un quart du carré initial. Plus précisément, l'intervalle $[0,1/4]$ est associé au sous-carré $[0,1/2]\times [0,1/2]$ ; l'intervalle $[1/4,1/2]$ est associé au sous-carré $[0,1/2]\times [1/2,1]$ ; l'intervalle $[1/2,3/4]$ est associé au sous-carré $[1/2,1]\times [1/2,1]$ ; et enfin, l'intervalle $[3/4,1]$ est associé au sous-carré $[1/2,1]\times [0,1/2]$. Ainsi, le parcours des quatre sous-carrés se fait dans l'ordre suivant :
| 1 | 2 |
| 0 | 3 |
    Si on relie les centres de ces carrés par des segments, on obtient le graphe H$_1$. Son point initial est le point de coordonnées $(1/4,1/4)$, et son point final est le point de coordonnées $(3/4,1/4)$. C'est l'arc paramétré par une fonction f$_1$ qui envoie l'intervalle [0, 1/4] sur la partie de H$_1$ contenue dans le carré 0, l'intervalle $[1/4,1/2]$ sur la partie de H$_1$ contenue dans le carré 1, l'intervalle $[1/2,3/4]$ sur la partie de H$_1$ contenue dans le carré 2, et l'intervalle $[3/4,1]$ sur la partie de H$_1$ contenue dans le carré 3, en suivant le sens de parcours.
* À l'étape n, chaque intervalle de la subdivision obtenue à l'étape n-1 est lui-même divisé en quatre, de même que le carré qui lui est associé. On dispose dans chaque carré de côté 1/2 numéroté de 0 à 3 un exemplaire du graphe H$_{n-1}$ calculé au rang précédent, après lui avoir fait subir une homothétie de rapport 1/2, mais de façon que, pour i variant de 0 à 2, le point final du graphe H$_{n-1}$ disposé dans le carré i soit le plus proche possible du point initial du graphe H$_{n-1}$ disposé dans le carré i+1. Il suffit pour cela d'effectuer une symétrie par rapport à la diagonale ascendante dans le carré numéroté 0, et une symétrie par rapport à la diagonale descendante dans le carré numéroté 3. Ainsi, à l'étape n= 2, le sens de parcours dans chaque sous-carré de l'étape 1 est comme suit :
| 1 | 2 | 1 | 2 |
| 0 | 3 | 0 | 3 |
| 3 | 2 | 1 | 0 |
| 0 | 1 | 2 | 3 |
    Le point initial du graphe H$_n$ ainsi obtenu est le point initial du graphe H$_{n-1}$ du carré 0 en bas à gauche, et le point final du graphe H$_n$ est le point final du graphe H$_{n-1}$ du carré 3, en bas à droite. Les parties de H$_n$ contenues dans chacun des 4$^n$ petits carrés de côté 1/2$^n$ par ordre de parcours sont les images successives par la fonction f$_n$ de chacun des intervalles successifs de longueur 1/4$^n$ subdivisant $[0,1]$.
En raison de la définition locale des graphes H$_n$, la suite de fonctions continues (f$_n$) est uniformément de Cauchy, donc converge uniformément vers une fonction continue f dont le graphe est la courbe de Hilbert. Ce graphe est dense dans le carré $[0,1]\times [0,1]$. Il est de plus compact comme image continue du compact [0,1], donc c'est un fermé dense de $[0,1]\times [0,1]$, donc il est égal à $[0,1]\times [0,1]$. f est une application surjective. Elle n'est dérivable en aucun point.
On peut montrer par récurrence que les graphes H$_n$, et donc la courbe de Hilbert par passage à la limite, sont symétriques par rapport à la droite d'équation x = 1/2.

## Définition récursive

Le paramétrage f(t) = (x(t), y(t)) de la fonction de Hilbert précédemment définie vérifie, compte tenu des symétries de la construction :
       pour $t\in [0,1/4],x(t)={\frac {y(4t)}{2}},y(t)={\frac {x(4t)}{2}}$
       pour $t\in [1/4,1/2],x(t)={\frac {x(4t-1)}{2}},y(t)={\frac {1+y(4t-1)}{2}}$
       pour $t\in [1/2,3/4],x(t)={\frac {1+x(4t-2)}{2}},y(t)={\frac {1+y(4t-2)}{2}}$
       pour $t\in [3/4,1],x(t)={\frac {2-y(4t-3)}{2}},y(t)={\frac {1-x(4t-3)}{2}}$
En outre f(0) = (0, 0) et f(1) = (1, 0).
On peut aussi traduire ces relations comme suit. Posons :
       S$_0$ la symétrie par rapport à la droite y = x
       S$_1$ la translation de vecteur (0, 1)
       S$_2$ la translation de vecteur (1,1)
       S$_3$ la symétrie par rapport à la droite y = -x, composée avec la translation de vecteur (2,1).
Alors, si $t=0,u_{1}u_{2}\cdots u_{n}\cdots =\sum _{n=0}^{\infty }{\frac {u_{n}}{4^{n}}}$ où les u$_n$ sont les chiffres en base 4 de t, on a :
       $f(t)={\frac {1}{2}}S_{u_{1}}(f(0,u_{2}\cdots u_{n}\cdots ))$
et en itérant :
       $f(t)={\frac {1}{2^{n}}}S_{u_{1}}S_{u_{2}}\cdots S_{u_{n}}(f(0,u_{n}\cdots ))$
En particulier, si t est un réel ayant un nombre fini n de chiffres en base 4 ($t=0,u_{1}u_{2}\cdots u_{n}$), on a :
       $f(t)={\frac {1}{2^{n}}}S_{u_{1}}S_{u_{2}}\cdots S_{u_{n}}(f(0))={\frac {1}{2^{n}}}S_{u_{1}}S_{u_{2}}\cdots S_{u_{n}}(0,0)$
On peut ainsi calculer facilement la valeur de n'importe quelle quantité $f({\frac {k}{4^{n}}})$ et plus spécialement les $f({\frac {2k-1}{2\times 4^{n}}})=f({\frac {4k-2}{4^{n+1}}})$, qui donnent les coordonnées des centres des petits carrés lorsque k varie de 1 à 4$^n$.

## Construction par approximations discrètes

On peut déterminer directement par récurrence les coordonnées des sommets du graphe H$_n$. Une translation sera effectuée pour que les coordonnées du sommet initial soient ramenées en (0,0) (et non au centre d'un petit carré). Nous continuerons néanmoins à désigner ce graphe translaté par H$_n$. On utilise pour cela une variable auxiliaire a indiquant l'orientation du déplacement, et pouvant prendre les valeurs 0, 1, 2, 3. L'orientation donnée par a correspondra aux quatre sens de parcours possibles suivants du graphe H$_1$ ou de ses symétrisés :
On se donne également trois matrices :
    $X={\begin{pmatrix}0&0&1&1\\1&0&0&1\\1&1&0&0\\0&1&1&0\end{pmatrix}}\!,\,Y={\begin{pmatrix}0&1&1&0\\1&1&0&0\\1&0&0&1\\0&0&1&1\end{pmatrix}}\!,\;A={\begin{pmatrix}3&0&0&1\\2&1&1&0\\1&2&2&3\\0&3&3&2\end{pmatrix}}\;\;{\begin{matrix}{\begin{array}{ll}\leftarrow &0=a\\\leftarrow &1=a\\\leftarrow &2=a\\\leftarrow &3=a\end{array}}\end{matrix}}$
Les indices de lignes varient de 0 à 3 (et non de 1 à 4 comme usuellement) et ces indices correspondent à des valeurs prises par a. Les indices de colonnes varient également de 0 à 3 et correspondent à des valeurs prises par les chiffres en base 4 d'un paramètre t donné. Les éléments de X seront les abscisses et ceux de Y les ordonnées d'un sommet que l'on cherche à calculer ; les éléments de A donneront les diverses orientations à suivre au cours du calcul.
À l'étape n, le graphe (translaté de) H$_n$ comporte 4$^n$ sommets. Pris dans l'ordre de parcours, ils seront associés aux 4$^n$ éléments t de $[0,1[$ dont la décomposition en base 4 comporte exactement n chiffres (y compris éventuellement des 0 finaux) :
    $t_{n}=0.u_{1}u_{2}\cdots u_{n}=\sum _{i=1}^{n}{\frac {u_{i}}{4^{i}}}$, $u_{i}\in \{0,1,2,3\}$.
Soit donc $t_{n}$ un tel nombre. Les coordonnées du sommet $M_{n}$ du graphe H$_n$ correspondant à $t_{n}$ peuvent être calculées par récurrence sur k variant de 0 à n, à partir des coordonnées du sommet $M_{k}$ du graphe H$_k$ correspondant au nombre $t_{k}=0.u_{1}u_{2}\cdots u_{k}$. Désignons par $(x_{k},y_{k})$ les coordonnées de $M_{k}$, et soit $a_{k}$ la valeur du paramètre qui donne l'orientation à adopter pour construire les quatre points du graphe H$_{k+1}$ issus de $M_{k}$ (dont le sommet $M_{k+1}$ qui correspondant à $t_{k+1}$.
Pour k = 0, le graphe H$_0$ est réduit au point (0,0) et l'orientation adoptée pour construire H$_1$ correspond à a = 0. On a donc initialement :
    $x_{0}=0,\,y_{0}=0,\,a_{0}=0$
Pour k variant de 1 à n, on définit ensuite par récurrence les suites :
    $x_{k}=x_{k-1}+{\frac {1}{2^{k}}}X_{a_{k-1},\,u_{k}}$ $y_{k}=y_{k-1}+{\frac {1}{2^{k}}}Y_{a_{k-1},\,u_{k}}$ $a_{k}=A_{a_{k-1},\,u_{k}}$
On vérifiera en effet que, si l'orientation en $M_{k-1}$ est donnée par la valeur de $a_{k-1}$, alors les différences entre les coordonnées des quatre points du graphe H$_k$ issus de $M_{k-1}$ et les coordonnées de $M_{k-1}$sont, au facteur 1/2$^k$ près, situés sur la ligne d'indice $a_{k-1}$ des matrices X et Y, en fonction du dernier chiffre $u_{k}$ de $t_{k}$ donnant l'indice de colonne à adopter. De plus, la nouvelle orientation à adopter au point ainsi obtenu $M_{k}$ pour construire le point $M_{k+1}$ est le nombre $a_{k}$ situé sur la ligne d'indice $a_{k-1}$ de la matrice A, là aussi en fonction du dernier chiffre $u_{k}$ de $t_{k}$.
Lorsque $t_{n}$ parcourt les valeurs depuis 0.00...0 jusqu'à 0.33...3 (avec n chiffres), les 4$^n$ sommets $M_{n}$ occupent le coin en bas en gauche des 4$^n$ petits carrés en suivant l'ordre du graphe H$_n$
Pour obtenir les centres des carrés, il suffit d'ajouter ${\frac {1}{2^{n+1}}}$ à chaque coordonnée de chaque sommet $M_{n}$.

## Généralisation en dimension supérieure

La courbe de Hilbert peut se généraliser à des dimensions supérieures. Par exemple, en dimension 3, il suffit à l'étape 1 de parcourir les huit sommets du cube d'un sommet à un sommet adjacent. Pour passer de l'étape n-1 à l'étape n, on découpe le cube unité en huit sous-cubes dans lesquels on dispose une courbe approchée de Hilbert d'ordre n-1, mais de façon que le point final de chaque graphe d'ordre n-1 soit le plus proche possible du sommet initial du graphe d'ordre n-1 suivant.
La généralisation peut aussi se faire par composition fonctionnelle. Ainsi la courbe de Hilbert de dimension 4 peut être définie par f(t) = (x(x(t)), y(x(t)), x(y(t)), y(y(t))). Cette définition peut être étendue aux dimensions qui sont des puissances de 2.

## Représentation en L-système

La courbe de Hilbert peut aussi être construite par un L-système :
    Alphabet : L, R
    Constantes : F, +, −
    Axiome : L
    Règles :
    L → –RF+LFL+FR−
    R → +LF−RFR−FL+
Ici, F signifie « avance », + signifie « à gauche 90° », et − signifie « à droite 90° ».
Butz propose un algorithme pour calculer la courbe de Hilbert en plusieurs dimensions.