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

$$We present an efficient $O(n+1\mathrm{/}{\epsilon }^{4.5})$-time algorithm for computing a $(1+\epsilon$)-approximation of the minimum-volume bounding box of $n$ points in ${\mathrm{\Re }}^3$. We also present a simpler algorithm (for the same purpose) whose running time is $O(n\log n+n\mathrm{/}{\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.