Minimal vertices 3D polygon fitting between inner and outer boundaries

Question

I have a set of 3D points representing a convex hull which I define as the inner boundary. The points are then offset outwards by a selected distance (the 'error') and I define this expanded hull as the outer boundary. The problem is finding the 3D polygon that fits only within the inner and outer boundaries with the minimum number of facets/vertices. At maximum error, a tetrahedron would be the resulting polygon, at minimum error it would be the original convex hull. As a 2D problem, I can see how it would be straightforward to make a brute force method of calculating this, but the 3D aspect throws me completely. Can anyone give any pointers as to how this can be solved, or if there is any software that can do this already?

Answer 1

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

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

The $O(\log n)$ factor derives from approximating the set cover problem.