# Computing the convex hull of several polyhedra

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)$?

• 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 Mar 16 '14 at 14:55
• Thanks for the comment. I modified the question accordingly. – Lior Eldar Mar 16 '14 at 15:12
• The convex hull might have exponentially many vertices and exponentially many faces. – Yury Mar 16 '14 at 15:20
• 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 Mar 16 '14 at 16:43
• @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 Mar 17 '14 at 1:13