Polytope

From Wikipedia, the free encyclopedia

In geometry polytope means, first, the generalization to any dimension of polygon in two dimensions, polyhedron in three dimensions, and polychoron in four 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.

1 Convex polytopes
2 Simplicial decomposition
3 Uses
4 References
5 See also
6 External links

[edit] Convex polytopes

One special kind of polytope is a convex polytope, which is the convex hull of a finite set of points. A convex polytope can also be represented as the intersection of half-spaces. This intersection can be written as the matrix inequality:

$Ax \leq b$

where A is an m by n matrix, m being the number of bounding half-spaces and n being the number of dimensions of the affine space Rⁿ in which the polytope is contained; and b is an m 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 supporting hyperplane of the polytope, which is any hyperplane one of whose closed half-spaces contains the polytope; and some of the rows correspond with a bounding hyperplane of the polytope, which is a hyperplane that is spanned by its intersection with the polytope. This definition assumes that the polytope is n-dimensional; if it is not, then the solution of Ax ≤ b lies in a proper affine subspace of Rⁿ and the preceding discussion should be applied to that subspace. (Note that the intersection of arbitrary half-spaces need not be bounded; it is a convex polytope if and only if it is bounded.)

An n-dimensional convex polytope is bounded by a number of (n−1)-dimensional facets. These facets are themselves polytopes, whose facets are (n−2)-dimensional ridges of the original polytope. Every ridge arises as the intersection of two facets (but the intersection of two facets need not be a ridge). Ridges are once again polytopes whose facets give rise to (n−3)-dimensional boundaries of the original polytope, and so on. These bounding sub-polytopes may be referred to as faces, or specifically k-dimensional faces or k-faces (although the term "face" may also refer specifically to a 2-dimensional face). A 0-dimensional face is called a vertex; and a 1-dimensional face is called an edge. A 3-dimensional face is sometimes called a cell.

Dimension of element	Element name (in a d-polytope)
0	Vertex
1	Edge
2	Face
3	Cell
$\vdots$	$\vdots$
n	n-face - elements order n = 2, 3, ..., d − 1
$\vdots$	$\vdots$
d − 3	Peak - (d−3)-face
d − 2	Ridge - (d−2)-face
d − 1	Facet - (d−1)-face
d	Body - d-face

Assume in the matrix definition of a convex polytope P, Ax ≤ b, that the matrix A has the smallest possible number of rows of any matrix that defines P. Then there is one row for each facet, and the facet consists of the points on the polytope that satisfiy equality in the one row of the matrix that corresponds to that facet (it does not matter whether they also satisfy equality in other rows). Similarly, a ridge satisfies equality in two rows the matrix representation. In general, an (n−j)-dimensional face satisfies equality in j specific rows of A. These rows form a basis of the face. (They are not arbitrary; the set must be j-dimensional so the rows must be linearly independent in the augmented matrix [A | b]. The choice of the j rows may not be unique.) Geometrically speaking, this means that the face is the set of points on the polytope that lie in the intersection of j of the polytope's bounding hyperplanes.

The face lattice of a square pyramid, drawn as a Hasse diagram; each face in the lattice is labeled by its vertex set.

The faces of a convex polytope thus form a lattice called its face lattice, where the partial ordering is by set containment of faces. (To ensure that every pair of faces has a join and a meet in the face lattice, the polytope itself and the empty set are considered 'faces'. The whole polytope is the unique maximum element of the lattice. The empty set, considered to be a −1-dimensional face of every polytope, is the unique minimum element of the lattice.)

This terminology is not fully standardized. The term face is sometimes used to refer only to 2-dimensional faces, 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:

If two segments meet at each vertex (so not the case for the final one), we get a topological curve, called a polygonal curve. One may 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.

[edit] Uses

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