Take the 2-minute tour ×
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|improve this question
    
You might want to check out convex hull algorithms. –  Tunococ Jan 28 '13 at 14:56

1 Answer 1

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|improve this answer

Your Answer

 
discard

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.