Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

HI,

I have a question regarding convex polytopes. Let us say I have the vertices of a polytope which I name as $ V = \{v_1,\cdots,v_k\}$. Each of the $v_k$ are n-dimensional vectors, i.e. $v_k \in R^n$. I would like to know if it is possible to write the polytope as intersection of half-spaces using the information from the vertices, i.e. can I write the polytops as $Ax\leq b, A \in \mathbb{R}^{m \times n}, b \in \mathbb{R}^m, x \in R^n$, where $m$ denotes the number of linear inequalities. Columns of A are not necessarily the vertices of the given polytope. An example, consider a polytope in $R^2_+$ with vertices $\{(0,1),(1,1),(2,0),(0,0)\}$. It can be observed that the corresponding half space representation is $Ax\le b$, where $$A=\begin{pmatrix}\\\ 0 & 1 \\\ 1 & 1 \\\ -1 & 0\\\ 0 & -1\end{pmatrix}, b = (1,2,0,0 )^T$$.

Thank You

share|improve this question
    
Are the columns of $A$ supposed to be the vectors in $V$? What is $m$? Thank you for clarifying. –  Patricia Hersh Nov 14 '12 at 23:05
2  
Yes, there are algorithms for this: see e.g. Ziegler's book. –  Dan Petersen Nov 14 '12 at 23:24
1  
Ziegler has more than one book, but I'm sure Dan means the one "Lectures on polytopes", which does discuss going back and forth between $V$-representation and $H$-representation (i.e. vertex representation and hyperplane representation) of a polytope. –  Patricia Hersh Nov 14 '12 at 23:27
    
I will try to get the book and see the relevant sections. –  user27396 Nov 14 '12 at 23:53
add comment

2 Answers 2

up vote 9 down vote accepted

The problem you identify is called the facet enumeration problem in the literature: Given the vertices, find a description of the facets. There has been quite a bit of work on this. For $n$ points in $d$ dimensions, $O(n^{\lfloor d/2 \rfloor})$ is achievable, and aymptotically worstcase optimal. But this is a theoretical result. The work of Avis & Fukuda, to which Igor refers, is quite practical, achieving a complexity of $O(d^{O(1)} n M)$ where $M$ is the size of the output description. Here is one reference:

D. Bremner, K. Fukuda, and A. Marzetta. "Primal-dual methods for vertex and facet enumeration." Discrete Comput. Geom., 20(3):333 – 357, 1998. (Citeseer link, which includes a PDF download link.)

If you are interested in software, permit me to also suggest polymake:
           polymake 24-cell

share|improve this answer
1  
polymake is a nice piece of software, once you get it installed, but that first step is highly nontrivial :( –  Igor Rivin Nov 15 '12 at 1:36
add comment

If you want software, there is Komei Fukuda's cdd et al.

share|improve this answer
    
I will check it and confirm. I believe it will work for me. –  user27396 Nov 14 '12 at 23:59
1  
cdd worked for me. Many Thanks for your answer. –  user27396 Nov 15 '12 at 1:42
add comment

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.