1
$\begingroup$

I have a polyhedron which is defined by the following system of inequalities:

$$ \left\{ \begin{array}{c} x \leq 2 \\ y \leq 1 \\ x + y + z \leq 1\\ x + y + 2z \leq 1 \end{array} \right. $$ I want to write a general algorithm that can find the vertices of this polyhedron. This is my best solution so far:

0) Get in the form $Ax \leq b$

1) Since it is in $\mathbb{R}^3$, iterate through combinations of 3 rows of A, and see if the rank = 3 for those sub matrices. this tells us that the inequalities intersect.

2) For each of those combinations that have rank = 3, solve the system $A' x=b'$ where $A'$ and $b'$ are truncated versions of $A$ and $b$ just for the combination at hand.

3) Use this solution $x'$ to see if it is inside the polyhedron. If so, then a vertex is found.

I have not seen this process documented anywhere, and it seems to work on the cases i have tried. am I missing anything in this algorithm?

$\endgroup$
  • 1
    $\begingroup$ If you're just interested in something that will compute this for you, try Sage. If you actually want to know an algorithm, maybe try looking at the source there. They also reference the Frequently Asked Questions in Polyhedral Computation by Komei Fukuda, so maybe you can find something there also. $\endgroup$ – Avi Steiner Oct 10 '18 at 15:24
  • 1
    $\begingroup$ You could combine steps 1 and 2 by starting with the augmented matrix $[A\mid-b]$ and computing the null space of each three-row combination. If it’s one-dimensional, the resulting null vector gives the homogeneous coordinates of a vertex candidate. $\endgroup$ – amd Oct 10 '18 at 21:04
1
$\begingroup$

With CAS Maxima and my package "gt" (game theory):

enter image description here

Function "ext" compute extreme points of polyhedron.

$\endgroup$
  • $\begingroup$ This doesn’t really answer the question being asked. $\endgroup$ – amd Oct 10 '18 at 20:59

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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