Facet Enumeration

A convex polytope is a special case of a polytope, having the additional property that it is also a convex set contained in the $n$-dimensional Euclidean space $\mathbb^n$. Most texts. use the term "polytope" for a bounded convex polytope, and the word "polyhedron" for the more general, possibly unbounded object. Others''Mathematical Programming'', by Melvyn W. Jeter (1986)
p. 68
/ref> (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. Yet other texts identify a convex polytope with its boundary.

Convex polytopes play an important role both in various branches of mathematics and in applied areas, most notably in linear programming.

In the influential textbooks of Grünbaum and Ziegler on the subject, as well as in many other texts in discrete geometry, convex polytopes are often simply called "polytopes". Grünbaum points out that this is solely to avoid the endless repetition of the word "convex", and that the discussion should throughout be understood as applying only to the convex variety (p. 51).

A polytope is called ''full-dimensional'' if it is an $n$-dimensional object in $\mathbb^n$.

Examples

*Many examples of bounded convex polytopes can be found in the article "polyhedron".
*In the 2-dimensional case the full-dimensional examples are a half-plane, a strip between two parallel lines, an angle shape (the intersection of two non-parallel half-planes), a shape defined by a convex polygonal chain with two rays attached to its ends, and a convex polygon.
*Special cases of an unbounded convex polytope are a slab between two parallel hyperplanes, a wedge defined by two non-parallel half-spaces, a polyhedral cylinder (infinite prism), and a polyhedral cone (infinite cone) defined by three or more half-spaces passing through a common point.

Definitions

A convex polytope may be defined in a number of ways, depending on what is more suitable for the problem at hand. Grünbaum's definition is in terms of a convex set of points in space. Other important definitions are: as the intersection of half-spaces (half-space representation) and as the convex hull of a set of points (vertex representation).

Vertex representation (convex hull)

In his book ''Convex Polytopes'', Grünbaum defines a convex polytope as a compact convex set with a finite number of extreme points:
: A set $K$ of $\mathbb^n$ is ''convex'' if, for each pair of distinct points $a$, $b$ in $K$, the closed segment with endpoints $a$ and $b$ is contained within $K$.

This is equivalent to defining a bounded convex polytope as the convex hull of a finite set of points, where the finite set must contain the set of extreme points of the polytope. Such a definition is called a vertex representation (V-representation or V-description). For a compact convex polytope, the minimal V-description is unique and it is given by the set of the vertices of the polytope. A convex polytope is called an integral polytope if all of its vertices have integer coordinates.

Intersection of half-spaces

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). 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.

A closed half-space can be written as a linear inequality:Branko Grünbaum'', 2nd edition, prepared by Volker Kaibel, Victor Klee, and Günter M. Ziegler, 2003, , , 466pp.

:$a_1 x_1 + a_2 x_2 + \cdots + a_n x_n \leq b$

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:

:$\begin a_ x_1 &&\; + \;&& a_ x_2 &&\; + \cdots + \;&& a_ x_n &&\; \leq \;&&& b_1 \\ a_ x_1 &&\; + \;&& a_ x_2 &&\; + \cdots + \;&& a_ x_n &&\; \leq \;&&& b_2 \\ \vdots\;\;\; && && \vdots\;\;\; && && \vdots\;\;\; && &&& \;\vdots \\ a_ x_1 &&\; + \;&& a_ x_2 &&\; + \cdots + \;&& a_ x_n &&\; \leq \;&&& b_m \\ \end$

where $m$ is the number of half-spaces defining the polytope. This can be concisely written as the matrix inequality:

:$Ax \leq b$

where $A$ is an $m\times n$ matrix, $x$ is an $n\times1$ column vector whose coordinates are the variables $x_1$ to $x_n$, and $b$ is an $m\times1$ column vector whose coordinates are the right-hand sides $b_1$ to $b_m$ of the scalar inequalities.

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. In this case, there is a ''unique'' minimal set of defining inequalities (up to multiplication by a positive number). Inequalities belonging to this unique minimal system are called essential. The set of points of a polytope which satisfy an essential inequality with equality is called a facet.

If the polytope is not full-dimensional, then the solutions of $Ax\leq b$ lie in a proper affine subspace of $\mathbb^n$ and the polytope can be studied as an object in this subspace. In this case, there exist linear equations which are satisfied by all points of the polytope. Adding one of these equations to any of the defining inequalities does not change the polytope. Therefore, in general there is no unique minimal set of inequalities defining the polytope.

In general the intersection of arbitrary ha