Faster algorithms for convex hulls

No, I don't think you will find a guaranteed fast algorithm, as the problem appears intractable in general, if I understand the below paper correctly. A quick search led me to, e.g.,

On the Hardness of Computing Intersection, Union and Minkowski Sum of Polytopes, by Hans Raj Tiwary


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.