Home Bookmarks Papers Blog

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

Gill Barequet, and Sariel Har-Peled


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.

Appeared in SODA 99


Postscript, PDF

Source code
@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
}

Last modified: Fri Nov 14 10:56:16 CST 2014