Polytopes convex hull

Question

Assume $P_1$, $P_2$ and $Q$ are axis-parallel polytopes in $\mathbb{R}^d$. Is it true to say that checking $CH(P_1\cup P_2)\neq Q$ is NP-hard? There is a similar result for the general polytopes but I need the same for polytopes that their facets are parallel to the coordinate axises.

Answer 1

Assuming your polytopes are closed, I don't think this is true. Each of your polytopes $P_1,P_2,Q$ is a product of (possibly unbounded) intervals $I_i^1$, $I_i^2$, or $I_i^Q$, respectively, for $i=1,\dots,d$. Then $CH(P_1\cup P_2)$ is axis-parallel iff there are no $i,j$ with $i\neq j$ such that one of the following holds:

• $I_i^1\not\subseteq I_i^2$, $I_j^1$ has a lower bound $a_j^1$, and $I_j^2$ has a lower bound $a_j^2<a_j^1$,
• $I_i^1\not\subseteq I_i^2$, $I_j^1$ has an upper bound $b_j^1$, and $I_j^2$ has an upper bound $b_j^2>b_j^1$,
• $I_j^2\not\subseteq I_j^1$, $I_i^1$ has a lower bound $a_i^1$, and $I_i^2$ has a lower bound $a_i^2<a_i^1$,
• $I_j^2\not\subseteq I_j^1$, $I_i^1$ has an upper bound $b_i^1$, and $I_i^2$ has an upper bound $b_i^2>b_i^1$.

These are the cases in which $P_1\cup P_2$ (and therefore the convex hull) contains points $x,y$ with $x_i\neq y_i, x_j\neq y_j$, but at least one of the points obtained by replacing e.g. $x_i$ with $y_i$ in $x$ is not in the convex hull. This can be checked in polynomial time.

If the convex hull is axis-parallel, then it equals $Q$ iff $I_i^Q=I_i^1\cup I_i^2$ for all $i$, which also can be checked in polynomial time.