Outils :Vous avez un site web ? Un blog ?
 Technorati reactions rencontre |
A convex polytope is a special case of a polytope, having the additional property that it is also a convex set of points in the n-dimensional space Rn.[1] Some authors use the terms "convex polytope" and "convex polyhedron" interchangeably, while others prefer to draw a distinction between the notions of a polyhedron and a polytope.
In addition, some texts require a polytope to be a bounded set, while others[2] (including this article) allow polytopes to be unbounded. The terms "bounded/unbounded convex polytope" will be used below whenever the boundedness is critical to the discussed issue.
Convex polytopes play an important role both in various branches of mathematics and in applied areas, most notably in linear programming.
A comprehensive and influential book in the subject, called Convex Polytopes, was published in 1967 by Branko Grünbaum. In 2003 the 2nd edition of the book was published, significantly updated and expanded by Grünbaum's followers.[1]
In the Grünbaum's book and in some other texts in discrete geometry the convex polytopes are called simply "polytopes".
A polytope is called full-dimensional, if it is an n-dimensional object in Rn.
Contents |
 |
Wikimedia Commons has media related to: Polyhedron |
Convex polytopes may be represented in a number of ways, depending on what is more suitable for the problem at hand. The two main representations of a convex polytope are the intersection of half-spaces (half-space representation) and the convex hull of a set of points (vertex representation).
A convex polytope may be defined as an intersection of a finite number of half-spaces. Such definition is called a half-space representation (H-representation or H-description).[1] There exist infinitely many H-descriptions of a convex polytope. However, for a full-dimensional convex polytope, the minimal H-description is in fact unique and is given by the set of the facet-defining halfspaces.[1]
A closed half-space can be written as a linear inequality:[1]
where n is the dimension of the space containing the polytope under consideration. Hence, a closed convex polytope may be regarded as the set of solutions to the system of linear inequalities:
where m is the number of half-spaces defining the polytope. This can be concisely written as the matrix inequality:
where A is an m×n matrix, x is an n×1 column vector of variables, and b is an m×1 column vector of constants.
An open convex polytope is defined in the same way, with strict inequalities used in the formulas instead of the non-strict ones.
The coefficients of each row of A and b correspond with the coefficients of the linear inequality defining the respective half-space. Hence, each row in the matrix corresponds with a supporting hyperplane of the polytope, a hyperplane bounding a half-space that contains the polytope. If a supporting hyperplane also intersects the polytope, it is called a bounding hyperplane (since it is a supporting hyperplane, it can only intersect the polytope at the polytope's boundary).
The foregoing definition assumes that the polytope is full-dimensional. If it is not, then the solution of Ax ≤ b lies in a proper affine subspace of Rn and discussion of the polytope may be constrained to this subspace.
In general, the intersection of arbitrary half-spaces need not be bounded.
A finite convex polytope may also be defined as a convex hull of a finite set of points. Such a definition is called a vertex representation (V-representation or V-description).[1] There exist infinitely many V-descriptions of a convex polytope. However, for a full-dimensional convex polytope, the minimal V-description is in fact unique and is given by the set of the vertices of the polytope.[1]
The finite basis theorem[2] is an extension of the notion of V-description to include infinitie polytopes. The theorem states that a convex polyhedron is the convex sum of its vertices plus the conical sum of the direction vectors of its infinite edges.
Given a convex polytope P defined by the matrix inequality , if each row in A corresponds with a bounding hyperplane and is linearly independent of the other rows, then each facet of P corresponds with exactly one row of A, and vice versa. Each point on a given facet will satisfy the linear equality of the corresponding row in the matrix. (It may or may not also satisfy equality in other rows). Similarly, each point on a ridge will satisfy equality in two of the rows of A.
In general, an (n − j)-dimensional face satisfies equality in j specific rows of A. These rows form a basis of the face. 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 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 also considered 'faces'. The whole polytope is the unique maximum element of the lattice, and the empty set, considered to be a (−1)-dimensional face (a null polytope) of every polytope, is the unique minimum element of the lattice.
Two polytopes are called combinatorially isomorphic if their face lattices are isomorphic.
The polytope graph ( polytopal graph, graph of the polytope) is the set of vertices and edges of the polytope only - higher dimensional faces are ignored. In fact, for a simple polytope the face lattice is completely determined by its polytope graph (Blind & Mani-Levitska (1987), a simple proof by Kalai (1988))[3]. The latter fact is instrumental in the proof that from the point of view of computational complexity, the problem of deciding whether two convex polytopes are combinatorially isomorphic is equivalent to the graph isomorphism problem, even when restricted to the class of simple or simplicial polytopes. [4]
See also "Polyhedral graph".
All bounded convex polytopes in Rn, being topological (n − 1)-spheres, have a Euler characteristic of 0 for odd n and 2 for even n. Hence, they may be regarded as tessellations of (n − 1)-dimensional elliptic space.
Different representations of a convex polytope have different utility, therefore the construction of one representation given another one is an important problem. The problem of the construction of a V-representation is known as the vertex enumeration problem and the problem of the construction of a H-representation is known as the facet enumeration problem. While the vertex set of a bounded convex polytope uniquely defines it, in various applications it is important to know more about the combinatorial structure of the polytope, i.e., about its face lattice. Various convex hull algorithms deal both with the facet enumeration and face lattice construction.
In the planar case, i.e., for a convex polygon, both facet and vertex enumeration problems amount to the ordering vertices (resp. edges) around the convex hull. It is a trivial task when the convex polygon is specified in a traditional for polygons way, i.e., by the ordered sequence of its vertices 
. When the input list of vertices (or edges) is unordered, the time complexity of the problems becomes O(m log m).[citation needed]
