Smallest Rectangular Box that surrounds a polyhedron

Question

I'm looking for an algorithm that finds the smallest box enclosing a polyhedron.

My idea is as follows: find the largest side, and move the solid so that side aligns with the x axis. Find the next largest side that meets this side, and align it as close as possible to the z axis, while leaving the other side on x. Then, calculate the greatest differences in x, y and z. Use those dimensions to create the surrounding shape and then shift the box back to the object's original location.

Is there a more efficient strategy for this? Does my idea overlook some corner cases?

Edit: For now assume the object to be bounded is convex. Though, an answer for the general case would also be welcome.

Answer 1

The problem of finding minimal (volume) boxes for convex polyhedrons has been studied by O'Rourke, who proposes an O(n^3) algorithm:

J. O-Rourke. Finding minimal enclosing boxes. International Journal of Computer & Information Sciences, 1985, 14(3), p.183.

O'Rourke's algorithm finds the minimal enclosing box for a set of points in R^3 -- but this is clearly equivalent to finding the enclosing box for the polyhedron formed as the convex hull of the underlying point-set.

Contrary to what one might expect (and the approach you've described, if I've understood you correctly), the minimal box is not necessarily oriented such that a face of the polyhedron is coplanar with a face of the box! Note the animation shown here for a simple tetrahedron.

If you're happy with the idea of simply find an enclosing box that's relatively small, rather than the smallest enclosing box, there may be other (faster) heuristics that can be applied...