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 (la courbe approchée continue obtenue à la n-ième itération) est ; 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é. Hilbert définit la fonction comme limite de fonctions 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é . 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 tout entier. À l'étape 1, on coupe en quatre parties égales l'intervalle et on fait correspondre à chaque intervalle de la subdivision un quart du carré initial. Plus précisément, l'intervalle est associé au sous-carré ; l'intervalle est associé au sous-carré ; l'intervalle est associé au sous-carré ; et enfin, l'intervalle est associé au sous-carré . Ainsi, le parcours des quatre sous-carrés se fait dans l'ordre suivant : 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 , et son point final est le point de coordonnées . 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 sur la partie de H contenue dans le carré 1, l'intervalle sur la partie de H contenue dans le carré 2, et l'intervalle 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é.