# Removing redundant half-spaces that bound a convex polytope

I am computationally representing a convex polytope in $\mathbb{R}^n$ as a set $A$ of half-spaces that bound it; each such half-space is represented by a row vector $\mathbf{v} = \begin{bmatrix}v_1 & v_2 & \cdots & v_n & b\end{bmatrix}$ such that the half-space is the set $$\{(x_1, x_2, \dotsc, x_n) \in \mathbb{R}^n\ |\ v_1x_1 + v_2x_2 + \dotsb + v_nx_n \geq b\}.$$

The set $A$ then represents the convex polytope that is the intersection of all half-spaces in $A$.

Question: What algorithm can find the smallest subset of $A$ that represents the same convex polytope as $A$? This may depend on detecting if a half-space is "redundant", so how do you do that as well? Hopefully, the algorithms make use of the vectors $\mathbf{v}$.

-
You might want to check out convex hull algorithms. –  Tunococ Jan 28 '13 at 14:56

The polytope can be written as $Ax \geq b$ (where rows of $A$ contain your $v$ vectors). For each row $v = [v_1 v_2 \ldots v_n]$ of $A$, solve the LP $$\begin{array}{c} \min v^T x \\ Ax \geq b \end{array}$$
The half-space defined by this $v$ is not redundant if and only if the optimum value obtained above is equal to the corresponding $b$ value.