Suppose you have two polytopes $P\_1, P\_2 \in \Bbb{R}^n$ given by


$$ P\_1 = \lbrace x: A\_1 x \le b\_1\rbrace$$
$$ P\_2 = \lbrace x: A\_2 x \le b\_2\rbrace $$


I wish to find their convex hull, that is a matrix $A\_3$ and vector $b\_3$ such that 


$$ A\_3 x \le b\_3$$


Is the convex hull of $P\_1$ and $P\_2$. Now I have two questions,


1. Is there a bound on the number of n-1 facets of the convex hull?, that is suppose $P\_1$ has $\alpha$ facets (so $A\_1$ has $\alpha$ inequalities) and $P\_2$ has $\beta$ facets (so $A\_2$ has $\beta$ inequalities) , then can we say for example that $A\_3$ has no more than $\gamma(\alpha + \beta)$ inequalities itself? Where $\gamma$ is some constant.
2. What is the best way to actually compute $A\_3,b\_3$ given $A\_1,b\_1$ and $A\_2,b\_2$?


Now I have a sketch of a procedure to do (2) but it seems far from elegant. I am also noticing there seems to be a lack of literature (at least after some surface level googling and discussing with two professors) regarding this specific problem. I'm pretty certain many people have considered it so I would also be requesting references about it.


Some Ideas for (1)
------------------


So $\gamma = 2$ seems plausible. If you take both polytopes, lift them to a higher dimensional space and orient them to be parallel. You can create a high dimensional antiprism with one facet for every face on each of the original polytopes (that is $\alpha + \beta$ new facets), and if you add it's to the current facet count you end up with twice of what you started with. I feel if you go back to the original dimension $n$ from this higher dimensional setting its only natural that some number of faces becomes "unnecessary". But this is a loose hand wavey kind of argument.


A definite upper bound is $\begin{pmatrix} \alpha \\ 2 \end{pmatrix}+ \begin{pmatrix} \beta \\ 2 \end{pmatrix} + \alpha + \beta $ and this is trivial from considering every n-1 facet that can be generated from an $n-2$ face of one polytope connected to a point on the other. But I have very sincere doubts about it being quadratic.



Efficiently Generating the Convex Hulls of Two Polytopes and Counting Faces
In general, computing the "H-representation" (your "$Ax \leq b$") of the convex hull of the union of two polytopes given by their H-representations is NP-hard: 



> 
> Tiwary. [On the Hardness of Computing Intersection, Union and Minkowski Sum of Polytopes](http://dx.doi.org/10.1007/s00454-008-9097-3). Discrete & Comput. Geom. 40(3):469-479. 
> 
> 
> 


In particular, this means you are unlikely to come up with a significantly elegant and efficient algorithm (certainly not a polynomial-time one, without showing $\mathsf{P} = \mathsf{NP}$ :)). It also means there unlikely to be a clean combinatorial characterization (that is, unless $\mathsf{P} = \mathsf{NP}$ or at least $\mathsf{NP} = \mathsf{coNP}$).


Regarding your intuition about bounding the number of facets: although you can lift to a higher-dimensional space and then project down, the act of projecting down can blow up the number of facets exponentially. There is a whole literature on "extended formulations" of polytopes (an extended formulation of a polytope $P \subseteq \mathbb{R}^n$ is a polytope $Q \subseteq \mathbb{R}^m$ together with an affine linear projection $\mathbb{R}^m \to \mathbb{R}^n$ that sends $Q$ to $P$), precisely because an extended formulation can in principle have exponentially fewer facets than the original polytope.


