Sign up ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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}$.

share|cite|improve this question
You might want to check out convex hull algorithms. – Tunococ Jan 28 '13 at 14:56

2 Answers 2

up vote 3 down vote accepted

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.

share|cite|improve this answer
The "if and only if" in your claim is not true. Counterexample: Let $A=\begin{pmatrix}-1&0\\1&0\\0&-1\\0&1\\-1&-1\end{pmatrix}$ and $b=\begin{pmatrix}-1&-1&-1&-1&-2\end{pmatrix}^T$. The system $Ax \geq b$ describes a two dimensional box and the last row is redundant. (It is the sum of the first and the third row). Anyhow, your proposed LP yields the optimal value $-2$. – Willem Hagemann Jun 4 at 13:13
Or even more intuitive: In the system $x\geq 1, 2x\geq 2$ clearly $2x\geq 2$ is redundant. However, $\min\ 2x$ over the system yields $2$. – Willem Hagemann Jun 4 at 13:46

Let $Ax\leq b$ a system of linear inequalities. We denote the rows of $A$ by $A_k$ and the $k$th component of $b$ by $b_k$. Further, let $I$ be the set of all row indices of $Ax\leq b$. The $k$th row of $Ax \leq b$ is not redundant if and only if the LP

maximize $A_k$x subject to $A_ix \leq b_i$ $\forall i\in I\setminus\{k\}$ and $A_kx \leq b_k-1$

has an optimal value strictly greater than $b_k$.

(See page 52 and following Clarkson algorithm for more efficient methods.)

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.