Les courbes remplissantes expliquées
Une ligne a une dimension et un carré en a deux : il semble donc évident qu'une ligne ne pourra jamais recouvrir un carré. En 1890, Giuseppe Peano a montré que c'est possible : il existe une courbe continue qui passe par tous les points d'un carré. Cette découverte a obligé les mathématiciens à repenser ce que sont une courbe et une dimension, et, un siècle plus tard, ces mêmes courbes maintiennent en ordre les données des cartes et des images à l'intérieur des ordinateurs.
Autant de points qu'un carré
En 1877, Georg Cantor a démontré qu'un segment de droite a exactement autant de points qu'un carré : chaque point du carré peut être associé à un point de la ligne qui lui est propre. Il a écrit à Richard Dedekind : « Je le vois, mais je ne le crois pas. » Mais la correspondance de Cantor saute en tous sens ; elle déchire la ligne jusqu'à la réduire en poussière. Restait à savoir si une ligne pouvait recouvrir un carré sans être déchirée, c'est-à-dire de façon continue.
La courbe de Peano
En 1890, le mathématicien italien Giuseppe Peano a donné la réponse : oui. Il a décrit, uniquement par des formules et sans un seul dessin, une courbe continue qui passe par tous les points du carré unité. Sa construction découpe le carré en 9 carrés plus petits, les parcourt en décrivant des lacets en S, puis recommence à l'intérieur de chacun d'eux, encore et encore.
Le dessin de Hilbert
Un an plus tard, David Hilbert a publié une version plus simple, accompagnée du dessin qui a rendu l'idée visible. Découpez le carré en 4 et reliez les centres par une seule ligne coudée. Découpez ensuite chaque petit carré en 4 et recommencez, en tournant les petites copies de façon que la ligne se poursuive de l'une à la suivante. La courbe de niveau n visite 4ⁿ cases ; ce qui remplit le carré, c'est la limite de tous les niveaux. En 1900, Eliakim Hastings Moore a proposé une variante qui se termine là où elle commence, une boucle fermée.
Pourquoi la limite fonctionne
Suivez un point de la ligne, par exemple celui qui se trouve au tiers du parcours. Au niveau 1, il est dans l'une des 4 cases. À chaque niveau suivant il se déplace, mais il reste à l'intérieur de cette case, puis à l'intérieur d'un quart de celle-ci, et ainsi de suite : à l'intérieur d'une case dont le côté diminue de moitié à chaque fois. Sa position se stabilise donc, et il en va de même pour chaque point de la ligne. La limite est une courbe continue. Et comme chaque niveau visite chaque case d'une grille toujours plus fine, la courbe limite s'approche d'aussi près qu'on veut de chaque point du carré et, étant continue, l'atteint.
Elle ne peut pas être injective
Une courbe remplissante a un prix à payer. En 1879, Eugen Netto a démontré qu'on ne peut pas appliquer une ligne sur un carré de façon à la fois continue et injective. La courbe doit donc passer par certains points plus d'une fois ; la courbe de Hilbert touche certains points jusqu'à quatre fois. De plus, elle n'est lisse nulle part : elle n'a de tangente en aucun point.
Longueur et dimension
Le niveau n de la courbe de Hilbert a une longueur de 2ⁿ − 2⁻ⁿ fois le côté du carré, soit environ le double du niveau précédent. La longueur n'a pas de limite, et pourtant la courbe ne sort jamais du carré. Une courbe faite de 4 copies d'elle-même réduites de moitié a pour dimension log 4 / log 2 = 2, la dimension du carré qu'elle remplit. La courbe de Peano compte 9 copies réduites au tiers : log 9 / log 3 = 2 également.
Garder les voisins ensemble
La courbe de Hilbert possède une propriété qui la rend utile : des points proches sur la ligne se retrouvent proches dans le carré. La réciproque ne peut pas toujours être vraie : deux cases voisines peuvent être très éloignées sur la ligne. Les ordinateurs utilisent la courbe pour ranger des données à deux dimensions, comme des tuiles cartographiques, des pixels ou des lieux du globe, dans un ordre à une dimension qui garde la plupart des voisins proches les uns des autres. L'ordre Z, décrit par Guy Morton chez IBM en 1966, remplit le même rôle en entrelaçant les bits des deux coordonnées. Il est plus rapide à calculer, mais il garde moins bien les voisins ensemble, parce qu'il fait des sauts.
Le flowsnake de Gosper et la pointe de flèche de Sierpiński
Toutes les courbes remplissantes ne remplissent pas un carré. La courbe de Bill Gosper, de 1973, connue sous le nom de flowsnake depuis que Martin Gardner a écrit à son sujet en 1976, parcourt une grille de triangles à raison de sept segments pour un. Elle remplit l'île de Gosper, une forme au littoral fractal, dont sept copies s'assemblent pour en former une plus grande. La courbe en pointe de flèche de Wacław Sierpiński lui ressemble à première vue, mais elle ne compte que trois morceaux par segment, deux fois plus courts, et ne remplit donc rien : elle dessine le triangle de Sierpiński, de dimension log 3 / log 2 ≈ 1,585.
À vous de jouer
Ouvrez l'explorateur de courbes remplissantes et appuyez sur Lancer pour voir un crayon tracer chaque niveau de la courbe de Hilbert du début à la fin. Passez aux lacets en S de Peano, à la boucle fermée de Moore, à l'ordre Z et à ses sauts, au flowsnake de Gosper et à la pointe de flèche. Placez le crayon n'importe où sur la courbe, ou sur la droite numérique sous l'image, pour voir quel pas tombe dans quelle case, et affichez le niveau précédent pour voir comment chaque pas devient un coude entier.
Questions fréquemment posées
Qui a découvert la première courbe remplissante ?
Giuseppe Peano, en 1890. C'est pourquoi les courbes remplissantes sont aussi appelées courbes de Peano. La courbe de David Hilbert, de 1891, est la plus connue, car Hilbert a été le premier à donner un dessin de la construction.
Une courbe remplissante est-elle une fractale ?
Elle est construite comme une fractale, à partir de copies plus petites d'elle-même. Mais sa dimension fractale est 2, un nombre entier, car la courbe achevée recouvre une aire. La courbe en pointe de flèche de Sierpiński, de dimension environ 1,585, est une fractale au sens habituel.
Quelle est la longueur de la courbe de Hilbert ?
Le niveau n mesure 2ⁿ − 2⁻ⁿ fois le côté du carré : 1,5 au niveau 1, 15,94 au niveau 4 et presque 256 au niveau 8. La courbe limite est infiniment longue.
Combien de niveaux l'explorateur peut-il tracer ?
Jusqu'à 8 niveaux pour la courbe de Hilbert, la courbe de Moore et l'ordre Z, soit une grille de 256 sur 256 cases ; 5 pour la courbe de Peano (243 sur 243 cases) et la courbe de Gosper (16 807 segments) ; et 10 pour la pointe de flèche de Sierpiński (59 049 segments).
Prêt à l'essayer ?
Ouvrez PictorX dans votre navigateur – aucune installation, aucune carte de crédit requise pour démarrer.
Ouvrir l'explorateur de courbes remplissantes