Courbe de Hilbert

Un article de Wikipédia, l'encyclopédie libre.
Sauter à la navigation Sauter à la recherche
Les 6 premières étapes de la courbe de Hilbert (les trois premières sont exactement celles dessinées par Hilbert dans son article)[1].

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 Hn (la courbe continue obtenue à la n-ième itération) est  ; elle croit donc exponentiellement avec n.

Pour les 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é.

Surjectivité et continuité[modifier | modifier le code]

Hilbert définit[1] la fonction comme limite uniforme des fonctions continues définissant les approximations successives de la courbe de Hilbert. Ces fonctions peuvent être définies par récurrence sur n[2].

Elles ont des propriétés de symétrie :

Si 0 < t < 1, et .

La convergence uniforme des fonctions fn vers la fonction f tient essentiellement à la localité des courbes de Hilbert.

L'application f, en tant que limite uniforme de fonctions continues, est continue.

Comme toute fonction continue, l'image du compact [0, 1] par f est un compact. Notamment, c'est un fermé. Par ailleurs, f([0, 1]) est dense dans [0, 1]2. C'est donc [0, 1]2 tout entier.

Construction par approximations discrètes[modifier | modifier le code]

Soit   et   .

Pour obtenir la même vitesse dans les deux dimensions comme dans l'une[pas clair] on divise l'intervalle en « pièces » égales, on représente le paramètre dans le système quaternaire

avec et  

et l'on demande que deux intervalles voisins sont projetés sur deux carrés voisins. Ensuite, les fonctions discrètes

exprimant les coordonnées « désignantes » un carré et ainsi « successivement approximantes la courbe de Hilbert » peuvent être définies par récurrence[3] sur à partir des fonctions et  :

et  
et  

en utilisant les trois matrices de dimension (4,4) :

De cette construction il est clair que projette tout des 4 intervalles avec sur un des 4 carrés qui sont contenus dans le carré précédent et le remplissent. De plus, si le chiffre advance par 1, on voit immédiatement que exactement 1 des 2 chiffres ou change aussi. Donc le parcours du paramètre à travers les intervalles entraîne un parcours à travers les carrés, et toujours de carré à carré traversant parallèlement aux axes. Alors, les fonctions discrètes observent un voisinage consécutif des intervalles sur les carrés voisins. En même temps, elles sont bijectives sur l'image . Ainsi[précision nécessaire], l'application comme limite uniforme [Information douteuse] [?] de ces fonctions est surjective et est uniformément continue.

Si l'on prend les centres des carrés

on trouve que

et

qui est en limite

et

Représentation en L-système[modifier | modifier le code]

Courbe de Hilbert en trois dimensions.

La courbe de Hilbert peut aussi être construite par un L-système[4] :

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

Références[modifier | modifier le code]

  1. a, b et c (de) D. Hilbert, « Über die stetige Abbildung einer Linie auf ein Flächenstück », Math. Ann., vol. 38,‎ , p. 459-460 (lire en ligne).
  2. « Courbe de Hilbert », sur mathcurve.
  3. 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).
  4. (en) Heinz-Otto Peitgen (en) et Dietmar Saupe (éds.), The Science of Fractal Images, Springer, (lire en ligne), p. 278.
  5. (en) Arthur Butz, « Alternative algorithm for Hilbert’s space filling curve », IEEE Trans. On Computers, vol. 20,‎ , p. 424-442.

Voir aussi[modifier | modifier le code]

Sur les autres projets Wikimedia :

Articles connexes[modifier | modifier le code]

Liens externes[modifier | modifier le code]