Sierpinski carpet
Encyclopedia
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.
. 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
.
/**
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
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);
}
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.
Fractal
A fractal has been defined as "a rough or fragmented geometric shape that can be split into parts, each of which is a reduced-size copy of the whole," a property called self-similarity...
first described by Wacław Sierpiński in 1916. The carpet is a generalization of the Cantor set
Cantor set
In mathematics, the Cantor set is a set of points lying on a single line segment that has a number of remarkable and deep properties. It was discovered in 1875 by Henry John Stephen Smith and introduced by German mathematician Georg Cantor in 1883....
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
Menger sponge
In mathematics, the Menger sponge is a fractal curve. It is a universal curve, in that it has topological dimension one, and any other curve is homeomorphic to some subset of it. It is sometimes called the Menger-Sierpinski sponge or the Sierpinski 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
Self-replication
Self-replication is any behavior of a dynamical system that yields construction of an identical copy of that dynamical system. Biological cells, given suitable environments, reproduce by cell division. During cell division, DNA is replicated and can be transmitted to offspring during reproduction...
arrangements.
Construction
The construction of the Sierpinski carpet begins with a squareSquare (geometry)
In geometry, a square is a regular quadrilateral. This means that it has four equal sides and four equal angles...
. The square is cut into 9 congruent
Congruence (geometry)
In geometry, two figures are congruent if they have the same shape and size. This means that either object can be repositioned so as to coincide precisely with the other object...
subsquares in a 3-by-3 grid, and the central subsquare is removed. The same procedure is then applied recursively
Recursion
Recursion is the process of repeating items in a self-similar way. For instance, when the surfaces of two mirrors are exactly parallel with each other the nested images that occur are a form of infinite recursion. The term has a variety of meanings specific to a variety of disciplines ranging from...
to the remaining 8 subsquares, ad infinitum. The Hausdorff dimension
Hausdorff dimension
thumb|450px|Estimating the Hausdorff dimension of the coast of Great BritainIn mathematics, the Hausdorff dimension is an extended non-negative real number associated with any metric space. The Hausdorff dimension generalizes the notion of the dimension of a real vector space...
of the carpet is log 8/log 3 ≈ 1.8928.
The area of the carpet is zero (in standard Lebesgue measure
Lebesgue measure
In measure theory, the Lebesgue measure, named after French mathematician Henri Lebesgue, is the standard way of assigning a measure to subsets of n-dimensional Euclidean space. For n = 1, 2, or 3, it coincides with the standard measure of length, area, or volume. In general, it is also called...
).
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 (programming language)
C is a general-purpose computer programming language developed between 1969 and 1973 by Dennis Ritchie at the Bell Telephone Laboratories for use with the Unix operating system....
, C++
C++
C++ is a statically typed, free-form, multi-paradigm, compiled, general-purpose programming language. It is regarded as an intermediate-level language, as it comprises a combination of both high-level and low-level language features. It was developed by Bjarne Stroustrup starting in 1979 at Bell...
, and Java
Java (programming language)
Java is a programming language originally developed by James Gosling at Sun Microsystems and released in 1995 as a core component of Sun Microsystems' Java platform. The language derives much of its syntax from C and C++ but has a simpler object model and fewer low-level facilities...
.
/**
- 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 emptyreturn 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);
}
Brownian motion on the Sierpinski carpet
The topic of Brownian motionBrownian motion
Brownian motion or pedesis is the presumably random drifting of particles suspended in a fluid or the mathematical model used to describe such random movements, which is often called a particle theory.The mathematical model of Brownian motion has several real-world applications...
on the Sierpinski carpet has attracted interest in recent years. Martin Barlow and Richard Bass have shown that a random walk
Random walk
A random walk, sometimes denoted RW, is a mathematical formalisation of a trajectory that consists of taking successive random steps. For example, the path traced by a molecule as it travels in a liquid or a gas, the search path of a foraging animal, the price of a fluctuating stock and the...
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
Large deviations theory
In probability theory, the theory of large deviations concerns the asymptotic behaviour of remote tails of sequences of probability distributions. Some basic ideas of the theory can be tracked back to Laplace and Cramér, although a clear unified formal definition was introduced in 1966 by Varadhan...
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.
See also
- List of fractals by Hausdorff dimension
- Sierpinski triangleSierpinski triangleThe Sierpinski triangle , also called the Sierpinski gasket or the Sierpinski Sieve, is a fractal and attractive fixed set named after the Polish mathematician Wacław Sierpiński who described it in 1915. However, similar patterns appear already in the 13th-century Cosmati mosaics in the cathedral...
- Hawaiian earringHawaiian earringIn mathematics, the Hawaiian earring H is the topological space defined by the union of circles in the Euclidean plane R2 with center and radius 1/n for n = 1, 2, 3, ......
- Menger spongeMenger spongeIn mathematics, the Menger sponge is a fractal curve. It is a universal curve, in that it has topological dimension one, and any other curve is homeomorphic to some subset of it. It is sometimes called the Menger-Sierpinski sponge or the Sierpinski sponge...