Complexity of computing the union of H-polytopes in three dimensions

Question

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

Answer 1

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.