<p>Let $K_1,..., K_m$ be a set of $m$ polyhedra, with $K_i\subseteq \mathbf{R}^n$, for all $i\in [m]$, and each is described by a set of $poly(n)$ linear inequalities.
How easy is it to compute an efficient description (half-space representation, or vertex representation) of the convex hull:
$$
conv(K_1,...,K_n).
$$
Is there an algorithm running in time $poly(n)$,  $poly(n,m)$ ?</p>

<p>Similarly, given membership oracles to $K_1,...,K_n$ can one determine in polynomial time, w.r.t. these oracles, whether a point $x$ belongs to $conv(K_1,...,K_n)$?</p>

CC BY-SA 3.0
2014-03-16T14:55:39.530Z
This is impossible since the number of facets of the convex hull can be as large as (roughly) $m^{n/2}$, even if each $K_i$ is a single point.
Yoshio Okamoto
CC BY-SA 3.0
2014-03-16T15:12:28.587Z
Thanks for the comment.  I modified the question accordingly.
Lior Eldar
CC BY-SA 3.0
2014-03-16T15:20:08.950Z
The convex hull might have exponentially many vertices and exponentially many faces.
Yury
CC BY-SA 3.0
2014-03-16T16:20:35.863Z
http://en.wikipedia.org/wiki/Convex_hull_algorithms#Higher_dimensions
Kaveh
CC BY-SA 3.0
2014-03-16T16:43:56.527Z
There is an oracle that given a point $x$ determines whether $x$ belongs to the convex hull of $K_1,\dots, K_n$ in polynomial-time. If $x$ is not in the convex hull, the oracle finds a separating hyperplane.
Yury
CC BY-SA 3.0
2014-03-16T18:57:06.963Z
Thanks Yury.  I have modified the question accordingly, since essentially this is what I was looking for.  Can I kindly ask that you supply some reference for the claim you mentioned?
Lior Eldar
CC BY-SA 3.0
2014-03-17T01:13:00.937Z
@LiorEldar: We construct a separation oracle that determines whether $\hat x$ is in the convex null or not. Here is how the oracle works. We look for a separating hyperplane of the form $c^T x \geq c_0$ that separates $\hat x$ with each of $K_i$. We write a linear program with variables $c = (c_1,\dots, c_d)^T$ and $c_0$. We write an LP condition that $c^T\hat x \geq c_0$ and that each $K_i$ lies on the other side of the hyperplane. The latter condition for $K_i$ means that $(c, c_0')$ is a convex combination of face hyperplanes of $K_i$ and $c_0' \leq c_0$.
Yury
CC BY-SA 3.0
2014-03-17T04:09:17.627Z
@Yury I think that counts as an answer.
Suresh Venkat
CC BY-SA 3.0
2014-03-17T08:09:12.327Z
@Yury: I don't see how the latter condition is formulated as an LP?   For each $K_i$ you would need the following condition: that any point $y$ for which all linear constraints of $K_i$ hold, also has $c^T y< c_0$, no?.  Also, I certainly agree that this is an answer.
Lior Eldar
CC BY-SA 3.0
2014-03-17T09:52:32.473Z
@Yury: The polyhedra $K_i$ are given by membership oracles, and so we don't know (or cannot extract) an inequality description of $K_i$ that is needed for your formulation.
Yoshio Okamoto
CC BY-SA 3.0
2014-03-17T15:33:22.490Z
@YoshioOkamoto: I was answering the question Lior asked me. See the original statement of the question and the discussion above (note that the question was edited several times). If sets $K_i$ are given by oracles, then we can still construct a membership oracle for the convex hull of $K_i$ but the oracle is a bit more complicated.
Yury
<cg.comp-geom><optimization><convex-optimization><convex-geometry>
Computing the convex hull of several polyhedra
Lior Eldar
# Computing the convex hull of several polyhedra

(Asked by: username_0 on 2014-03-16)

Let $K\_1,..., K\_m$ be a set of $m$ polyhedra, with $K\_i\subseteq \mathbf{R}^n$, for all $i\in [m]$, and each is described by a set of $poly(n)$ linear inequalities.
How easy is it to compute an efficient description (half-space representation, or vertex representation) of the convex hull:
$$
conv(K\_1,...,K\_n).
$$
Is there an algorithm running in time $poly(n)$, $poly(n,m)$ ?

Similarly, given membership oracles to $K\_1,...,K\_n$ can one determine in polynomial time, w.r.t. these oracles, whether a point $x$ belongs to $conv(K\_1,...,K\_n)$?

**Tags:** cg.comp-geom, optimization, convex-optimization, convex-geometry
> **Comments:**
> **username_1**: This is impossible since the number of facets of the convex hull can be as large as (roughly) $m^{n/2}$, even if each $K_i$ is a single point.  
> **username_0**: Thanks for the comment.  I modified the question accordingly.  
> **username_2**: The convex hull might have exponentially many vertices and exponentially many faces.  
> **username_3**: http://en.wikipedia.org/wiki/Convex_hull_algorithms#Higher_dimensions  
> **username_2**: There is an oracle that given a point $x$ determines whether $x$ belongs to the convex hull of $K_1,\dots, K_n$ in polynomial-time. If $x$ is not in the convex hull, the oracle finds a separating hyperplane.  
> **username_0**: Thanks Yury.  I have modified the question accordingly, since essentially this is what I was looking for.  Can I kindly ask that you supply some reference for the claim you mentioned?  
> **username_2**: @LiorEldar: We construct a separation oracle that determines whether $\hat x$ is in the convex null or not. Here is how the oracle works. We look for a separating hyperplane of the form $c^T x \geq c_0$ that separates $\hat x$ with each of $K_i$. We write a linear program with variables $c = (c_1,\dots, c_d)^T$ and $c_0$. We write an LP condition that $c^T\hat x \geq c_0$ and that each $K_i$ lies on the other side of the hyperplane. The latter condition for $K_i$ means that $(c, c_0')$ is a convex combination of face hyperplanes of $K_i$ and $c_0' \leq c_0$.  
> **username_4**: @Yury I think that counts as an answer.  
> **username_0**: @Yury: I don't see how the latter condition is formulated as an LP?   For each $K_i$ you would need the following condition: that any point $y$ for which all linear constraints of $K_i$ hold, also has $c^T y< c_0$, no?.  Also, I certainly agree that this is an answer.  
> **username_1**: @Yury: The polyhedra $K_i$ are given by membership oracles, and so we don't know (or cannot extract) an inequality description of $K_i$ that is needed for your formulation.  
> **username_2**: @YoshioOkamoto: I was answering the question Lior asked me. See the original statement of the question and the discussion above (note that the question was edited several times). If sets $K_i$ are given by oracles, then we can still construct a membership oracle for the convex hull of $K_i$ but the oracle is a bit more complicated.  

---

## 0 answers

