1
$\begingroup$

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.

$\endgroup$

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.