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. I am particularly interested in the complexity.

  • $\begingroup$ 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. $\endgroup$ – Sasho Nikolov Oct 1 '15 at 15:38
  • $\begingroup$ 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$. $\endgroup$ – maomao Oct 1 '15 at 21:54

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.