3ドル$-dimensional convex hull using only a desired number of planes

Question

I would like to find the convex polytope with the smallest volume that envelops (contains) all the points of a given 3D point cloud and that can be constructed from only $k$ planes. This is similar to the convex hull problem, except that the convex hull can have an arbitrary large number of faces (limited only by $n,ドル the size of the input) while I am looking for a polytope with only $k$ faces (say, $k=8$).

Another way to phrase the problem:

Given a large 3D point cloud with $n$ points and a small number $k,ドル find $k$ planes so that all points are in the polytope created by the union of the planes and that polytope has the smallest possible volume.

All "exact" convex hull algorithms I looked at (Gift wrapping, Graham scan, Quickhull) produce a polytope with a lot of faces and I can't see a way of reducing the number of faces after computing the convex hull (by merging adjacent faces or so until the face count is down to k or less). From the "approximative" convex hull algorithms, I have thought of computing the discrete orientation polytope (k-DOP, see this PPT), but that would not be optimal (the volume would not be minimal) because it requires that each face has a parallel "partner face".

I would be happy to hear your thoughts on how to do this!

• orlp: Take a look at "Minimum area circumscribing Polygons" by Alok Aggarwal, J.S. Chang and Chee K. Yap, and see if you can generalize to three dimensions.