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, 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?
You cannot avoid an exponential blow-up in the number of resulting constraints.
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.