Algorithms for a Minimum Volume Enclosing Simplex in Three Dimensions

We develop a combinatorial algorithm for determining a minimum volume simplex enclosing a set of points in R³. If the convex hull of the points has n vertices, then our algorithm takes Θ(n⁴) time. Combining our exact but slow algorithm with a simple but crude approximation technique, we also develop an ε-approximation algorithm. The algorithm computes in O(n + 1/ε⁶) time a simplex whose volume is within (1 + ε) factor of the optimal for any ε > 0.