5
$\begingroup$

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.

$\endgroup$
5
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Fantastic! Thanks. $\endgroup$ – Shaull Jun 29 at 9:42
  • $\begingroup$ 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 shaull.cswp.cs.technion.ac.il). If not, I'll acknowledge your username :) $\endgroup$ – Shaull Jul 6 at 9:42
  • $\begingroup$ @Shauli: For me it is fine, if you simply acknowledge "discussions with other users on cstheory.stackexchange". $\endgroup$ – Gamow Jul 7 at 8:52
  • $\begingroup$ Sure thing. As you wish. $\endgroup$ – Shaull Jul 7 at 9:16

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.