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 $n\to \infty$ 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 $n\to \infty$ ) est 2.

La longueur euclidienne de la courbe $S_{n}$ à l'itération n est

{\begin{aligned}l_{n}&={2 \over 3}(1+{\sqrt {2}})2^{n}-{1 \over 3}(2-{\sqrt {2}}){1 \over 2^{n}},\\&={\frac {2^{7/4}}{3}}\sinh \left(n\ln(2)+\mathrm {argsinh} \left({\frac {3}{2^{5/4}}}\right)\right)\end{aligned}}

c'est-à-dire qu'il croît de façon exponentielle avec $n$ au-delà de toute limite, alors que la limite pour $n\to \infty$ de la zone délimitée par $S_{n}$ est $5/12\,$ celle du carré (en métrique euclidienne).

Courbe de Sierpiński ("flocon de neige carré de Sierpinski" ) du premier ordre

Utilisations de la courbe[modifier | modifier le code]

La 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[modifier | modifier le code]

La 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[modifier | modifier le code]

La 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[modifier | modifier le code]

La 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[modifier | modifier le code]

Courbe de Hilbert
Flocon de Koch
Graphe de Moore
Polygone de Murray
Courbe de Peano
Liste des fractales par dimension de Hausdorff
Algorithme récursif
Triangle de Sierpinski

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

(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, n^o 4,‎ 1989, p. 719–737 (DOI 10.1145/76359.76361)
↑ Bartholdi, « Some combinatorial applications of spacefilling curves » [archive du 3 août 2012], 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 | modifier le code]

H.-O. Peitgen, H. Jürgens et D. Saupe, Chaos and Fractals: New Frontiers of Science, Springer, 2013 (ISBN 978-1-4757-4740-9, lire en ligne)
Roger T. Stevens, Fractal Programming in C, M&T Books, 1989 (ISBN 978-1-55851-037-1, lire en ligne)

Portail de la géométrie

[Platzman89-1] Platzman et Bartholdi, « Spacefilling curves and the planar traveling salesman problem », Journal of the Association for Computing Machinery, vol. 36, n^o 4,‎ 1989, p. 719–737 (DOI 10.1145/76359.76361)

[BartholdiURL-2] Bartholdi, « Some combinatorial applications of spacefilling curves » [archive du 3 août 2012], Georgia Institute of Technology

[1]

[2]

v · m Fractales
Caractéristiques	Dimensions fractales Assouad Minkowski-Bouligand Hausdorff Récursivité Autosimilarité
Système de fonctions itérées	Fougère de Barnsley Ensemble de Cantor Flocon de Koch Éponge de Menger Arbre de Pythagore Tapis de Sierpiński Triangle de Sierpiński Fractale de Vicsek Courbes Blanc-manger Cesàro De Rahm Dragon Dragon d'or Gosper Hilbert Koch Lebesgue Lévy Courbe remplissante courbe de Peano remplissant le flocon de Koch Sierpiński
Attracteur étrange	Multifractale
L-Système	Canopée fractale Courbe remplissante Arbre en H
Création	Burning ship Julia Dendrite Lapin de Douady Liapounov Mandelbrot Multibrot Newton Tricorne (en) Mandelbox Mandelbulb
Techniques de rendu photoréaliste	Buddhabrot Piège orbital (en) Trognon de Pickover (en)
Fractales aléatoires	Mouvement brownien Terrain fractal Théorie de la percolation Chemin auto-évitant
Personnalités	Georg Cantor Felix Hausdorff Gaston Julia Helge von Koch Paul Lévy Alexandre Liapounov Benoît Mandelbrot Lewis Fry Richardson Wacław Sierpiński
Liste de fractales par dimension de Hausdorff Art fractal La Théorie du chaos (livre)