Given the vertices of a convex polytope, how can we construct its half-space representation?

Question

Let us say I have the vertices of a polytope $V = \{v_1,\dots,v_k\} \subset \mathbb R^n$. Is it possible to write $V$ as intersection of half-spaces using the information from the vertices, i.e., can I write the polytope in the form $Ax \leq b$ where $A \in \mathbb{R}^{m \times n}$ and $b \in \mathbb{R}^m$?

The columns of $A$ are not necessarily the vertices of the given polytope. An example, consider a polytope in $\mathbb 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}$$

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