# Converting convex hull from $V$-representation to $H$-representation

After looking at many articles and understanding various algorithms regarding finding extreme points and convex hull of a set of vectors in $$\mathbb{R}^d$$, I still have not figured out how to go from vertex representation of a polytope (specifically convex hull) to a half-space representation of it. I also know that it is called facet enumeration of some sort in the literature. I am looking for simple article discussing the exact problem I have already stated which is $$V\rightarrow H$$ I have a set of extreme points of a convex hull and I want to find the halfspace-representation of it. Any simple code, by simple of course I mean a program targetting the exact problem rather than being part of a bigger project like Qhull, would be really appreciated.

I have already read this and referred to references provided there but still none of them discussed anything regarding $$V$$-representation to $$H$$-representation conversion. Probably I have overlooked, I do appreciate if anyone has found anything anyways.

• A generic method to obtain the $H$-representation is to use the Fourier-Motzkin elimination: Let $V$ be a $(d \times n)$-matrix whose columns are a set of vectors. The convex hull of these vectors is given by the set $\{\mathbb x \mid \exists \mathbb u: \mathbb u\geq \mathbb 0, \mathbb{1}^T\mathbb u=1, \mathbb x = V\mathbb u\}$. Eliminating all coefficients $u_1,\dots,u_n$ of $\mathbb u$ from the system of linear inequalities by Fourier-Motzkin yields an $H$-representation. But this method is not efficient and the resulting $H$-representation will contain redundant constraints. May 14, 2019 at 10:24
• @WillemHagemann Is there any resource explaining this method completely? May 14, 2019 at 10:42
• The Fourier-Motzkin elimination should be found in almost any textbook on polytopes (Ziegler: Lecture on Polytopes) or linear prgramming (e.g. Matousek, Gärtner: Understanding and using Linear Programming). The system of linear inequalities is easily obtained by formalizing convex combination of vertices. May 14, 2019 at 14:33
• Be warned again: The elimination method is mainly of theoretical interest. For any non-trivial example the number of resulting linear inequalities will explode. May 14, 2019 at 14:48
• @WillemHagemann I welcome any working and understandable method available. May 14, 2019 at 17:54