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

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


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.