Subject: RE:SMALLEST BOUNDING BOX

From: [email-masked] (Marvin Waldman)
Date: Thu, 13 Jun 1996 10:05:24 -0700

Since this thread will not seem to die, I thought I would throw in my own 
observations about the subject.  Using principal axes is probably a 
reasonable approximation for most molecules, but is certainly not the
full analytical solution.  Implementing some kind of optimization procedure
(genetic algorithm, simplex, etc.) to calculate the bounding box for
different orientations of the molecule is also quite reasonable, but
is not guaranteed to find a global minimum solution (local minima are possible).

A correct analytical procedure can be written fairly straightforwardly and
involves determining something called the convex hull for the molecule
by generating planes corresponding to all triplets of points and then
finding the distance from each of the remaining points to each of the planes.
Any planes for which there are points on both sides of the plane can
be immediately rejected.  The remaining planes form the convex hull of
the molecule.  For each of these planes, determine the maximum distance
to all remaining points.  Take the point maximally distant to the plane,
and generate a parallel plane through it.  Project all the remaining
points onto one of the parallel planes.  Now the problem is reduced
to finding the bounding 2 dimensional rectangle for these projected
points.  This can be done by finding all pairs of lines through the
points.  Reject any lines for which there are points on both sides
of the line.  The remaining lines form the 2 dimensional hull for
these points.  For each such line, find the maximally distance point.
Draw a line through this point parallel to its corresponding line.
Now project all the remaining points onto one of these lines.
Find the two points with largest extent along this line.  Draw a
pair of lines through them perpendicular to the original line.  Now take
the 4 lines (which generate the bounding rectangle in the plane) and
generate planes through them perpendicular to the original plane.  The
6 planes generate a bounding box for the original points.  After generating
all such possible bounding boxes (considering all planes of the 3D
convex hull for the molecule and all lines for the 2D convex hull for the 
projected points in each of these planes), choose the bounding box with the
smallest volume (or surface area or whatever other criterion you may
choose to apply).  

The above algorithm while correct and fully analytical is not 
optimal.  There are many ways to improve the efficiency of this procedure.
The problem has been investigated at length in the computer math literature.
A good discussion may be found in:

"Putting objects into boxes", by R.R. Martin and P.C. Stephenson in
Computer Aided Design, Volume 20, pp. 506-514, (1988).

By the way, the above only discusses a box enclosing the points which
I assume correspond to the atoms of the molecule.  Possibly a more
relevant application to molecular modeling is the minimum bounding
box enclosing the VDW ( dare I say v(V?)an der Waals('?) ) surface
of the molecule.  This has a different (although related) solution
to the above problem.

Regards,

Marvin Waldman, Ph.D.
Director, Rational Drug Design
Molecular Simulations Inc.
e-mail: [email-masked]
Web:    http://www.msi.com