Efficiently approximating the minimum-volume bounding box of a point set in three dimensions

We present an efficient O(n + 1/epsilon (4.5))-time algorithm for computing a (1 + epsilon)-approximation of the minimum-volume bounding box of n points in R-3. We also present a simpler algorithm whose running time is O(n log n + n/epsilon (3)). We give some experimental results with implementations of various variants of the second algorithm. (C) 2001 Academic Press.