Efficiently approximating the minimum-volume bounding box of a point set in three dimensions
By G. Barequet, Sariel Har-Peled. 2025
334 citations recorded by the source corpus.
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 R3. We also present a simpler algorithm whose running time is O(nlogn+n/?3). We give some experimental results with implementations of various variants of the second algorithm.
Subfields: Algorithms & Complexity
How researchers see this paper
The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.
In Algorithms & Complexity
Citations in the corpus
- Geometric Approximation via Coresets (2007, methodology): “The approach described in this section for approximating faithful measures had been used for geometric approximation algorithms before the framework of "-kernels was introduced; see e.g. [AP02, BH01 , Cha02, ZS02].”
- Approximating extent measures of points (2004, methodology): “Consequently, attention has shifted to developing approximation algorithms [10, 32].”
- The Algorithm Design Manual (2020, neutral): “This algorithm runs in near-linear time [BH01].”
- Reachability Analysis and its Application to the Safety Assessment of Autonomous Cars (2010, background): “vehicle A s(0) ∈ [40, 52] m v(0) ∈ [10, 12] m/s vehicle B s(0) ∈ [5, 17] m v(0) ∈ [10, 12] m/s vehicle C s(0) ∈ [25, 37] m v(0) ∈ [6, 8] m/s vehicle D s(0) ∈ [5, 17] m v(0) ∈ [8, 10] m/s”
- Geometric Approximation Algorithms (2011, methodology): “Our exposition follows roughly the work of Barequet and Har-Peled [BH01].”