We present an efficient O(n + 1/ε4.5)-time algorithm for computing a (1 + ε)-approximation of the minimum-volume bounding box of n points in ℝ3. We also present a simpler algorithm whose running time is O(n log n + n/ε3). We give some experimental results with implementations of various variants of the second algorithm.
- Bounding box
ASJC Scopus subject areas
- Control and Optimization
- Computational Mathematics
- Computational Theory and Mathematics