Corba de Sierpiński

La corba de Sierpiński és una seqüència definida de forma recursiva d'una corba fractal contínua que en el límit $n\rightarrow \infty$ omple completament el quadrat unitari.^[1] Per tant, la corba límit és un exemple de corba de Peano, és a dir, una corba de recobriment del pla. Va ser descoberta pel matemàtic Wacław Sierpiński.^[2] La corba original a vegades també s'anomena floc de neu quadrat de Sierpiński.^[3]

Corba de Sierpinski. Es mostra la figura inicial i els ordres 1 fins al 8. El canvi de color representa la distància recorreguda per la corda.

Com que la corba té aquesta propietat de recobriment del pla, la seva dimensió de Hausdorff-Bezikóvitx al límit $n\rightarrow \infty$ és 2.

La distància euclidiana de $S_{n}$ és

l_{n}={2 \over 3}(1+{\sqrt {2}})2^{n}-{1 \over 3}(2-{\sqrt {2}}){1 \over 2^{n}}

és a dir, creix de forma accelerada amb $n$ més enllà de qualsevol límit, mentre que el límit per $n\rightarrow \infty$ de l'àrea tancada per $S_{n}$ és $5/12\,$ la del quadrat (en mètrica euclidiana).

Procediment

Formació dels quatre nous punts segons el tipus de punt inicial. Blau: amunt; vermell: dreta; taronja: avall i verd: esquerra.

Un possible procediment per obtenir la corba és mitjançant transformació de punts:

Es parteix de quatre punts, a cadascun se li assigna un tipus: amunt, dreta, avall i esquerra.
Per formar la iteració següent, cada punt és transformat a quatre punts nous, segons el seu tipus.
Finalment s'uneixen tots els punts formats per ordre en aquesta nova iteració.

També hi ha altres maneres d'obtenir la figura. Una d'elles és transformar les arestes, en aquest cas diferenciades en només dos tipus (segons si són o no diagonals), de manera que a cada tipus se li atribueix una transformació diferent.

Una altra manera d'obtenir la corba és utilitzar l'auto-similaritat del fractal de forma similar a la corba de Hilbert. Per fer-ho es divideix la graella en quadrants, i a cadascun d'ells se li col·loca la figura d'ordre anterior, amb la meitat de la mida anterior, i finalment s'uneixen de forma adequada. Tot i això, a diferència de la corba de Hilbert, la corba de Sierpiński és un circuit tancat. Per tant, és necessari aplicar les transformacions entre ordres en una versió oberta de la corba i tancar el circuit en l'últim pas, tal com succeeix en la corba de Moore.^[4]

Figura inicial
Primer ordre
Segon ordre
Tercer ordre
Quart ordre
Cinquè ordre

Pseudocodi

A continuació es mostra un exemple de pseudocodi per obtenir la corba mitjançant transformació de punts.

points = [] // Array dels punts
max_order = 8 // Nombre d'ordres a avaluar

// Punts inicials
points <- Point.new(0, -1, :top) // Amunt
points <- Point.new(1, 0, :right) // Dreta
points <- Point.new(0, 1, :bottom) // Avall
points <- Point.new(-1, 0, :left) // Esquerra

// Crear cada ordre a partir dels punts de l'anterior
for order in 1..max_order
 // Els punts actuals ja no surten al nou ordre
 current = points.clone
 points.clear
 // La distància depèn de l'ordre
 d = sd = 0.5 / (2 ** (order - 1))
 // Crear punt nou a partir de cada punt de l'ordre anterior
 for point in corrent
 px = point.x
 py = point.y
 case point.type
 when :top // Amunt
 points <- Point.new(px - d - sd, py - sd, :top)
 points <- Point.new(px - d, py, :right)
 points <- Point.new(px + d, py, :left)
 points <- Point.new(px + d + sd, py - sd, :top)
 when :right // Dreta
 points <- Point.new(px + sd, py - d - sd, :right)
 points <- Point.new(px, py - d, :bottom)
 points <- Point.new(px, py + d, :top)
 points <- Point.new(px + sd, py + d + sd, :right)
 when :bottom // Avall
 points <- Point.new(px + d + sd, py + sd, :bottom)
 points <- Point.new(px + d, py, :left)
 points <- Point.new(px - d, py, :right)
 points <- Point.new(px - d - sd, py + sd, :bottom)
 when :left // Esquerra
 points <- Point.new(px - sd, py + d + sd, :left)
 points <- Point.new(px, py + d, :top)
 points <- Point.new(px, py - d, :bottom)
 points <- Point.new(px - sd, py - d - sd, :left)
 end
 end
end

Usos

La corba de Sierpiński és útil en diverses aplicacions pràctiques perquè és més simètrica que altres corbes d'ompliment del pla comunament estudiades. Per exemple, s'ha utilitzat com a base per la construcció ràpida d'una solució aproximada al problema del viatjant de comerç, que busca la seqüència més curta d'un conjunt de punts: l'heurística és simplement visitar els punts en la mateixa seqüència en la que apareixen en la corba de Sierpiński.^[5] Per fer-ho, cal calcular una imatge inversa de cada punt a visitar, i després ordenar els valors. Aquesta idea s'ha utilitzat per construir sistemes d'enrutament per a vehicles comercials basats únicament en arxius de targetes Rolodex.^[6]

Variants

Primeres iteracions de la corba quadrada de Sierpinski.	Primeres iteracions de la corba de punta de fletxa de Sierpinski.

Corba quadrada de Sierpiński

Sierpiński va crear altres corbes partint de la mateixa idea. La corba quadrada de Sierpinski parteix d'un quadrat i aquest cop defineix fins a vuit tipus de punt (amunt-dreta, amunt-esquerra, avall-dreta i avall-esquerra; cadascun dels quals amb versió externa o interna). Cada punt extern és transformat a quatre punts externs i un d'intern, i cada punt intern és transformat a un altre punt intern. El resultat és pràcticament idèntic a la corba original, però inclinat 45 graus. Com en el cas de l'original, aquest també pot ser format utilitzant auto-similaritat.^[4]

Corba de punta de fletxa de Sierpiński

Sierpiński també va mostrar que el límit d'aquestes corbes no només pot ser un pla, sinó també un fractal. Aquest és el cas de la corba de punta de fletxa de Sierpiński, que al seu límit és idèntica al triangle de Sierpiński.

En aquest cas s'utilitza la transformació d'arestes, en la que cada aresta forma tres arestes noves. Es poden distingir dos tipus d'arestes, segons si fan el plec cap a dins de la figura (internes) o cap a fora (externes); cada aresta forma simètricament dues arestes de tipus contrari i una del mateix tipus a l'actual. Com en la resta de casos, també pot ser formada utilitzant auto-similaritat.^[4]

Referències

↑ Cundy, H.; Rollet, A.. Mathematical Models. 3a ed.. Sradbroke, England: Tarquin Pub., 1989, p. 67-68.
↑ Sierpiński, W. «Sur une nouvelle courbe continue qui remplit toute un aire plane.». Bull. l'Acad. des Sciences Cracovile A, 1912, pàg. 462-478.
↑ Wells, D.. The Penguin Dictionary of Curious and Interesting Geometry. Londres: Penguin, 1991, p. 229.
↑ ^4,0 ^4,1 ^4,2 Dickau, Robert M. (1996/7) "Two-dimensional L-systems", Robert's Math Figures. MathForum.org.
↑ Platzman, Loren K.; Bartholdi, John J. «Spacefilling curves and the planar traveling salesman problem». Journal of the Association of Computing Machinery, 36, 4, 1989, pàg. 719-737. DOI: 10.1145/76359.76361.
↑ Bartholdi, John J. «Some combinatorial applications of spacefilling curves». Arxivat de l'original el 3 d'agost 2012. [Consulta: 31 març 2021].

Vegeu també

Bibliografia

Peitgen, H.-O.; Jürgens, H.; Saupe, D. Chaos and Fractals: New Frontiers of Science. Springer, 2013. ISBN 978-1-4757-4740-9.
Stevens, Roger T. Fractal Programming in C. M&T Books, 1989. ISBN 9781558510371.

Enllaços externs

Mathworld - Sierpinski Curve (anglès)

[1] Cundy, H.; Rollet, A.. Mathematical Models. 3a ed.. Sradbroke, England: Tarquin Pub., 1989, p. 67-68.

[2] Sierpiński, W. «Sur une nouvelle courbe continue qui remplit toute un aire plane.». Bull. l'Acad. des Sciences Cracovile A, 1912, pàg. 462-478.

[3] Wells, D.. The Penguin Dictionary of Curious and Interesting Geometry. Londres: Penguin, 1991, p. 229.

[dickau-4] 4,0 ^4,1 ^4,2 Dickau, Robert M. (1996/7) "Two-dimensional L-systems", Robert's Math Figures. MathForum.org.

[5] Platzman, Loren K.; Bartholdi, John J. «Spacefilling curves and the planar traveling salesman problem». Journal of the Association of Computing Machinery, 36, 4, 1989, pàg. 719-737. DOI: 10.1145/76359.76361.

[6] Bartholdi, John J. «Some combinatorial applications of spacefilling curves». Arxivat de l'original el 3 d'agost 2012. [Consulta: 31 març 2021].

[1]

[2]

[3]

[4]

[5]

[6]