OBB algorithm

Jeff Erickson jeffe at cs.uiuc.edu
Tue Sep 30 11:18:51 PDT 2003

Nash Aragam wrote:
> Can somebody send me a link for a quick and easy code sample/algorithm  
> for computing OBB on a cloud of 3D points? Thanks much,

I assume by "OBB" you mean "oriented bounding box", ie, the  
minimum-volume box, in any orientation, that contains all the points.

For the fastest known exact algorithm, which runs in O(n^3) time, see  
Joe O'Rourke's paper "Finding Minimal Enclosing Boxes" (International  
Journal of Computer and Information Sciences 14:183-199, 1985).  Sorry,  
it's not online, but it's worth the trip to the library.

Here's code to quickly compute a provably-good approximation:

For a description of the algorithm, see

Sariel and Gill's paper also includes a description of several  
commonly-used heuristics, none of which is guaranteed to be very good,  
although most of them are decent in practice.

			-- Jeff

The compgeom mailing lists: see
or send mail to compgeom-request at research.bell-labs.com with the line:
send readme
Now archived at http://www.uiuc.edu/~sariel/CG/compgeom/maillist.html.

More information about the Compgeom-announce mailing list