Check if convex polytope contained inside a union of convex polytopes?

Question

Suppose I have a polytope $\mathcal P$ and a set of other polytopes $\{\mathcal S_0,\dots,\mathcal S_N\}$. Is there a computationally efficient way to check that $\mathcal P\subseteq\bigcup_{i=0}^{N}\mathcal S_i$? You can assume that both halfspace and vertex representations are available.

Answer 1

Baotic, M., "Polytopic Computations in Constrained Optimal Control" describes the polycover algorithm which does just this. The computational complexity has an exponential flavor, but in practice the algorithm performs pretty well.

Answer 2

I think your problem is difficult. Even the convex hull of the union of two polytopes is of recent (2017) interest.

Conforti, Michele, Marco Di Summa, and Yuri Faenza. "Balas formulation for the union of polytopes is optimal." arXiv preprint arXiv:1711.00891 (2017).