13
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Are the columns of $A$ supposed to be the vectors in $V$? What is $m$? Thank you for clarifying. $\endgroup$ Nov 14, 2012 at 23:05
  • 3
    $\begingroup$ Yes, there are algorithms for this: see e.g. Ziegler's book. $\endgroup$ Nov 14, 2012 at 23:24
  • 3
    $\begingroup$ 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. $\endgroup$ Nov 14, 2012 at 23:27
  • $\begingroup$ I will try to get the book and see the relevant sections. $\endgroup$
    – user27396
    Nov 14, 2012 at 23:53

2 Answers 2

14
$\begingroup$

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

$\endgroup$
1
  • 2
    $\begingroup$ polymake is a nice piece of software, once you get it installed, but that first step is highly nontrivial :( $\endgroup$
    – Igor Rivin
    Nov 15, 2012 at 1:36
4
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ I will check it and confirm. I believe it will work for me. $\endgroup$
    – user27396
    Nov 14, 2012 at 23:59
  • 1
    $\begingroup$ cdd worked for me. Many Thanks for your answer. $\endgroup$
    – user27396
    Nov 15, 2012 at 1:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.