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);
  }

[edit] 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.

[edit] 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)

Full article ▸

related documents
Euclidean distance
Endomorphism ring
Sedenion
Co-NP
Ring homomorphism
Identity function
Disjoint sets
Sieve of Eratosthenes
Context-sensitive language
Galois group
Doubling the cube
Markov process
Equivalence class
Water, gas, and electricity
Center (group theory)
Harmonic analysis
Lazy initialization
Chart parser
Measurable function
Gabriel Lamé
Church–Rosser theorem
Co-NP-complete
Recursive language
Senary
Digital Signature Algorithm
Greibach normal form
Power associativity
Prime ideal
JUnit
Essential singularity