Given $n$ polytopes $P_1, \cdots, P_n$, each $P_i$ is given as the V-representation, i.e., a set of $m$ points as its set of vertices.

Furthermore, consider a variant of the Minkowski sum (somehow its weighted version). For $n$ nonnegative numbers $\vec{w}=(w_1, \cdots, w_n)$, we write $\sum_{\vec{w}}P_i=\{\sum_{i=1}^n w_i \vec{x}_i\mid \vec{x}_i\in P_i\}$.

The question is, given two weight vectors $\vec{w}$ and $\vec{v}$, decide whether $\sum_{\vec{w}}P_i = \sum_{\vec{v}}P_i$, where $=$ is interpreted as set equivalence.

It appears that a straightforward approach fails because $\sum_{\vec{w}}P_i$ as a polytope, might contain exponentially many vertices (?, order of $m^n$), so I only can show that the problem is in coNP. But is the problem in P, or it is coNP-hard as well?


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.