Efficiently Generating the Convex Hulls of Two Polytopes and Counting Faces

Question

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.

Answer 1

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. 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.