 <p>You can find the 3d convex hull of all the vertex. Using the points of the convex hull you can form the faces of the convex hull. Then incline one by one all the faces parallel to x-axis. Then find the min x/y/z and max x/y/z along each face rotation.Calculate the volume using min x/y/z and max x/y/z. Find the index corresponding to the minimum volume. Rotate back this volume using the rotation you used for the corresponding face. This problem is similar to the 2d problem of minimum area rectangle. For minimum area rectangle the reference is <a href="http://gis.stackexchange.com/questions/22895/how-to-find-the-minimum-area-rectangle-for-given-points">http://gis.stackexchange.com/questions/22895/how-to-find-the-minimum-area-rectangle-for-given-points</a></p>