It is also possible to approximate the minimum bounding box volume, to within any constant factor greater than one, in linear time. The algorithm for doing this involves finding an approximation to the diameter of the point set, and using a box oriented towards this diameter as an initial approximation to the minimum volume bounding box. Then, this initial bounding box is partitioned into a grid of smaller cubes, and grid points near the boundary of the convex hull of the input are used as a coreset, a small set of points whose optimum bounding box approximates the optimum bounding box of the original input. Finally, O'Rourke's algorithm is applied to find the exact optimum bounding box of this coreset.