next up previous contents
Next: What is the vertex Up: Convex Polyhedron Previous: What is convex hull?   Contents


What is the Minkowski-Weyl theorem for convex polyhedra?

The Minkowski-Weyl Theorem states every polyhedron is finitely generated and every finitely generated set is a polyhedron. More precisely, for two subsets $ P$ and $ Q$ of $ R^d$, $ P+Q$ denotes the Minkowski sum of $ P$ and $ Q$:

$\displaystyle P + Q$ $\displaystyle =$ $\displaystyle \{ p +q: p \in P$    and $\displaystyle q \in Q \}.$  

Theorem 5 (Minkowski-Weyl's Theorem)   For a subset $ P$ of $ R^d$, the following statements are equivalent:
(a)
P is a polyhedron, i.e., for some real (finite) matrix $ A$ and real vector $ b$, $ P=\{ x : A x \le b \}$;

(b)
There are finite real vectors $ v_1, v_2, \ldots, v_n$ and $ r_1, r_2, \ldots, r_s$ in $ R^d$ such that
$ P = conv(v_1, v_2, \ldots, v_n) + nonneg(r_1, r_2, \ldots, r_s)$.

Thus, every polyhedron has two representations of type (a) and (b), known as (halfspace) H-representation and (vertex) V-representation, respectively. A polyhedron given by H-representation (V-representation) is called H-polyhedron (V-polyhedron).


next up previous contents
Next: What is the vertex Up: Convex Polyhedron Previous: What is convex hull?   Contents
Komei Fukuda 2004-08-26