2
$\begingroup$

Consider a set of polytopes $P_i : i=1,2,...,k$ each of which has a structure as $P_i:= \{(x_{i1},x_{i2},..., x_{in})\; |\; x_{ij} \in [a_{ij}, b_{ij}] \subseteq [0,1]\}\;\; \text{for all}\;\; j=1,...,n$ and $\sum_j x_{ij}=1$. We define $P= CH (\cup_i P_i)$ where $CH$ stands for the convex hull.

On the other side, we have another set of polytopes $Q_t: t=1,2,..., r$ each of which defined similarly as $Q_t:= \{(y_{t1},y_{t2},..., y_{tn})\; |\; y_{tj} \in [c_{tj}, d_{tj}] \subseteq [0,1]\; \text{for all}\; j=1,...,n \; \text{and} \sum_j y_{tj}=1\}$. Then we define $Q= CH (\cup_t Q_t)$.

Please note that the number of polytopes $P_i$, i.e., k and the number of polytopes $Q_t$, i.e., r are not necessarily equal. However, both polytopes $P_i$ and $Q_t$ are defined in $\mathbb{R}^n$ as above.

Query: Is checking if $P=Q$ computationally hard?

$\endgroup$
  • 1
    $\begingroup$ This one looks tricky. One possible simplification: since $P,Q,R,S$ all lie in the affine subspace $\sum_ix_i=1$, so do the convex hulls, and the last coordinate $x_n$ of any relevant vector is uniquely determined by the others. So you could drop the last coordinate and replace the norm constraint with $x_1+\dots+x_{n-1}\le 1$. $\endgroup$ – Klaus Draeger Aug 14 '15 at 11:46
  • 3
    $\begingroup$ Cross-posted: scicomp.stackexchange.com/q/20449/713, math.stackexchange.com/q/1395844/11268 $\endgroup$ – Kirill Aug 17 '15 at 18:37
  • $\begingroup$ Simultaneous cross-posting is forbidden by our site policy (and most other Stack Exchange sites prohibit any cross-posting at all). Please don't cross-post. $\endgroup$ – D.W. Aug 19 '15 at 16:28
  • $\begingroup$ I am deleting the version in Math.Se. Because there's a bounty running here it is probably best to keep this copy. $\endgroup$ – Jyrki Lahtonen Aug 20 '15 at 20:17

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.