Efficiently Approximating the Minimum-Volume Bounding Box of a Point Set in Three Dimensions

Abstract

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 ${\Re }^3$. We also present a simpler algorithm (for the same purpose) 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. The implementation of the algorithm described in this paper is available online https://github.com/sarielhp/MVBB.