How to determine if a solid fits inside a given box in O(N^2)?

Question

I'm looking for an algorithm that will let me determine if a solid object can fit inside of a box (rectangular prism) with given dimensions. The solid may be rotated and translated to fit inside the box.

I already have a solution to this problem:

1. Calculate the minimum bounding box of the solid (known algorithm).
2. Determine if the minimum bounding box fits inside the other box (easy).

(EDIT: this is not a valid solution)

This works, but I am looking for a more efficient solution. The minimum bounding box algorithm runs in O(n^3) time where n is the number of vertices. I am hoping for an O(n^2) algorithm.

Note that instead of a "solid object" I may just as well be asking if the set of points which form the convex hull of the solid can fit inside the box.

Answer 1

You might want to take a look at this paper. It gives an algorithm than compute an 1+epsilon approximation of a 3D minimum bounding box in O(n log n + 1/epsilon^3) time.