<p>Your problem is solvable in polynomial time, as the dimension is fixed (at <span class="math-container">$d=3$</span>):</p>
<ul>
<li>Let <span class="math-container">$h_1,\ldots,h_n$</span> be an enumeration of all the bounding hyperplanes of the
polytopes <span class="math-container">$P_1,\ldots,P_k$</span> and <span class="math-container">$Q$</span>.</li>
<li>Compute the arrangement of <span class="math-container">$h_1,\ldots,h_n$</span> (the subdivision of three-dimensional space into vertices edges, faces, and cells). This can be done in polynomial time; see for instance <em>&quot;Constructing Arrangements of Lines and Hyperplanes with Applications&quot;</em> by H. Edelsbrunner, J. O’Rourke, and R. Seidel, SIAM Journal on Computing 15 (1986), pp 341–363.</li>
<li>Now check whether there exists some cell <span class="math-container">$C$</span> in the arrangement that is contained in <span class="math-container">$Q$</span> but in none of <span class="math-container">$P_1,\ldots,P_k$</span>.
(For checking containment, it is enough to check whether the vertices of
the cell satisfy the inequalities of the polytope.)</li>
<li>If such a cell <span class="math-container">$C$</span> exists, answer NO. Otherwise answer YES.</li>
</ul>
<p>If the dimension <span class="math-container">$d$</span> is given as part of the input, then your problem
(&quot;Does the union of <span class="math-container">$P_1,\ldots,P_k$</span> cover all of <span class="math-container">$Q$</span>&quot;) is coNP-hard.</p>

CC BY-SA 4.0
2020-06-29T09:42:09.907Z
Fantastic! Thanks.
Shaull
CC BY-SA 4.0
2020-07-06T09:42:43.840Z
I am planning to use thissolution in a paper, and I would be happy to give appropriate credit in the acknowledgements. If you'd like, please email me your name (my email address is on my website https://shaull.cswp.cs.technion.ac.il/).
If not, I'll acknowledge your username :)
Shaull
CC BY-SA 4.0
2020-07-07T08:52:38.403Z
@Shauli: For me it is fine, if you simply acknowledge "discussions with other users on cstheory.stackexchange".
Gamow
CC BY-SA 4.0
2020-07-07T09:16:13.017Z
Sure thing. As you wish.
Shaull
CC BY-SA 4.0
2020-06-29T09:33:00.353Z
2020-06-29T09:33:00.353Z
Gamow
<p>Consider a set <span class="math-container">$P_1,\ldots,P_k$</span> of polytopes in <span class="math-container">$\mathbb{R}^3$</span>, each given as an intersection of halfspaces with rational normals (in particular, they are all convex).
We are also given a target polytope <span class="math-container">$Q$</span>, which we can assume is the box <span class="math-container">$[-1,1]^3$</span>.</p>
<blockquote>
<p>What is the complexity class of deciding whether <span class="math-container">$Q\subseteq \bigcup_{i=1}^k P_i$</span>?</p>
</blockquote>
<p>If I'm not mistaken, <a href="https://www.semanticscholar.org/paper/The-Union-of-Convex-Polyhedra-in-Three-Dimensions-Aronov-Sharir/bbcbf370abd5daa0334b16ed38ee7c0e41e57fbe" rel="nofollow noreferrer">This paper by Aronov and Sharir</a> shows that the problem can be solved in expected polynomial time.</p>
<p>Is it known whether the problem is in P?</p>
<p>If it simplifies things, in my setting the polytopes are each defined by 4 non-affine halfspaces, so they are infinite cones.</p>

<reference-request><computational-geometry><convex-geometry>
Complexity of computing the union of H-polytopes in three dimensions
Shaull
# Complexity of computing the union of H-polytopes in three dimensions

(Asked by: username_0 on 2020-06-28)

Consider a set $P\_1,\ldots,P\_k$ of polytopes in $\mathbb{R}^3$, each given as an intersection of halfspaces with rational normals (in particular, they are all convex).
We are also given a target polytope $Q$, which we can assume is the box $[-1,1]^3$.

> What is the complexity class of deciding whether $Q\subseteq \bigcup\_{i=1}^k P\_i$?

If I'm not mistaken, [This paper by Aronov and Sharir](https://www.semanticscholar.org/paper/The-Union-of-Convex-Polyhedra-in-Three-Dimensions-Aronov-Sharir/bbcbf370abd5daa0334b16ed38ee7c0e41e57fbe) shows that the problem can be solved in expected polynomial time.

Is it known whether the problem is in P?

If it simplifies things, in my setting the polytopes are each defined by 4 non-affine halfspaces, so they are infinite cones.

**Tags:** reference-request, computational-geometry, convex-geometry


---

## 1 answers

### Answer by username_1 on 2020-06-29. Score: 5 | Accepted answer

Your problem is solvable in polynomial time, as the dimension is fixed (at $d=3$):

* Let $h\_1,\ldots,h\_n$ be an enumeration of all the bounding hyperplanes of the
  polytopes $P\_1,\ldots,P\_k$ and $Q$.
* Compute the arrangement of $h\_1,\ldots,h\_n$ (the subdivision of three-dimensional space into vertices edges, faces, and cells). This can be done in polynomial time; see for instance *"Constructing Arrangements of Lines and Hyperplanes with Applications"* by H. Edelsbrunner, J. O’Rourke, and R. Seidel, SIAM Journal on Computing 15 (1986), pp 341–363.
* Now check whether there exists some cell $C$ in the arrangement that is contained in $Q$ but in none of $P\_1,\ldots,P\_k$.
  (For checking containment, it is enough to check whether the vertices of
  the cell satisfy the inequalities of the polytope.)
* If such a cell $C$ exists, answer NO. Otherwise answer YES.

If the dimension $d$ is given as part of the input, then your problem
("Does the union of $P\_1,\ldots,P\_k$ cover all of $Q$") is coNP-hard.

> **Comments:**
> **username_0**: Fantastic! Thanks.  
> **username_0**: I am planning to use thissolution in a paper, and I would be happy to give appropriate credit in the acknowledgements. If you'd like, please email me your name (my email address is on my website https://shaull.cswp.cs.technion.ac.il/). If not, I'll acknowledge your username :)  
> **username_1**: @Shauli: For me it is fine, if you simply acknowledge "discussions with other users on cstheory.stackexchange".  
> **username_0**: Sure thing. As you wish.  

---

