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 Modèle:Math (la courbe approchée continue obtenue à la Modèle:Math-ième itération) est $2^{n} - \frac{1}{2^{n}}$ ; elle croit donc exponentiellement avec Modèle:Math.

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 Modèle:Math 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 Modèle:Math. Le centre du carré de coordonnées (1/2, 1/2) est l'image par une fonction Modèle:Math 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 Modèle:Math. 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 Modèle:Math qui envoie l'intervalle [0, 1/4] sur la partie de Modèle:Math contenue dans le carré 0, l'intervalle

[1 / 4, 1 / 2]

sur la partie de Modèle:Math contenue dans le carré 1, l'intervalle

[1 / 2, 3 / 4]

sur la partie de Modèle:Math contenue dans le carré 2, et l'intervalle

[3 / 4, 1]

sur la partie de Modèle:Math 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 Modèle:Math 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 Modèle:Math disposé dans le carré i soit le plus proche possible du point initial du graphe Modèle:Math 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 Modèle:Math ainsi obtenu est le point initial du graphe Modèle:Math du carré 0 en bas à gauche, et le point final du graphe Modèle:Math est le point final du graphe Modèle:Math du carré 3, en bas à droite. Les parties de Modèle:Math contenues dans chacun des Modèle:Math petits carrés de côté Modèle:Math par ordre de parcours sont les images successives par la fonction Modèle:Math de chacun des intervalles successifs de longueur Modèle:Math subdivisant

[0, 1]

.

En raison de la définition locale des graphes Modèle:Math, la suite de fonctions continues (Modèle:Math) 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 Modèle:Math, 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 (4 t)}{2}, y (t) = \frac{x (4 t)}{2}

pour

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

pour

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

pour

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

En outre f(0) = (0, 0) et f(1) = (1, 0).

On peut aussi traduire ces relations comme suit. Posons :

Modèle:Math la symétrie par rapport à la droite y = x

Modèle:Math la translation de vecteur (0, 1)

Modèle:Math la translation de vecteur (1,1)

Modèle:Math 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} \dots u_{n} \dots = \sum_{n = 0}^{\infty} \frac{u_{n}}{4^{n}}$ où les Modèle:Math sont les chiffres en base 4 de t, on a :

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

et en itérant :

f (t) = \frac{1}{2^{n}} S_{u_{1}} S_{u_{2}} \dots S_{u_{n}} (f (0, u_{n} \dots))

En particulier, si t est un réel ayant un nombre fini n de chiffres en base 4 ( $t = 0, u_{1} u_{2} \dots u_{n}$ ), on a :

f (t) = \frac{1}{2^{n}} S_{u_{1}} S_{u_{2}} \dots S_{u_{n}} (f (0)) = \frac{1}{2^{n}} S_{u_{1}} S_{u_{2}} \dots 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{2 k - 1}{2 \times 4^{n}}) = f (\frac{4 k - 2}{4^{n + 1}})$ , qui donnent les coordonnées des centres des petits carrés lorsque k varie de 1 à Modèle:Math.

Construction par approximations discrètes

On peut déterminer directement par récurrence les coordonnées des sommets du graphe Modèle:Math. 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 Modèle:Math. 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 Modèle:Math 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{matrix} 0 & 0 & 1 & 1 \\ 1 & 0 & 0 & 1 \\ 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 \end{matrix}), Y = (\begin{matrix} 0 & 1 & 1 & 0 \\ 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 1 \\ 0 & 0 & 1 & 1 \end{matrix}), A = (\begin{matrix} 3 & 0 & 0 & 1 \\ 2 & 1 & 1 & 0 \\ 1 & 2 & 2 & 3 \\ 0 & 3 & 3 & 2 \end{matrix}) \begin{matrix} \begin{matrix} \leftarrow & 0 = a \\ \leftarrow & 1 = a \\ \leftarrow & 2 = a \\ \leftarrow & 3 = a \end{matrix} \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) Modèle:Math comporte Modèle:Math sommets. Pris dans l'ordre de parcours, ils seront associés aux Modèle:Math é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} \dots 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 Modèle:Math 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 Modèle:Math correspondant au nombre $t_{k} = 0 . u_{1} u_{2} \dots 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 Modèle:Math issus de $M_{k}$ (dont le sommet $M_{k + 1}$ qui correspondant à $t_{k + 1}$ .

Pour k = 0, le graphe Modèle:Math est réduit au point (0,0) et l'orientation adoptée pour construire Modèle:Math 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 Modèle:Math issus de $M_{k - 1}$ et les coordonnées de $M_{k - 1}$ sont, au facteur Modèle:Math 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 Modèle:Math sommets $M_{n}$ occupent le coin en bas en gauche des Modèle:Math petits carrés en suivant l'ordre du graphe Modèle:Math

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

Modèle:Références

Voir aussi

Modèle:Autres projets

Articles connexes

Liens externes

Modèle:Palette Modèle:Portail

↑ ^1,0 ^1,1 et ^1,2 Modèle:Article.
↑ 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, Modèle:P.).
↑ Modèle:Ouvrage.
↑ Modèle:Article.

[Hilbert-1] 1,0 ^1,1 et ^1,2 Modèle:Article.

[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, Modèle:P.).

[3] Modèle:Ouvrage.

[4] Modèle:Article.

[1]

[2]

[3]

[4]

Courbe de Hilbert

Sommaire

Construction géométrique

Définition récursive

Construction par approximations discrètes

Généralisation en dimension supérieure

Représentation en L-système

Notes et références

Voir aussi

Articles connexes

Liens externes

Menu de navigation

Courbe de Hilbert

Construction géométrique

Définition récursive

Construction par approximations discrètes

Généralisation en dimension supérieure

Représentation en L-système

Notes et références

Voir aussi

Articles connexes

Liens externes

Menu de navigation

Rechercher