# Given the vertices of a convex polytope, How can we construct its Half-Space representation

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

-
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
Yes, there are algorithms for this: see e.g. Ziegler's book. –  Dan Petersen Nov 14 '12 at 23:24
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

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 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

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

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