Polytope

From Free net encyclopedia

In geometry polytope means, first, the generalization to any dimension of polygon in two dimensions, and polyhedron in three dimensions. Beyond that, the term is used for a variety of related mathematical concepts. This is analogous to the way the term square may be used to refer to a square-shaped region of the plane, or just to its boundary, or even to a mere list of its vertices and edges along with some information about the way they are connected. The term was coined by Alicia Boole, the daughter of logician George Boole.

The Platonic solids, or regular polytopes in three dimensions, were a major focus of study of ancient Greek mathematicians (most notably Euclid's Elements), probably because of their intrinsic aesthetic qualities. In modern times, polytopes and related concepts have found important applications in computer graphics, optimization, search engines and numerous other fields.

Contents

[edit]

Convex polytopes

One special kind of polytope is a convex polytope, which is the convex hull of a finite set of points.

Convex polytopes can also be represented as the intersection of half-spaces. This intersection can be written as the matrix inequality:

<math>Ax \leq b</math>

where A is an n by m matrix, n being the number of bounding half-spaces and m being the number of dimensions of the polytope. b is an n by 1 column vector. The coefficients of each row of A and b correspond with the coefficients of the linear inequality defining the respective half-space (see hyperplane for an explanation). Hence, each row in the matrix corresponds with a bounding hyperplane of the polytope.

An n-dimensional convex polytope is bounded by a number of (n-1)-dimensional facets. Each pair of facets meet at an (n-2)-dimensional ridge. Ridges, in turn, meet at (n-3)-dimensional boundaries, and so on. These bounding sub-polytopes are referred to as faces (although the term may also refer specifically to the 2-dimensional case). A 0-dimensional face is called a vertex; and a 1-dimensional face is called an edge. A 3-dimensional face is called a cell.

A facet consists of the points on the polytope that also satisfies the equality form of the matrix representation where only one row in A is present. Similarly, a ridge satisfies the equality form of the matrix representation where two rows in A are present. In general, an (n-j)-dimensional face satisfies the equality relation with j rows of A. These rows form the basis of the face. Geometrically speaking, this means that the face is the set of points on the polytope that lie in intersection of j of the polytope's bounding hyperplanes. The faces of a convex polytope thus form a lattice called its face lattice, where the subset relation is defined between basis hyperplanes. (The polytope itself is considered a 'face' in the face lattice, and is the maximum of the lattice.)

Note that this terminology is not yet fully standardized. The term face is sometimes used to refer only to 2-dimensional subpolytopes, and other times used in place of facet. The word edge is sometimes used to refer to a ridge.

[edit]

Simplicial decomposition

Now given any convex hull in r-dimensional space (but not in any (r-1)-plane, say) we can take linearly independent subsets of the vertices, and define r-simplices with them. In fact, you can choose several simplices in this way such that their union as sets is the original hull, and the intersection of any two is either empty or an s-simplex (for some s < r).

For example, in the plane a square (convex hull of its corners) is the union of the two triangles (2-simplices), defined by a diagonal 1-simplex which is their intersection.

In general, the definition (attributed to Alexandrov) is that an r-polytope is defined as a set with an r-simplicial decomposition with some additional properties. If a set has an r-simplicial decomposition this means it is a union of s-simplices for values of s with s at most r, that is closed under intersection, and such that the only time that one of simplices is contained in another is as a face. (For a more abstract treatment, see simplicial complex).

What does this let us build? Let's start with the 1-simplex, or line segment. Then we have the line segment, of course, and anything that you can get by joining line segments end-to-end:

Image:Examples of polytopes as set of line segments.png


If two segments meet at each vertex (so not the case for the final one), we get a topological curve, called a polygonal curve. You can categorize these as open or closed, depending on whether the ends match up, and as simple or complex, depending on whether they intersect themselves. Closed polygonal curves are called polygons.

Simple polygons in the plane are Jordan curves: they have an interior that is a topological disk. So does a 2-polytope (as you can see in the third example above), and these are often treated interchangeably with their boundary, the word polygon referring to either.

Now the process can be repeated. Joining polygons along edges (1-faces) gives a polyhedral surface, called a skew polygon when open and a polyhedron when closed. Simple polyhedra are interchangeable with their interiors, which are 3-polytopes that can be used to build 4-dimensional forms (sometimes called polychora), and so on to higher polytopes.

Other definitions (equivalent and otherwise) are possible and occur in the mathematical literature. Polytopes may be regarded as a tessellation of some sort of the manifold of their surface.

The theory of abstract polytopes attempts to detach polytopes from the space containing them, considering their purely combinatorial properties. This allows the definition of the term to be extended to include objects for which it is difficult to define clearly a natural underlying space<I/>.

[edit]

Uses

In the study of optimization, linear programming studies the maxima and minima of linear functions constricted to the boundary of an <math>n</math>-dimensional polytope.

[edit]

References

  • Grünbaum, Branko, Convex polytopes, New York ; London : Springer, c2003. ISBN 0387004246.
    Second edition prepared by Volker Kaibel, Victor Klee, and Günter M. Ziegler.
[edit]

See also

[edit]

External links

es:Politopo fr:Polytope it:Politopo

Retrieved from "http://www.netipedia.com/index.php/Polytope"