<p>Given $n$ polytopes</p>

<p>$$\begin{align*}
P_1&amp;=\{(f^1_1(\vec{x}_1), \cdots, f^1_m(\vec{x}_1))\mid A_1\vec{x}_1\leq b_1\}\\
P_2&amp;=\{(f^2_1(\vec{x}_2), \cdots, f^2_m(\vec{x}_2))\mid A_2\vec{x}_2\leq b_2\}\\
\vdots\\
P_n&amp;=\{(f^n_1(\vec{x}_2), \cdots, f^n_m(\vec{x}_2))\mid A_n\vec{x}_n\leq b_n\}\\
\end{align*}$$
where $f$'s are <em>affine</em> mappings. Namely, they are of <strong>the form</strong> $\vec{c}\cdot \vec{x} +d$. (We note that each $P_i$ is a polytope because it is an affine projection of the polytope $A_i\vec{x}_i\leq b_i$.)</p>

<p>We assume that any $\vec{x}_i$ and $\vec{x}_j$ are disjoint. </p>

<p>We can form the Minkowski sum of $P_i$'s, i.e., $P=\sum_{i=1}^n P_i$. </p>

<p>Given $n$ points $\vec{y}_1, \cdots, \vec{y}_n$, decide whether for all $1\leq i\leq n$
$\vec{y}_i$ is a vertex of $P_i$ and $\sum_{i=1}^n \vec{y}_i$ is a vertex of $P$? </p>

<p>The question is inspired by the recent <a href="https://cstheory.stackexchange.com/questions/32587/checking-equivalence-of-two-polytopes">question</a>. I am particularly interested in the complexity. </p>

CC BY-SA 3.0
2015-10-01T15:38:48.740Z
I don't know why you present the polytopes in this funky form rather than in the standard $\{x: Ax \leq b\}$. It is easy to convert what you have to the standard form.
Sasho Nikolov
CC BY-SA 3.0
2015-10-01T21:54:37.663Z
I think user35648 wants to emphasize the polytope is an affine projection. Are you sure that this can be easily convert to the standard form? Note that the length of $\vec{x}$ might be different from $m$.
maomao
<linear-algebra><linear-programming><computational-geometry><polytope>
Check whether a point is a vertex of Minkowski sum of polytopes
user35648
# Check whether a point is a vertex of Minkowski sum of polytopes

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

Given $n$ polytopes

$$\begin{align\*}
P\_1&=\{(f^1\_1(\vec{x}\_1), \cdots, f^1\_m(\vec{x}\_1))\mid A\_1\vec{x}\_1\leq b\_1\}\\
P\_2&=\{(f^2\_1(\vec{x}\_2), \cdots, f^2\_m(\vec{x}\_2))\mid A\_2\vec{x}\_2\leq b\_2\}\\
\vdots\\
P\_n&=\{(f^n\_1(\vec{x}\_2), \cdots, f^n\_m(\vec{x}\_2))\mid A\_n\vec{x}\_n\leq b\_n\}\\
\end{align\*}$$
where $f$'s are *affine* mappings. Namely, they are of **the form** $\vec{c}\cdot \vec{x} +d$. (We note that each $P\_i$ is a polytope because it is an affine projection of the polytope $A\_i\vec{x}\_i\leq b\_i$.)

We assume that any $\vec{x}\_i$ and $\vec{x}\_j$ are disjoint.

We can form the Minkowski sum of $P\_i$'s, i.e., $P=\sum\_{i=1}^n P\_i$.

Given $n$ points $\vec{y}\_1, \cdots, \vec{y}\_n$, decide whether for all $1\leq i\leq n$
$\vec{y}\_i$ is a vertex of $P\_i$ and $\sum\_{i=1}^n \vec{y}\_i$ is a vertex of $P$?

The question is inspired by the recent [question](https://cstheory.stackexchange.com/questions/32587/checking-equivalence-of-two-polytopes). I am particularly interested in the complexity.

**Tags:** linear-algebra, linear-programming, computational-geometry, polytope
> **Comments:**
> **username_1**: I don't know why you present the polytopes in this funky form rather than in the standard $\{x: Ax \leq b\}$. It is easy to convert what you have to the standard form.  
> **username_2**: I think user35648 wants to emphasize the polytope is an affine projection. Are you sure that this can be easily convert to the standard form? Note that the length of $\vec{x}$ might be different from $m$.  

---

## 0 answers

