Sierpiński curves are a recursively defined sequence of continuous closed plane fractal
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...
In mathematics, a curve is, generally speaking, an object similar to a line but which is not required to be straight...
s discovered by Wacław Sierpiński, which in the limit completely fill the unit square: thus their limit curve, also called the Sierpiński curve, is an example of a space-filling curve
Space-filling curve
In mathematical analysis, a space-filling curve is a curve whose range contains the entire 2-dimensional unit square...
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...
In mathematics, the Euclidean distance or Euclidean metric is the "ordinary" distance between two points that one would measure with a ruler, and is given by the Pythagorean formula. By using this formula as distance, Euclidean space becomes a metric space...
of is ,
i.e., it grows exponentially with beyond any limit, whereas the limit for of the area enclosed by is that of the square (in Euclidean metric).
Uses of the curve
The Sierpiński curve is useful in several practical applications because it is more symmetrical than other commonly-studied space-filling curves. For example, it has been used as a basis for the rapid construction of an approximate solution to the Traveling Salesman Problem (which asks for the shortest sequence of a given set of points): The heuristic is simply to visit the points in the same sequence as they appear on the Sierpiński curve. To do this requires two steps: First compute an inverse image of each point to be visited; then sort the values. This idea has been used to build routing systems for commercial vehicles based only on Rolodex card files.
A space-filling curve is a continuous map of the unit interval onto a unit square and so a (pseudo) inverse maps the unit square to the unit interval. One way of constructing a pseudo-inverse is as follows. Let the lower-left corner (0, 0) of the unit square correspond to 0.0 (and 1.0). Then the upper-left corner (0, 1) must correspond to 0.25, the upper-right corner (1, 1) to 0.50, and the lower-right corner (1, 0) to 0.75. The inverse map of interior points are computed by taking advantage of the recursive structure of the curve. Here is a function coded in Java that will compute the relative position of any point on the Sierpiński curve (that is, a pseudo-inverse value). It takes as input the coordinates of the point (x,y) to be inverted, and the corners of an enclosing right isosceles triangle (ax, ay), (bx, by), and (cx, cy). (Note that the unit square is the union of two such triangles.) The remaining parameters specify the level of accuracy to which the inverse should be computed.
static long sierp_pt2code( double ax, double ay, double bx, double by, double cx, double cy,
int currentLevel, int maxLevels, long code, double x, double y )
{
if (currentLevel <= maxLevel) {
currentLevel++;
if ((sqr(x-ax) + sqr(y-ay)) < (sqr(x-cx) + sqr(y-cy))) {
code = sierp_pt2code( ax, ay, (ax+cx)/2.0, (ay+cy)/2.0, bx, by,
currentLevel, maxLevel, 2 * code + 0, x, y );
}
else {
code = sierp_pt2code( bx, by, (ax+cx)/2.0, (ay+cy)/2.0, cx, cy,
currentLevel, maxLevel, 2 * code + 1, x, y );
}
}
return code;
}
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...
In computing, an applet is any small application that performs one specific task that runs within the scope of a larger program, often as a plug-in. An applet typically also refers to Java applets, i.e., programs written in the Java programming language that are included in a web page...
draws a Sierpiński curve by means of four methods that 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...
call one another:
import java.awt.*;
import java.applet.*;
public class SierpinskiCurve extends Applet {
private SimpleGraphics sg=null;
private int dist0 = 128, dist;
public void init {
sg = new SimpleGraphics(getGraphics);
dist0 = 128;
resize ( 4*dist0, 4*dist0 );
}
Logo is a multi-paradigm computer programming language used in education. It is an adaptation and dialect of the Lisp language; some have called it Lisp without the parentheses. It was originally conceived and written as functional programming language, and drove a mechanical turtle as an output...
program draws a Sierpiński curve by means of recursion
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 half.sierpinski :size :level
if :level = 0 [forward :size stop]
half.sierpinski :size :level - 1
left 45
forward :size * sqrt 2
left 45
half.sierpinski :size :level - 1
right 90
forward :size
right 90
half.sierpinski :size :level - 1
left 45
forward :size * sqrt 2
left 45
half.sierpinski :size :level - 1
end
to sierpinski :size :level
half.sierpinski :size :level
right 90
forward :size
right 90
half.sierpinski :size :level
right 90
forward :size
right 90
end
A Hilbert curve is a continuous fractal space-filling curve first described by the German mathematician David Hilbert in 1891, as a variant of the space-filling curves discovered by Giuseppe Peano in 1890....
A Moore curve is a continuous fractal space-filling curve which is a variant of the Hilbert curve. Precisely, it is the loop version of the Hilbert curve, and it may be thought as the union of four copies of the Hilbert curves combined in such a way to make the endpoints coincide.Because the Moore...
The Sierpiński arrowhead curve is a fractal curve similar in appearance and identical in limit to the Sierpiński triangle.-Representation as Lindenmayer system:The Sierpiński arrowhead curve can be expressed by a rewrite system .-Literature:...
Recursion in computer science is a method where the solution to a problem depends on solutions to smaller instances of the same problem. The approach can be applied to many types of problems, and is one of the central ideas of computer science....
The 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...
The source of this article is wikipedia, the free encyclopedia. The text of this article is licensed under the GFDL.
completely fill the unit square: thus their limit curve, also called the Sierpiński curve, is an example of a space-filling curve
) is 
. 
is 
,
beyond any limit, whereas the limit for 
of the area enclosed by 
is 
that of the square (in Euclidean metric).
