<p>I am wondering whether there is an <em>efficient</em> algorithm to compute the basis of the set of vertices of a polytope. </p>

<p>Formally, </p>

<p>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</p>

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

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

<p>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).</p>

CC BY-SA 3.0
2015-09-21T14:58:31.907Z
What do you mean by basis? A basis for the linear subspace spanned by these points?
Sasho Nikolov
CC BY-SA 3.0
2015-09-21T15:39:33.077Z
yes, this is exactly what I am looking for. I will edit to make it clear. Thanks.
user35648
CC BY-SA 3.0
2015-09-25T02:37:04.337Z
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.
Sariel Har-Peled
<ds.algorithms><linear-algebra><computational-geometry><convex-geometry>
Compute basis of vertex set of polytope
user35648
# Compute basis of vertex set of polytope

(Asked by: username_0 on 2015-09-21)

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).

**Tags:** ds.algorithms, linear-algebra, computational-geometry, convex-geometry
> **Comments:**
> **username_1**: What do you mean by basis? A basis for the linear subspace spanned by these points?  
> **username_0**: yes, this is exactly what I am looking for. I will edit to make it clear. Thanks.  
> **username_2**: 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.  

---

## 0 answers

