We present an efficient O(n + 1/µ4.5) time
algorithm for computing an µ-approximation of the
minimum-volume bounding box of n points in
R3. We also present a simpler algorithm (for the
same purpose) whose running time is O(n log n + n /
µ3). We give some experimental results with
implementations of various variants of the second algorithm.
@Article{bh-eamvb-01,
author = {G.~Barequet and S.~{Har-Peled}},
journal = {J. Algorithms},
title = {Efficiently Approximating the Minimum-Volume
Bounding Box of a Point Set in Three Dimensions},
volume = {38},
issue = {1},
pages = {91--109},
year = 2001
}