minimum bounding box for a convex polygon

Paul Henning phenning at
Thu Nov 16 16:10:44 PST 2000

It should be noted that Gottschalk's algorithm produces an _approximate_
minimum bounding box.   Unfortunately, it will bound a polygon like
[(1,0),(0,1),(-1,0),(0,-1)] by an axis-aligned box, which is not a great
bound.   All that being said, I haven't found a better approach for 3-D.
O'Rourke has an algorithm in:

  author =       {O'Rourke, Joseph},
  title =        {Finding Minimal Enclosing Boxes},
  journal =      {International Journal of Computer and Information Sciences},
  year =         1985,
  volume =       14,
  number =       3,
  pages =        {183--199},

for true minimal boxes, but it is a bit tricky to implement.


"Dickinson, John" wrote:

> If you want an axis-orientated bounding box that will work and is very easy
> to do.  If not then search for orientated bounding box algorithms on the
> net.  S.  Gottschalk implemented a 3D orientated bounding box algorithm see
> the following paper. and his site:
> OBB-Tree: A Hierarchical Structure for Rapid Interference Detection , S.
> Gottschalk, M. C. Lin and D. Manocha (27 pages PostScript, ) 493K, Technical
> report TR96-013, Department of Computer Science, University of N. Carolina,
> Chapel Hill. Proc. of ACM Siggraph'96.
> John

The compgeom mailing lists: see
or send mail to compgeom-request at with the line:
send readme
Now archived at

More information about the Compgeom-announce mailing list