Corba de Sierpiński
![](http://upload.wikimedia.org/wikipedia/commons/c/ce/Sierpinski_curve_steps.gif)
La corba de Sierpiński és una seqüència definida de forma recursiva d'una corba fractal contínua que en el límit 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]
Com que la corba té aquesta propietat de recobriment del pla, la seva dimensió de Hausdorff-Bezikóvitx al límit és 2.
La distància euclidiana de és
és a dir, creix de forma accelerada amb més enllà de qualsevol límit, mentre que el límit per de l'àrea tancada per és la del quadrat (en mètrica euclidiana).
Procediment
![](http://upload.wikimedia.org/wikipedia/commons/thumb/3/3b/Sierpinski_corba.png/220px-Sierpinski_corba.png)
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
![]() | ![]() |
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é
- Triangle de Sierpiński
- Corba de Peano
- Floc de neu de Koch
- Fractals per dimensió de Hausdorff
- Algorisme recursiu
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)