Question

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\le b, A \space is \space m \times n \space matrix, b \space is \space m \times 1, 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

Answer 1

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:
          

Answer 2

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