"In three dimensions, the problem is NP-complete even for two nested convex polyhedra":

> Mitchell, Joseph SB, and Subhash Suri. "Separation and approximation of polyhedral objects." *Computational Geometry* 5, no. 2 (1995): 95-114.
[doi](https://doi.org/10.1016/0925-7721(95)00006-U).

"In three dimensions, we show how to separate a convex polyhedron from a nonconvex polyhedron with a polyhedral surface whose facet-complexity is $O(\log n)$ times the optimal, where $n=|P|+|Q|$ is the complexity of the input polyhedra. Our algorithm runs in $O(n^4)$ time, but improves to $O(n^3)$ time if the two polyhedra are nested and convex."