4
$\begingroup$

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.

| cite | improve this question | | | | |
$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | | | | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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