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 $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 $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 :

Codage des orientations possibles utilisées pour la construction de la courbe de Hilbert.

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^[2] 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^[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

↑ ^{a b et c} (de) D. Hilbert, « Über die stetige Abbildung einer Linie auf ein Flächenstück », Math. Ann., vol. 38,‎ 1891, p. 459-460 (lire en ligne).
↑ Theodore Bially. Space-filling curves: Their generation and their application to bandwidth reduction. IEEE Transactions on Information Theory, IT-15(6):658–664, 1969. (Cité d'après Jonathan Lawder: Techniques for Mapping to and from Space-filling Curves, 1999, p. 58).
↑ (en) Heinz-Otto Peitgen (en) et Dietmar Saupe (éds.), The Science of Fractal Images, Springer, 2012 (lire en ligne), p. 278.
↑ (en) Arthur Butz, « Alternative algorithm for Hilbert’s space filling curve », IEEE Trans. On Computers, vol. 20,‎ avril 1971, p. 424-442.

Voir aussi

Sur les autres projets Wikimedia :

Courbe de Hilbert, sur Wikimedia Commons

Articles connexes

Liens externes

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

Portail de la géométrie

[Hilbert-1] {a b et c} (de) D. Hilbert, « Über die stetige Abbildung einer Linie auf ein Flächenstück », Math. Ann., vol. 38,‎ 1891, p. 459-460 (lire en ligne).

[2] Theodore Bially. Space-filling curves: Their generation and their application to bandwidth reduction. IEEE Transactions on Information Theory, IT-15(6):658–664, 1969. (Cité d'après Jonathan Lawder: Techniques for Mapping to and from Space-filling Curves, 1999, p. 58).

[3] (en) Heinz-Otto Peitgen (en) et Dietmar Saupe (éds.), The Science of Fractal Images, Springer, 2012 (lire en ligne), p. 278.

[4] (en) Arthur Butz, « Alternative algorithm for Hilbert’s space filling curve », IEEE Trans. On Computers, vol. 20,‎ avril 1971, p. 424-442.

[1]

[2]

[3]

[4]

v · m Fractales
Caractéristiques	Dimensions fractales Assouad Minkowski-Bouligand Hausdorff Récursivité Autosimilarité
Système de fonctions itérées	Fougère de Barnsley Ensemble de Cantor Flocon de Koch Éponge de Menger Arbre de Pythagore Tapis de Sierpiński Triangle de Sierpiński Fractale de Vicsek Courbes Blanc-manger Cesàro De Rahm Dragon Dragon d'or Gosper Hilbert Koch Lebesgue Lévy Courbe remplissante courbe de Peano remplissant le flocon de Koch Sierpiński
Attracteur étrange	Multifractale
L-Système	Canopée fractale Courbe remplissante Arbre en H
Création	Burning ship Julia Dendrite Lapin de Douady Liapounov Mandelbrot Multibrot Newton Tricorne (en) Mandelbox Mandelbulb
Techniques de rendu photoréaliste	Buddhabrot Piège orbital (en) Trognon de Pickover (en)
Fractales aléatoires	Mouvement brownien Terrain fractal Théorie de la percolation Chemin auto-évitant
Personnalités	Georg Cantor Felix Hausdorff Gaston Julia Helge von Koch Paul Lévy Alexandre Liapounov Benoît Mandelbrot Lewis Fry Richardson Wacław Sierpiński
Liste de fractales par dimension de Hausdorff Art fractal La Théorie du chaos (livre)