<p>This answer expands on Chandra's comment, and on my follow up comment. The problem is indeed solvable in polynomial time. More general versions of it are also solvable in polynomial time: $\Theta$ could be given by a separation oracle, rather than explicitly, and it is also possible to solve an appropriately formulated version for a polyhedron.</p>

<p>Observe first that we have an efficient separation oracle for $P = f(\Theta) = C\Theta + d$. Indeed, deciding $y \in P$ amounts to solving the feasibility problem
$$
y = Cx\\
Ax \le b
$$
over the variables $x$. This problem can be solved with the usual techniques, e.g. the ellipsoid method. By the equivalence of separation and optimization, we can also solve arbitrary linear optimization problems over $P$.</p>

<p>Let us first assume $y \in P$: otherwise we are done. Then, by <a href="https://en.wikipedia.org/wiki/Carath%C3%A9odory%27s_theorem_(convex_hull)" rel="noreferrer">Caratheodory's theorem</a>, $y$ can be written as a convex combination of at most $m+1$ vertices of $P$. Moreover, such a convex combination is computable in polynomial time using a separation/optimization oracle for $P$: this is proved, for example, in <a href="https://books.google.ca/books?id=zEzW5mhppB8C&amp;lpg=PP1&amp;dq=Schrijver%20Theory%20of%20Linear%20and%20Integer%20Programming&amp;pg=PA185#v=onepage&amp;q&amp;f=false" rel="noreferrer">Corollary 14.1g</a> of Schrijver's Theory of Linear and Integer Programming. I.e., given an efficient separation oracle for $P$, we can construct a procedure that takes $y$ and returns vertices $v_1, \ldots, v_k$ of $P$, $k \le m+1$, and coefficients, $\lambda_1, \ldots, \lambda_k \in (0,1]$ such that $y = \sum_{i = 1}^k{\lambda_i v_i}$. Then, $y$ is a vertex of $P$ if and only if the procedure returns $v_1 = y$ and $\lambda_1 = 1$. It is clear that if this happens, $y$ is a vertex. Conversely, if this does not happen, then $y$ can be written as a convex combination of other points in $P$, which means that $y$ is not extremal, and, therefore, not a vertex.</p>

<p>Computing $v_1, \ldots, v_k$ and $\lambda_1, \ldots, \lambda_k$ using a separation/optimization oracle is not too hard. First you compute a vertex $u_1$ of $P$: figuring out  how to do this by optimizing over $P$ is a nice exercise. If $u_1 = y$, we are done. Otherwise, let $\ell$ be the half-line starting at $u_1$ and going through $y$, and let $z$ be the point where $\ell$ intersects the boundary of $P$. Then $z$ lies in a proper face of $P$, and we can recurse on that face to express $z$ as a convex combination of the vertices of the face. We finish by expressing $y$ as a convex combination of $z$ and $u_1$. See Schrijver's book for the details.</p>

CC BY-SA 3.0
2017-04-16T21:01:53.150Z
2017-04-16T21:01:53.150Z
Sasho Nikolov
<p>Inspired by the <a href="https://cstheory.stackexchange.com/questions/32587/checking-equivalence-of-two-polytopes">question</a>, I would like to ask the following question:</p>

<p>Input: A polytope specified by $\Theta=\{\vec{x}\mid A\vec{x}\leq b\}$, and its affine projection 
$f(\Theta)= \{(\vec{c}_1\cdot \vec{x}+ d_1, \cdots, \vec{c}_m\cdot \vec{x}+d_m)\mid A\vec{x}\leq b\}$, a point $\vec{y}\in \mathbf{Q}^m$</p>

<p>Decide whether $\vec{y}$ is a vertex of $f(\Theta)$, what's the complexity? </p>

<p>I strongly believe there is a polynomial time (one might obtain many $\vec{x}$'s which project to the given $\vec{y}$ and check one of these $\vec{x}$'s is a vertex of $\Theta$?). However, I do not have a clear algorithm. </p>

CC BY-SA 3.0
2015-10-07T10:19:58.203Z
I assume that $d_1,\dots,d_m$are supposed to be scalars (otherwise $c_i\cdot x + d_i$ makes no sense), i.e. you have $f(\Theta) = C\Theta + d$ for a matrix $C$ and vector $d$. Do you assume $C$ to have full row rank? Otherwise not all vertices of $\Theta$ will be mapped to vertices of $f(\Theta)$.
Klaus Draeger
CC BY-SA 3.0
2015-10-07T10:33:56.887Z
Yes, you are right; I will correct them; I do not assume $C$ to be full row ranked.
maomao
CC BY-SA 3.0
2015-10-07T12:59:41.177Z
Given a polytope $P$ and a point $x$ one can write $x$ as a convex combination of vertices of $P$ in polynomial time iff one can optimize or separate over $P$. This should help address your problem, I think.
Chandra Chekuri
CC BY-SA 3.0
2017-04-14T17:06:43.713Z
Unfortunately $P$ can have exponentially many vertices, so I don't think that approach provides a polynomial-time algorithm in general.
D.W.
CC BY-SA 3.0
2017-04-15T11:37:08.330Z
@D.W. Are you referring to Chandra's comment? It doesn't matter how many vertices $P$ has: any point in $P$ can be written as the convex combindation of at most $m + 1$ vertices, by Caratheodory's theorem. And such a convex combination can be found in polynomial time using a separation oracle for $P$, which can be constructed from a separation oracle for $\Theta$. (See e.g. page 185 of Schrijver's Integer and Linear Programming.) Since a point $y$ in $P$ is extremal (i.e. cannot be written as the convex combination of other vertices) if and only if it is a vertex, this solves the problem.
Sasho Nikolov
CC BY-SA 3.0
2017-04-15T19:53:07.683Z
@SashoNikolov, ahh, cool, I didn't know about that result!  Would you like to write an answer explaining that?
D.W.
<linear-programming><convex-geometry><polytope>
Decide whether a point is a vertex of a polytope?
maomao
# Decide whether a point is a vertex of a polytope?

(Asked by: username_0 on 2015-10-07)

Inspired by the [question](https://cstheory.stackexchange.com/questions/32587/checking-equivalence-of-two-polytopes), I would like to ask the following question:

Input: A polytope specified by $\Theta=\{\vec{x}\mid A\vec{x}\leq b\}$, and its affine projection
$f(\Theta)= \{(\vec{c}\_1\cdot \vec{x}+ d\_1, \cdots, \vec{c}\_m\cdot \vec{x}+d\_m)\mid A\vec{x}\leq b\}$, a point $\vec{y}\in \mathbf{Q}^m$

Decide whether $\vec{y}$ is a vertex of $f(\Theta)$, what's the complexity?

I strongly believe there is a polynomial time (one might obtain many $\vec{x}$'s which project to the given $\vec{y}$ and check one of these $\vec{x}$'s is a vertex of $\Theta$?). However, I do not have a clear algorithm.

**Tags:** linear-programming, convex-geometry, polytope
> **Comments:**
> **username_1**: I assume that $d_1,\dots,d_m$are supposed to be scalars (otherwise $c_i\cdot x + d_i$ makes no sense), i.e. you have $f(\Theta) = C\Theta + d$ for a matrix $C$ and vector $d$. Do you assume $C$ to have full row rank? Otherwise not all vertices of $\Theta$ will be mapped to vertices of $f(\Theta)$.  
> **username_0**: Yes, you are right; I will correct them; I do not assume $C$ to be full row ranked.  
> **username_2**: Given a polytope $P$ and a point $x$ one can write $x$ as a convex combination of vertices of $P$ in polynomial time iff one can optimize or separate over $P$. This should help address your problem, I think.  
> **username_3**: Unfortunately $P$ can have exponentially many vertices, so I don't think that approach provides a polynomial-time algorithm in general.  
> **username_4**: @D.W. Are you referring to Chandra's comment? It doesn't matter how many vertices $P$ has: any point in $P$ can be written as the convex combindation of at most $m + 1$ vertices, by Caratheodory's theorem. And such a convex combination can be found in polynomial time using a separation oracle for $P$, which can be constructed from a separation oracle for $\Theta$. (See e.g. page 185 of Schrijver's Integer and Linear Programming.) Since a point $y$ in $P$ is extremal (i.e. cannot be written as the convex combination of other vertices) if and only if it is a vertex, this solves the problem.  
> **username_3**: @SashoNikolov, ahh, cool, I didn't know about that result!  Would you like to write an answer explaining that?  

---

## 1 answers

### Answer by username_4 on 2017-04-16. Score: 5

This answer expands on Chandra's comment, and on my follow up comment. The problem is indeed solvable in polynomial time. More general versions of it are also solvable in polynomial time: $\Theta$ could be given by a separation oracle, rather than explicitly, and it is also possible to solve an appropriately formulated version for a polyhedron.

Observe first that we have an efficient separation oracle for $P = f(\Theta) = C\Theta + d$. Indeed, deciding $y \in P$ amounts to solving the feasibility problem
$$
y = Cx\\
Ax \le b
$$
over the variables $x$. This problem can be solved with the usual techniques, e.g. the ellipsoid method. By the equivalence of separation and optimization, we can also solve arbitrary linear optimization problems over $P$.

Let us first assume $y \in P$: otherwise we are done. Then, by [Caratheodory's theorem](https://en.wikipedia.org/wiki/Carath%C3%A9odory%27s_theorem_(convex_hull)), $y$ can be written as a convex combination of at most $m+1$ vertices of $P$. Moreover, such a convex combination is computable in polynomial time using a separation/optimization oracle for $P$: this is proved, for example, in [Corollary 14.1g](https://books.google.ca/books?id=zEzW5mhppB8C&lpg=PP1&dq=Schrijver%20Theory%20of%20Linear%20and%20Integer%20Programming&pg=PA185#v=onepage&q&f=false) of Schrijver's Theory of Linear and Integer Programming. I.e., given an efficient separation oracle for $P$, we can construct a procedure that takes $y$ and returns vertices $v\_1, \ldots, v\_k$ of $P$, $k \le m+1$, and coefficients, $\lambda\_1, \ldots, \lambda\_k \in (0,1]$ such that $y = \sum\_{i = 1}^k{\lambda\_i v\_i}$. Then, $y$ is a vertex of $P$ if and only if the procedure returns $v\_1 = y$ and $\lambda\_1 = 1$. It is clear that if this happens, $y$ is a vertex. Conversely, if this does not happen, then $y$ can be written as a convex combination of other points in $P$, which means that $y$ is not extremal, and, therefore, not a vertex.

Computing $v\_1, \ldots, v\_k$ and $\lambda\_1, \ldots, \lambda\_k$ using a separation/optimization oracle is not too hard. First you compute a vertex $u\_1$ of $P$: figuring out how to do this by optimizing over $P$ is a nice exercise. If $u\_1 = y$, we are done. Otherwise, let $\ell$ be the half-line starting at $u\_1$ and going through $y$, and let $z$ be the point where $\ell$ intersects the boundary of $P$. Then $z$ lies in a proper face of $P$, and we can recurse on that face to express $z$ as a convex combination of the vertices of the face. We finish by expressing $y$ as a convex combination of $z$ and $u\_1$. See Schrijver's book for the details.


---

