next up previous contents
Next: What is the face Up: Convex Polyhedron Previous: What is convex polytope/polyhedron?   Contents


What are the faces of a convex polytope/polyhedron?

Let $ P$ be a convex $ d$-polyhedron (or $ d$-polytope) in $ R^d$.

For a real $ d$-vector $ c$ and a real number $ d$, a linear inequality $ c^T x \le d$ is called valid for $ P$ if $ c^T x \le d$ holds for all $ x \in P$. A subset $ F$ of a polyhedron $ P$ is called a face of $ P$ if it is represented as

$\displaystyle F= P \cap \{ x: c^Tx = d \}
$

for some valid inequality $ c^T x \le d$. By this definition, both the empty set $ \emptyset$ and the whole set $ P$ are faces. These two faces are called improper faces while the other faces are called proper faces.

We can define faces geometrically. For this, we need to define the notion of supporting hyperplanes. A hyperplane $ h$ of $ R^d$ is supporting $ P$ if one of the two closed halfspaces of $ h$ contains $ P$. A subset $ F$ of $ P$ is called a face of $ P$ if it is either $ \emptyset$, $ P$ itself or the intersection of $ P$ with a supporting hyperplane.

The faces of dimension 0, $ 1$, $ \mathop{\it dim}\nolimits (P)-2$ and $ \mathop{\it dim}\nolimits (P)-1$ are called the vertices, edges, ridges and facets, respectively. The vertices coincide with the extreme points of $ P$ which are defined as points which cannot be represented as convex combinations of two other points in $ P$. When an edge is not bounded, there are two cases: either it is a line or a half-line starting from a vertex. A half-line edge is called an extreme ray.


next up previous contents
Next: What is the face Up: Convex Polyhedron Previous: What is convex polytope/polyhedron?   Contents
Komei Fukuda 2004-08-26