<p>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.</p>

<p>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)$.</p>

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

<p><strong>Query</strong>: Is checking if $P=Q$ computationally hard?</p>

CC BY-SA 3.0
2015-08-14T11:46:34.703Z
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$.
Klaus Draeger
CC BY-SA 3.0
2015-08-17T18:37:28.210Z
Cross-posted: http://scicomp.stackexchange.com/q/20449/713, http://math.stackexchange.com/q/1395844/11268
Kirill
CC BY-SA 3.0
2015-08-19T16:28:59.560Z
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.
D.W.
CC BY-SA 3.0
2015-08-20T20:17:30.830Z
I am deleting the version in Math.Se. Because there's a bounty running here it is probably best to keep this copy.
Jyrki Lahtonen
<cc.complexity-theory><ds.algorithms><np-hardness><computational-geometry>
Convex hull of polytopes
Star
# Convex hull of polytopes

(Asked by: username_0 on 2015-08-14)

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?

**Tags:** cc.complexity-theory, ds.algorithms, np-hardness, computational-geometry
> **Comments:**
> **username_1**: 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$.  
> **username_2**: Cross-posted: http://scicomp.stackexchange.com/q/20449/713, http://math.stackexchange.com/q/1395844/11268  
> **username_3**: 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.  
> **username_4**: I am deleting the version in Math.Se. Because there's a bounty running here it is probably best to keep this copy.  

---

## 0 answers

