<p>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:</p>

<ul>
<li>$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&lt;a_j^1$,</li>
<li>$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&gt;b_j^1$,</li>
<li>$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&lt;a_i^1$, </li>
<li>$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&gt;b_i^1$.</li>
</ul>

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

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

CC BY-SA 3.0
2015-08-07T14:46:51.697Z
2015-08-07T15:51:45.370Z
2015-08-07T15:51:45.370Z
Klaus Draeger
<p>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.  </p>

<cc.complexity-theory><ds.algorithms><linear-programming><computational-geometry>
Polytopes convex hull
Star
# Polytopes convex hull

(Asked by: username_0 on 2015-08-06)

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.

**Tags:** cc.complexity-theory, ds.algorithms, linear-programming, computational-geometry

---

## 1 answers

### Answer by username_1 on 2015-08-07. Score: 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* $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* $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.


---

