5

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


Only top voted, non community-wiki answers of a minimum length are eligible