1
$\begingroup$

I am wondering whether there is an efficient algorithm to compute the basis of the set of vertices of a polytope.

Formally,

INPUT: a polytope $$\Xi=\{(\vec{a}_1\vec{x}+\vec{b}_1, \cdots, \vec{a}_m\vec{x}+\vec{b}_m)\mid C\vec{x}\leq d\}$$ and a subspace $span(E)$ where $E=\{e_1, \cdots, e_{\ell}\}$ is a given set of vectors

OUTPUT: a basis of the linear subspace spanned by $$V(\Xi)\setminus span(E),$$ where $V(\Xi)$ denotes the set of vertices of $\Xi$.

(Note that here $\Xi$ is given as an affine mapping of a polytope, which might complicates the problem a little bit.)

One can solve the problem in a straightforward approach, but I am asking for an ideally polynomial-time algorithm, or any evidence that this is not possible (e.g., NP-hardness).

|cite|improve this question
$\endgroup$
  • $\begingroup$ What do you mean by basis? A basis for the linear subspace spanned by these points? $\endgroup$ – Sasho Nikolov Sep 21 '15 at 14:58
  • $\begingroup$ yes, this is exactly what I am looking for. I will edit to make it clear. Thanks. $\endgroup$ – user35648 Sep 21 '15 at 15:39
  • $\begingroup$ Hmm. I hoe this is not a homework problem... I have not figured out all the details, but something along the following lines should work... Translate/rotate space such that $E$ is the span of the first $k$ coordinates. Find a vertex in the polytope that is not 0 in the $d-k$ coordinate, by maximizing a point in the direction of $(0, 0, ..., 0 [k times], 1,1, ..., 1)$ [or something along these lines]. Add this vector to $E$, and repeat the process. As long as $E$ does not cover the polytope, you are discovering a vertex at each step. And you should be done pretty quickly. $\endgroup$ – Sariel Har-Peled Sep 25 '15 at 2:37

Your Answer

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

Browse other questions tagged or ask your own question.