229
Efficiently Approximating the Minimum-Volume Bounding Box of a Point Set in Three Dimensions
arXiv:2512.12391v1 Announce Type: new
Abstract: $\renewcommand{\Re}{\mathbb{R}}$We present an efficient $O (n + 1/\varepsilon^{4.5})$-time algorithm for computing a $(1+\varepsilon$)-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 / \varepsilon^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.
Abstract: $\renewcommand{\Re}{\mathbb{R}}$We present an efficient $O (n + 1/\varepsilon^{4.5})$-time algorithm for computing a $(1+\varepsilon$)-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 / \varepsilon^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.
Anonymous