Courbe de Sierpiński
Les courbes de Sierpiński sont une suite définie de manière récursive de courbes fractales planes continues fermées découverte par Wacław Sierpiński, qui, à la limite remplissent complètement le carré unité : ainsi leur courbe limite, également appelée courbe de Sierpiński, est un exemple de courbe remplissante.
Parce que la courbe de Sierpiński remplit l'espace, sa dimension de Hausdorff (à la limite ) est 2.
La longueur euclidienne de la courbe à l'itération n est
c'est-à-dire qu'il croît de façon exponentielle avec au-delà de toute limite, alors que la limite pour de la zone délimitée par est celle du carré (en métrique euclidienne).
Utilisations de la courbe
modifierLa courbe de Sierpiński est utile dans plusieurs applications pratiques car elle est plus symétrique que les autres courbes de remplissage d'espace couramment étudiées. Par exemple, elle a été utilisée comme base pour la construction rapide d'une solution approximative au problème du voyageur de commerce (qui demande la suite la plus courte d'un ensemble de points donné) : l'heuristique consiste simplement à visiter les points dans la même suite, tels qu'ils apparaissent sur la courbe de Sierpiński[1]. Pour ce faire, il faut deux étapes : un calcul de l'image inverse de chaque point à visiter ; puis un tri des valeurs. Cette idée a été utilisée pour créer des systèmes de routage pour les véhicules commerciaux basés uniquement sur les fichiers de cartes Rolodex[2].
Une courbe remplissante plane est une application continue de l'intervalle unité vers un carré unitaire et donc une application (pseudo) inverse envoie le carré unité vers l'intervalle unité. Une façon de construire un pseudo-inverse est la suivante : on envoie le coin inférieur gauche (0 ; 0) du carré unité sur le point 0 (et 1) de l'intervalle, puis le coin supérieur gauche (0 ; 1) sur le point 0,25 de l'intervalle, le coin supérieur droit (1 ; 1) sur 0,5, et le coin inférieur droit (1 ; 0) sur 0,75. L'image inverse des points intérieurs est calculée en tirant parti de la structure récursive de la courbe.
Représentation selon le système Lindenmayer
modifierLa courbe de Sierpiński peut être exprimée par un système de réécriture comme le L-système.
- Alphabet : F, G, X
- Constantes : F, G, +, −
- Axiome : F − − XF − − F − − XF
- Règles de fabrication :
- X → XF+G+XF − − F − − XF+G+X
- Angle : 45
Ici, F et G signifient tous deux « avancer », + signifie « tourner à gauche de 45° » et − signifie « tourner à droite de 45° ». La courbe est généralement dessinée avec des longueurs différentes pour F et G.
La courbe carrée de Sierpiński peut être exprimée de la même manière :
- Alphabet : F, X
- Constantes : F, +, −
- Axiome : F+XF+F+XF
- Règles de fabrication :
- X → XF − F+F − XF+F+XF − F+F − X
- Angle : 90
Courbe en pointe de flèche
modifierLa courbe en pointe de flèche de Sierpiński est une courbe fractale d'apparence similaire et identique en limite au triangle de Sierpiński.
La courbe en pointe de flèche de Sierpiński dessine un triangle équilatéral avec des trous triangulaires à intervalles égaux. Il peut être décrit avec deux règles de production de substitution : (A → BAB) et (B → A+B+A). A et B se reproduisent et en bas font la même chose : tracer une ligne. Plus et moins (+ et -) signifient un virage de 60 degrés à gauche ou à droite. Le point final de la courbe en pointe de flèche de Sierpiński est toujours le même à condition qu'on réitère un nombre pair de fois et qu'on réduise de moitié la longueur de la ligne à chaque itération. Si on revient à une profondeur impaire (l'ordre est impair), on se retrouve alors tourné de 60 degrés, à un point différent du triangle.
Une constriction alternative est donnée dans l'article sur la courbe de De Rham : on utilise la même technique que les courbes de De Rham, mais au lieu d'utiliser un développement binaire (base-2), on utilise un développement ternaire (base-3).
Représentation selon le système de Lindenmayer
modifierLa courbe en pointe de flèche de Sierpiński peut être exprimée par un L-système.
- Alphabet : X, Y
- Constantes : F, +, −
- Axiome : XF
- Règles de fabrication :
- X → YF + XF + Y
- Y → XF − YF − X
Ici, F signifie « avancer », + signifie « tourner à gauche de 60° » et − signifie « tourner à droite de 60° » (voir graphique de la tortue ).
Voir également
modifierRéférences
modifier- (en) Cet article est partiellement ou en totalité issu de l’article de Wikipédia en anglais intitulé « Sierpiński curve » (voir la liste des auteurs).
- Platzman et Bartholdi, « Spacefilling curves and the planar traveling salesman problem », Journal of the Association for Computing Machinery, vol. 36, no 4, , p. 719–737 (DOI 10.1145/76359.76361)
- Bartholdi, « Some combinatorial applications of spacefilling curves » [archive du ], Georgia Institute of Technology
- (en) Eric W. Weisstein, « Sierpiński Curve », sur MathWorld
- (en) Eric W. Weisstein, �� Sierpiński Arrowhead Curve », sur MathWorld
Bibliographie
modifier- H.-O. Peitgen, H. Jürgens et D. Saupe, Chaos and Fractals: New Frontiers of Science, Springer, (ISBN 978-1-4757-4740-9, lire en ligne)
- Roger T. Stevens, Fractal Programming in C, M&T Books, (ISBN 978-1-55851-037-1, lire en ligne )