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^[1].

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 ${\displaystyle 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^[1] la fonction ${\displaystyle f:[0,1]\to [0,1]^{2}}$ comme limite de fonctions ${\displaystyle f_{n}:[0,1]\to [0,1]^{2}}$ donnant les approximations successives de la courbe de Hilbert.

• À l'étape 0, le graphe H₀ se limite à un seul point, disposé au centre du carré ${\displaystyle [0,1]\times [0,1]}$. Ce point est à la fois point initial et point final de H₀. Le centre du carré de coordonnées (1/2, 1/2) est l'image par une fonction f₀ de l'intervalle ${\displaystyle [0,1]}$ tout entier.
• À l'étape 1, on coupe en quatre parties égales l'intervalle ${\displaystyle [0,1]}$ et on fait correspondre à chaque intervalle de la subdivision un quart du carré initial. Plus précisément, l'intervalle ${\displaystyle [0,1/4]}$ est associé au sous-carré ${\displaystyle [0,1/2]\times [0,1/2]}$ ; l'intervalle ${\displaystyle [1/4,1/2]}$ est associé au sous-carré ${\displaystyle [0,1/2]\times [1/2,1]}$ ; l'intervalle ${\displaystyle [1/2,3/4]}$ est associé au sous-carré ${\displaystyle [1/2,1]\times [1/2,1]}$ ; et enfin, l'intervalle ${\displaystyle [3/4,1]}$ est associé au sous-carré ${\displaystyle [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₁. Son point initial est le point de coordonnées ${\displaystyle (1/4,1/4)}$, et son point final est le point de coordonnées ${\displaystyle (3/4,1/4)}$. C'est l'arc paramétré par une fonction f₁ qui envoie l'intervalle [0, 1/4] sur la partie de H₁ contenue dans le carré 0, l'intervalle ${\displaystyle [1/4,1/2]}$ sur la partie de H₁ contenue dans le carré 1, l'intervalle ${\displaystyle [1/2,3/4]}$ sur la partie de H₁ contenue dans le carré 2, et l'intervalle ${\displaystyle [3/4,1]}$ sur la partie de H₁ 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ⁿ petits carrés de côté 1/2ⁿ par ordre de parcours sont les images successives par la fonction f_n de chacun des intervalles successifs de longueur 1/4ⁿ subdivisant ${\displaystyle [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é ${\displaystyle [0,1]\times [0,1]}$. Il est de plus compact comme image continue du compact [0,1], donc c'est un fermé dense de ${\displaystyle [0,1]\times [0,1]}$, donc il est égal à ${\displaystyle [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 ${\displaystyle t\in [0,1/4],x(t)={\frac {y(4t)}{2}},y(t)={\frac {x(4t)}{2}}}$

pour ${\displaystyle t\in [1/4,1/2],x(t)={\frac {x(4t-1)}{2}},y(t)={\frac {1+y(4t-1)}{2}}}$

pour ${\displaystyle t\in [1/2,3/4],x(t)={\frac {1+x(4t-2)}{2}},y(t)={\frac {1+y(4t-2)}{2}}}$

pour ${\displaystyle 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₀ la symétrie par rapport à la droite y = x

S₁ la translation de vecteur (0, 1)

S₂ la translation de vecteur (1,1)

S₃ la symétrie par rapport à la droite y = -x, composée avec la translation de vecteur (2,1).

Alors, si ${\displaystyle 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 :

${\displaystyle f(t)={\frac {1}{2}}S_{u_{1}}(f(0,u_{2}\cdots u_{n}\cdots ))}$

et en itérant :

${\displaystyle 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 (${\displaystyle t=0,u_{1}u_{2}\cdots u_{n}}$), on a :

${\displaystyle 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é ${\displaystyle f({\frac {k}{4^{n}}})}$ et plus spécialement les ${\displaystyle 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ⁿ.

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₁ ou de ses symétrisés :

On se donne également trois matrices :

${\displaystyle 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ⁿ sommets. Pris dans l'ordre de parcours, ils seront associés aux 4ⁿ éléments t de ${\displaystyle [0,1[}$ dont la décomposition en base 4 comporte exactement n chiffres (y compris éventuellement des 0 finaux) :

${\displaystyle t_{n}=0.u_{1}u_{2}\cdots u_{n}=\sum _{i=1}^{n}{\frac {u_{i}}{4^{i}}}}$, ${\displaystyle u_{i}\in \{0,1,2,3\}}$.

Soit donc ${\displaystyle t_{n}}$ un tel nombre. Les coordonnées du sommet ${\displaystyle M_{n}}$ du graphe H_n correspondant à ${\displaystyle t_{n}}$ peuvent être calculées par récurrence^[2] sur k variant de 0 à n, à partir des coordonnées du sommet ${\displaystyle M_{k}}$ du graphe H_k correspondant au nombre ${\displaystyle t_{k}=0.u_{1}u_{2}\cdots u_{k}}$. Désignons par ${\displaystyle (x_{k},y_{k})}$ les coordonnées de ${\displaystyle M_{k}}$, et soit ${\displaystyle a_{k}}$ la valeur du paramètre qui donne l'orientation à adopter pour construire les quatre points du graphe H_k+1 issus de ${\displaystyle M_{k}}$ (dont le sommet ${\displaystyle M_{k+1}}$ qui correspondant à ${\displaystyle t_{k+1}}$.

Pour k = 0, le graphe H₀ est réduit au point (0,0) et l'orientation adoptée pour construire H₁ correspond à a = 0. On a donc initialement :

${\displaystyle x_{0}=0,\,y_{0}=0,\,a_{0}=0}$

Pour k variant de 1 à n, on définit ensuite par récurrence les suites :

${\displaystyle x_{k}=x_{k-1}+{\frac {1}{2^{k}}}X_{a_{k-1},\,u_{k}}}$

${\displaystyle y_{k}=y_{k-1}+{\frac {1}{2^{k}}}Y_{a_{k-1},\,u_{k}}}$

${\displaystyle a_{k}=A_{a_{k-1},\,u_{k}}}$

On vérifiera en effet que, si l'orientation en ${\displaystyle M_{k-1}}$ est donnée par la valeur de ${\displaystyle a_{k-1}}$, alors les différences entre les coordonnées des quatre points du graphe H_k issus de ${\displaystyle M_{k-1}}$ et les coordonnées de ${\displaystyle M_{k-1}}$sont, au facteur 1/2^k près, situés sur la ligne d'indice ${\displaystyle a_{k-1}}$ des matrices X et Y, en fonction du dernier chiffre ${\displaystyle u_{k}}$ de ${\displaystyle t_{k}}$ donnant l'indice de colonne à adopter. De plus, la nouvelle orientation à adopter au point ainsi obtenu ${\displaystyle M_{k}}$ pour construire le point ${\displaystyle M_{k+1}}$ est le nombre ${\displaystyle a_{k}}$ situé sur la ligne d'indice ${\displaystyle a_{k-1}}$ de la matrice A, là aussi en fonction du dernier chiffre ${\displaystyle u_{k}}$ de ${\displaystyle t_{k}}$.

Lorsque ${\displaystyle t_{n}}$ parcourt les valeurs depuis 0.00...0 jusqu'à 0.33...3 (avec n chiffres), les 4ⁿ sommets ${\displaystyle M_{n}}$ occupent le coin en bas en gauche des 4ⁿ petits carrés en suivant l'ordre du graphe H_n

Pour obtenir les centres des carrés, il suffit d'ajouter ${\displaystyle {\frac {1}{2^{n+1}}}}$ à chaque coordonnée de chaque sommet ${\displaystyle 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^[3] :

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^[4] propose un algorithme pour calculer la courbe de Hilbert en plusieurs dimensions.

Notes et références

Voir aussi

Articles connexes

• Courbe de Lebesgue
• Courbe de Peano
• Liste de fractales par dimension de Hausdorff

Liens externes

• (en) Eric W. Weisstein, « Hilbert Curve », sur MathWorld
• (en) Plane Filling Curves sur cut-the-knot

• Portail de la géométrie