<p>If you're okay with additional variables, then the answer is yes. This follows from <a href="http://www.math.ku.dk/~erhansen/web/OR/disjprog.pdf" rel="nofollow">Balas's extended formulation</a> for the disjunction of polyhedra. It shows that $\operatorname{convex}.\operatorname{hull} ( \cup_j P_j)$ admits an extended formulation of size at most $\sum_{j}(\operatorname{xc}(P_j)+1)$, where $\operatorname{xc}(\cdot)$ denotes extension complexity. (The extension complexity of $P_j$ is at most the number of inequalities defining $P_j$.)</p>

<p>I have not thought about whether this can be done in the original space of variables.</p>

CC BY-SA 3.0
2015-08-05T15:36:47.463Z
@ Austin: Now this question arises: If the extended formulation of convex hulls for two sets of polytopes are equivalent, can it be the case that the original convex hulls are also equivalent?
Star
CC BY-SA 4.0
2019-08-13T16:58:29.837Z
@how many variables do you need?
Turbo
CC BY-SA 3.0
2015-07-31T22:37:31.440Z
2015-07-31T22:37:31.440Z
Austin Buchanan
<p>Consider a set of polytopes $P_j\;\;j=1,2,\dots,r$ with the same structure as follows:</p>

<p>$P_j=\Big\{(x_{j1},\dots, x_{jt})\Big| \sum_{i=1}^t x_{ji}=1, x_{ji}\in [a_{ji},b_{ji}]\subseteq [0,1]\Big\}$ for $j=1\dots,r$. </p>

<p>Is it possible to derive the H-representation of the convex hull of the union of $P_j$s, i.e., ConvexHull$(\bigcup_j P_j)$, efficiently? </p>

<cc.complexity-theory><ds.algorithms><graph-algorithms><linear-programming><computational-geometry>
H-representation of convex hull
Star
# H-representation of convex hull

(Asked by: username_0 on 2015-07-31)

Consider a set of polytopes $P\_j\;\;j=1,2,\dots,r$ with the same structure as follows:

$P\_j=\Big\{(x\_{j1},\dots, x\_{jt})\Big| \sum\_{i=1}^t x\_{ji}=1, x\_{ji}\in [a\_{ji},b\_{ji}]\subseteq [0,1]\Big\}$ for $j=1\dots,r$.

Is it possible to derive the H-representation of the convex hull of the union of $P\_j$s, i.e., ConvexHull$(\bigcup\_j P\_j)$, efficiently?

**Tags:** cc.complexity-theory, ds.algorithms, graph-algorithms, linear-programming, computational-geometry

---

## 1 answers

### Answer by username_1 on 2015-07-31. Score: 3

If you're okay with additional variables, then the answer is yes. This follows from [Balas's extended formulation](http://www.math.ku.dk/~erhansen/web/OR/disjprog.pdf) for the disjunction of polyhedra. It shows that $\operatorname{convex}.\operatorname{hull} ( \cup\_j P\_j)$ admits an extended formulation of size at most $\sum\_{j}(\operatorname{xc}(P\_j)+1)$, where $\operatorname{xc}(\cdot)$ denotes extension complexity. (The extension complexity of $P\_j$ is at most the number of inequalities defining $P\_j$.)

I have not thought about whether this can be done in the original space of variables.

> **Comments:**
> **username_0**: @ Austin: Now this question arises: If the extended formulation of convex hulls for two sets of polytopes are equivalent, can it be the case that the original convex hulls are also equivalent?  
> **username_2**: @how many variables do you need?  

---

