3
$\begingroup$

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?

$\endgroup$

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.