Re: OBB algorithm

[Jeff Erickson <jeffe@cs.uiuc.edu>]

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:
	http://valis.cs.uiuc.edu/~sariel/research/papers/00/diameter/ 
diam_prog.html

For a description of the algorithm, see
	http://valis.cs.uiuc.edu/~sariel/research/papers/98/bbox.html

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
http://netlib.bell-labs.com/netlib/compgeom/readme.html
or send mail to compgeom-request@research.bell-labs.com with the line:
send readme
Now archived at http://www.uiuc.edu/~sariel/CG/compgeom/maillist.html.