Sierpinski carpet
The Sierpinski carpet is a plane fractal first described by Wacław Sierpiński in 1916. The carpet is a generalization of the Cantor set to two dimensions (another is Cantor dust). Sierpiński demonstrated that this fractal is a universal curve, in that any possible one-dimensional graph, projected onto the two-dimensional plane, is homeomorphic to a subset of the Sierpinski carpet. For curves that cannot be drawn on a 2D surface without self-intersections, the corresponding universal curve is the Menger sponge, a higher-dimensional generalization.
The technique can be applied to repetitive tiling arrangement; triangle, square, hexagon being the simplest. It would seem impossible to apply it to other than rep-tile arrangements.
Contents |
[edit] Construction
The construction of the Sierpinski carpet begins with a square. The square is cut into 9 congruent subsquares in a 3-by-3 grid, and the central subsquare is removed. The same procedure is then applied recursively to the remaining 8 subsquares, ad infinitum. The Hausdorff dimension of the carpet is log 8/log 3 ≈ 1.8928.
The area of the carpet is zero (in standard Lebesgue measure).
The Sierpinski carpet can also be created by iterating every pixel in a square and using the following algorithm to decide if the pixel is filled. The following implementation is valid C, C++, and Java.
/** * Decides if a point at a specific location is filled or not. * @param x is the x coordinate of the point being checked * @param y is the y coordinate of the point being checked * @param width is the width of the Sierpinski Carpet being checked * @param height is the height of the Sierpinski Carpet being checked * @return 1 if it is to be filled or 0 if it is not */ int isSierpinskiCarpetPixelFilled(int x, int y, int width, int height) { // base case 1 of 2 if ((x <= 0)||(y <= 0)||(x>=width)||(y>=height)) //top row or left column or out of bounds should be full { return 1; } { /* If the grid was split in 9 parts, what part(x2,y2) would x,y fit into? */ int x2 = x * 3 / width; // an integer from 0..2 inclusive int y2 = y * 3 / height; // an integer from 0..2 inclusive // base case 2 of 2 if (x2 == 1 && y2 == 1) // if in the center square, it should be empty return 0; // general case /* offset x and y so it becomes bounded by 0..width/3 and 0..height/3 and prepares for recursive call some offset is added to make sure the parts have all the correct size when width and height isn't divisible by 3 */ x -= (x2 * width+2) / 3; y -= (y2 * height+2) / 3; width = (width +2-x2)/3; height = (height+2-y2)/3; } return isSierpinskiCarpetPixelFilled(x, y, width, height); }
[edit] Brownian motion on the Sierpinski carpet
The topic of Brownian motion on the Sierpinski carpet has attracted interest in recent years.[1] Martin Barlow and Richard Bass have shown that a random walk on the Sierpinski carpet diffuses at a slower rate than an unrestricted random walk in the plane. The latter reaches a mean distance proportional to n1/2 after n steps, but the random walk on the discrete Sierpinski carpet reaches only a mean distance proportional to n1/β for some β > 2. They also showed that this random walk satisfies stronger large deviation inequalities (so called "sub-gaussian inequalities") and that it satisfies the elliptic Harnack inequality without satisfying the parabolic one. The existence of such an example was an open problem for many years.
[edit] References
Sierpiński, W.: Sur une courbe cantorienne qui contient une image biunivoque et continue de toute courbe donnée. C. r. hebd. Seanc. Acad. Sci., Paris 162, 629--632 (1916)
- ^ Barlow, Martin; Bass, Richard, Brownian motion and harmonic analysis on Sierpinski carpets, http://www.math.uconn.edu/~bass/papers/sch.pdf, retrieved 25 September 2011
[edit] See also
 |
Wikimedia Commons has media related to: Sierpinski carpet |
