# Faster Algorithms for Convex Hulls

I was interested in the following:

Given two polyhedra $P_1, P_2$ specified in the form:

$$P_1 = {x : A_1x \le b_1 }$$ $$P_2 = {x : A_2x \le b_2 }$$

Whereas $x \in R^n$ and $b_1, b_2$ are real vectors of same "height" dimension as $P_1$ and $P_2$ respectively.

How does one determine the convex hull $C$ of these two polyhedra. Given in the form

$$C = {x: Qx \le \tau}$$

Whereas $Q,\tau$ should be the minimum number of inequalities necessary to specify the set.

I had posted this question on OR-Exchange:

https://www.or-exchange.org/questions/12714/how-to-determine-cuts-for-convex-hull

Which recommended fourier-motzkin elimination in conjunction with a simple scheme for including every-point in the hull.

My one qualm is this doubled the number of variables. And running fourier-motzkin would take exponential time to reduce the "excess" variables.

Is there a procedure that that doesn't take exponential time which maintains the same number of variables?

• Why would you be concerned about doubling the number of variables? It wouldn't surprise me to find that standard LP presolvers have theoretically exponential worst-case performance; but if that is the case, it just indicates that exponential complexity ought not be an automatic disqualifier, because they do work well in practice. – Michael Grant Aug 28 '15 at 13:49
• The convex hull. In the same number of dimensions, for the two polyhedra has number of (n-1) dimensional facets that is polynomially bounded on the number if (n-1) dimensional facets of the original two polyhedra. To eliminate the doubling of variables back to the original n, results in exponential amount of facets (many of which become redundant), I find it, at least odd that the convex hull, which isn't by itself very complex in MY formulation, needs an EXPTIME worst case algorithm. – frogeyedpeas Aug 28 '15 at 13:56
• @MichaelGrant so hence I am curious and hopeful if in this specific application a polynomial time hull generating algorithm exists. Where the hull is given as a system of inequalities – frogeyedpeas Aug 28 '15 at 13:58
• Well, the problem is that correct algorithms have to handle not just problems like yours which "isn't by itself very complex" but also ones that are! The exponential-time simplex algorithm for LP, for instance, rarely consumes exponential time in practice, but we know that it will for certain problems. Thus is the conundrum. – Michael Grant Aug 28 '15 at 13:59
• Please know, I voted your question up, I think it's a very interesting one. I just don't think your theoretical objectives will be satisfied. My suspicion however is that a practical implementation will work just fine for you, even if it is not theoretically tractable. – Michael Grant Aug 28 '15 at 14:01

As an example, let us look at cross-polytope $P_3$ in $\mathbb{R}^n$. It is the convex hull of all vertices obtained by all permutations of $(\pm1,0,\dots,0)$. Hence, it has $2n$ vertices and $2^n$ facets (see https://en.wikipedia.org/wiki/Cross-polytope) and its $\mathcal{H}$-representation $Qx \leq \tau$ has at least $2^n$ rows. On the other hand, the two simplices $P_1$ and $P_2$, where $$P_1 = conv\{(0,\dots,0), (1,0,\dots,0), (0,1,0,\dots,0), \dots, (0,\dots,0,1)\}$$ $$P_2 = conv\{(0,\dots,0), (-1,0,\dots,0), (0,-1,0,\dots,0), \dots, (0,\dots,0,-1)\},$$ have $n+1$ vertices and also $n+1$ facets. Hence, their (minimal) $\mathcal{H}$-representations $A_1x \leq b_1$ and $A_2x \leq b_2$ have $n+1$ rows each. It is crucial to note that the convex hull of $P_1$ and $P_2$ is exactly the cross-polytope $P_3$. This shows that in your setting (unless I missed something about the "specific application") it is impossible to have a procedure which does not take exponential time at worst.
• Great answer. Of course, the cross-polytope, being just the unit ball of the $\ell_1$ norm, can readily be represented using $O(n)$ inequalities if you are allowed to introduce additional variables. For instance, introducing $y\in\mathbb{R}^n$, we have: $$-y_i \leq x_i \leq y_i, \quad i=1,2,\dots,n,\quad \sum_i y_i \leq 1$$ – Michael Grant Aug 29 '15 at 15:40
• Thanks, Michael. BTW: I like the idea of introducing additional variables and solving the problems by means of linear programs afterwards. Often you don't need the actual $\mathcal{H}$-representation. – Willem Hagemann Aug 29 '15 at 16:18
• so this is intriguing... there are explicit cases where raising the dimension of the system, even if representing the same object, results in a more compact $\mathcal{H}$ representation – frogeyedpeas Feb 17 '16 at 0:10