6
$\begingroup$

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.

$\endgroup$
7
  • 1
    $\begingroup$ 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. $\endgroup$
    – Willem Hagemann
    May 14, 2019 at 10:24
  • 1
    $\begingroup$ @WillemHagemann Is there any resource explaining this method completely? $\endgroup$
    – FreeMind
    May 14, 2019 at 10:42
  • 1
    $\begingroup$ 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. $\endgroup$
    – Willem Hagemann
    May 14, 2019 at 14:33
  • 1
    $\begingroup$ Be warned again: The elimination method is mainly of theoretical interest. For any non-trivial example the number of resulting linear inequalities will explode. $\endgroup$
    – Willem Hagemann
    May 14, 2019 at 14:48
  • 1
    $\begingroup$ @WillemHagemann I welcome any working and understandable method available. $\endgroup$
    – FreeMind
    May 14, 2019 at 17:54

0

Reset to default

You must log in to answer this question.