Sierpinski triangle
From Wikipedia, the free encyclopedia
Jump to: navigation, search
Sierpinski triangle
The Sierpinski triangle, also called the Sierpinski gasket, is a fractal named after Wacław Sierpiński who described it in 1915.[1] Originally constructed as a curve, this is one of the basic examples of self-similar sets, i.e. it is a mathematically generated pattern that can be reproducible at any magnification or reduction.
Contents
[hide]· 1 Construction
· 2 Properties
· 3 Analogs in higher dimension
· 4 Self-assembly with DNA
· 5 Computer program
· 6 See also
· 7 References
· 8 External links
[edit] Construction
An algorithm for obtaining arbitrarily close approximations to the Sierpinski triangle is as follows:
- Start with any triangle in a plane (any closed, bounded region in the plane will actually work). The canonical Sierpinski triangle uses an equilateral triangle with a base parallel to the horizontal axis (first image).
- Shrink the triangle by ½, make two copies, and position the three shrunken triangles so that each triangle touches the two other triangles at a corner (image 2).
- Repeat step 2 with each of the smaller triangles (image 3 and so on).
Note that this infinite process is not dependent upon the starting shape being a triangle - it is just clearer that way. The first few steps starting, for example, from a square also tend towards a Sierpinski gasket. Michael Barnsley used an image of a fish to illustrate this in his paper V-variable fractals and superfractals (PDF).
The actual fractal is what would be obtained after an infinite number of iterations. More formally, one describes it in terms of functions on closed sets of points. If we let da note the dilation by a factor of ½ about a point a, then the Sierpinski triangle with corners a, b, and c is the fixed set of the transformation da U db U dc.
This is an attractive fixed set, so that when the operation is applied to any other set repeatedly, the images converge on the Sierpinski triangle. This is what is happening with the triangle above, but any other set would suffice.
If one takes a point and applies each of the transformations da, db, and dc to it randomly, the resulting points will be dense in the Sierpinski triangle, so the following algorithm will again generate arbitrarily close approximations to it:
Start by labelling p1, p2 and p3 as the corners of the Sierpinski triangle, and a random point v1. Set vn+1 = ½ ( vn + prn ), where rn is a random number 1, 2 or 3. Draw the points v1 to v∞. If the first point v1 was a point on the Sierpinski triangle, then all the points vn lie on the Sierpinski triangle. If the first point v1 to lie within the perimeter of the triangle is not a point on the Sierpinski triangle, none of the points vn will lie on the Sierpinski triangle, however they will converge on the triangle. If v1 is outside the triangle, the only way vn will land on the actual triangle, is if vn is on what would be part of the triangle, if the triangle was infinitely large.
Or more simply:
- Take 3 points in a plane, and form a triangle
- Randomly select any point inside the triangle and move half the distance from that point to any of the 3 vertex points. Plot the current position.
- Repeat from step 2.
Note: This method is also called the Chaos game. You can start from any point outside or inside the triangle, and it would eventually form the Sierpinski Gasket with a few leftover points. It is interesting to do this with pencil and paper. A brief outline is formed after placing approximately one hundred points, and detail begins to appear after a few hundred.
Or using an Iterated function system
An alternative way of computing the Sierpinski triangle uses an Iterated function system and starts by a point in the origin (x0=0, y0=0) and then the new points are iteratively computed by randomly applying (with equal probability) one of the following 3 coordinate transformations (using the so called chaos game):
Sierpinski triangle using IFS
xn+1=0.5 xn
yn+1=0.5 yn ; a half-size copy
when this coordinate transformation is used, the point is drawn in brown in the figure
xn+1=0.5 xn+0.5
yn+1=0.5 yn+0.5; a half-size copy shifted right and up
when this coordinate transformation is used, the point is drawn in red
xn+1=0.5 xn+1
yn+1=0.5 yn ; a half-size copy doubled shifted to the right
when this coordinate transformation is used, the point is drawn in blue
Or using an L-system — The Sierpinski triangle drawn using an L-system.
Other means — The Sierpinski triangle also appears in certain cellular automata, including those relating to Conway's Game of Life. The automaton "12/1" when applied to a single cell will generate four approximations of the Sierpinksi triangle.
[edit] Properties
The Sierpinski triangle has Hausdorff dimension log(3)/log(2) ≈ 1.585, which follows from the fact that it is a union of three copies of itself, each scaled by a factor of ½.
If one takes Pascal's triangle with 2n rows and colors the even numbers white, and the odd numbers black, the result is an approximation to the Sierpinski triangle.
The area of a Sierpinski triangle is zero (in Lebesgue measure). This can be seen from the infinite iteration, where we remove 25% of the area left at the previous iteration.
[edit] Analogs in higher dimension
The tetrix is the three-dimensional analog of the Sierpinski triangle, formed by repeatedly shrinking a regular tetrahedron to one half its original height, putting together four copies of this tetrahedron with corners touching, and then repeating the process.
A Sierpinski square-based pyramid and its 'inverse'
[edit] Self-assembly with DNA
Researchers in Erik Winfree's lab at the California Institute of Technology have also constructed self-assembling Sierpinski triangles using DNA tiles (Rothemund et al. 2004).
[edit] Computer program
Computer programs to draw Sierpinski triangles are usually done recursively in programming languages that permit explicit recursion such as Java.
import java.awt.*;
import java.applet.*;
public class SierpinskiTriangle extends Applet {
private Graphics g;
private int dMin=4; // limit to recursion in pixels
public void paint(Graphics g) {
this.g = g;
int d = 1024; // basis (width of the triangle)
int x0 = 50; // distance from the left
int y0 = 50; // distance from the top
int h = (int)(d*Math.sqrt(3)/2); // height
// so: suitable for an equilateral triangle
int xA=x0, yA=y0+h; // (bottom-left)
int xB=x0+d, yB=y0+h; // (bottom-right)
int xC=x0+d/2, yC=y0; // equilateral triangle (top-center)
int[] x = { xA, xB, xC };
int[] y = { yA, yB, yC };
drawSierpinskiTriangle( x, y, d/2 ); // start recursion
}
private void drawSierpinskiTriangle ( int[] x, int[] y, int d ) {
if (d<=dMin) g.fillPolygon ( x, y, 3 ); // bottom of the recursion
else {
// centers of the sides:
int xMc = (x[0]+x[1])/2, yMc = (y[0]+y[1])/2;
int xMb = (x[0]+x[2])/2, yMb = (y[0]+y[2])/2;
int xMa = (x[1]+x[2])/2, yMa = (y[1]+y[2])/2;
int[] xNew1 = { x[0], xMc, xMb };
int[] yNew1 = { y[0], yMc, yMb };
drawSierpinskiTriangle ( xNew1, yNew1, d/2 ); // recursion
int[] xNew2 = { x[1], xMc, xMa };
int[] yNew2 = { y[1], yMc, yMa };
drawSierpinskiTriangle ( xNew2, yNew2, d/2 ); // recursion
int[] xNew3 = { x[2], xMb, xMa };
int[] yNew3 = { y[2], yMb, yMa };
drawSierpinskiTriangle ( xNew3, yNew3, d/2 ); // recursion
}
}
}
Another implementation doesn't use recursion and draws the triangle in a rotated manner, but it is easier to implement.
// Assumes:
// - plot plots a pixel on a surface
// - size is a power of two
// - & is a bitwise and operator
//
for(int x = 0; x < size; x++)
for(int y = 0; y < size; y++)
if(x & y)
plot(x, y, background)
else
plot(x, y, foreground)
[edit] See also
· List of fractals by Hausdorff dimension
· Sierpinski carpet
· Pascal's triangle
· Triforce
[edit] References
- ^ . W. Sierpinski, Sur une courbe dont tout point est un point de ramification, C. R. Acad. Sci. Paris 160(1915) 302-305
Wikimedia Commons has media related to:
Sierpinski triangle
[edit] External links
· Eric W. Weisstein, Sierpinski Sieve at MathWorld.
· Paul W. K. Rothemund, Nick Papadakis, and Erik Winfree, Algorithmic Self-Assembly of DNA Sierpinski Triangles, PLoS Biology, volume 2, issue 12, 2004.
· Sierpinski Gasket by Trema Removal at cut-the-knot
· Sierpinski Gasket and Tower of Hanoi at cut-the-knot
· Article explaining Sierpinski's Triangle created with a bitwise XOR (example program in Macromedia Flash ActionScript)
· Article explaining Sierpinski's Triangle created with the Chaos Game (example program in Macromedia Flash ActionScript)
· Sierpinski Triangle and Machu Picchu. Fractal illustration with animation and sound.
· VisualBots - Freeware multi-agent simulator in Microsoft Excel. Sample programs include Sierpinski Triangle.
· IFS Fractal fern and Sierpinski triangle - JAVA applet
· Contains a section where the Sierpinski triangle can be seen step by step -- Shockwave
Retrieved from "http://en.wikipedia.org/wiki/Sierpinski_triangle"
Categories: Fractals | Factorial and binomial topics | Curves | Topological spaces
Views
· Article
· Discussion
· Edit this page
· History
Personal tools
· Sign in / create account
Navigation
· Main page
· Contents
· Featured content
· Current events
· Random article
interaction
· About Wikipedia
· Community portal
· Recent changes
· Upload file
· Contact us
· Make a donation
· Help
Search
Top of Form
Bottom of Form
Toolbox
· What links here
· Related changes
· Upload file
· Special pages
· Printable version
· Permanent link
· Cite this article
In other languages
· Català
· Deutsch
· Español
· Français
· 한국어
· 日本語
· Polski
· Português
· Русский
· Svenska
· Українська
· This page was last modified 02:28, 21 May 2007.
· All text is available under the terms of the GNU Free Documentation License. (See Copyrights for details.)
Wikipedia® is a registered trademark of the Wikimedia Foundation, Inc., a US-registered 501(c)(3) tax-deductible nonprofit charity.
· Privacy policy
· About Wikipedia
· Disclaimers