# Sierpiński carpet

 related topics {math, number, function} {@card@, make, design} {math, energy, light} {day, year, event} {rate, high, increase}

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

### 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 <= 1)
{
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 centre squaure, it should be filled.
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
*/
x -= x2 * width / 3;
y -= y2 * height / 3;

}

return isSierpinskiCarpetPixelFilled(x, y, (width / 3) + 1, (height / 3) + 1);
}

## Brownian motion on the Sierpinski carpet

The topic of Brownian motion on the Sierpinski carpet has attracted interest in recent years. 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.

## References

Sierpiński, W.: Sur une courbe cantorienne qui contient une image biunivoque et continue de toute courbe donnée. C. r. hebd. Śeanc. Acad. Sci., Paris 162, 629--632 (1916)