Subject: SMALLEST BOUNDING BOX - THE PROBLEM THAT WOULD NOT DIE

From: [email-masked] (Marvin Waldman)
Date: Fri, 14 Jun 1996 10:11:10 -0700

Before some clever computational geometrist(?) flames me, I thought
I would flame myself.  My previous "analytical" solution does not
even work for the simple case of a tetrahedron!

Cory C. Pye wrote:
>the likelihood that any two faces opposite to each other would be parallel is 
>small, and given any face A, B, C, and the point P farthest from the plane 
>containing it, a slight rotation of the normal of the plane toward 
>avg(A,B,C)-P would shorten the distance from the plane to P, and thus the 
>most likely scenario would entail a vertex pair as being on the two planes.

This appears to be correct for the case of a tetrahedron.  If one
constructs a tetrahedron of edge length 1, then I calculate its height to be
sqrt(2/3).  So, constructing a plane containing one face and another
plane parallel and intersecting the opposite point has the two planes
a distance of sqrt(2/3) apart.  Projecting the 4 points onto one of the
planes produces a triangle with a base of 1 and a height of sqrt(3)/2.
The fourth point (from the opposite plane) is inside the triangle.
The minimum bounding rectangle for this triangle is then adjacent to one
edge and intersects the opposite point.  So, the bounding box for the
construction I originally proposed has a volume of:

   sqrt(2/3) * 1 * sqrt(3)/2 = 1/sqrt(2)

Now, consider the following construction.  Construct a plane intersecting
one edge of the tetrahedron and parallel to the opposite (non-adjacent)
edge.  Construct a plane for the opposite edge parallel to the first
plane.  The two planes are a distance 1/sqrt(2) apart (proof is left to
the reader - have fun).  Projecting the four points onto one of these
planes produces a square with diagonals equal to 1 and edges equal to
1/sqrt(2).  So the bounding box for this construction has a volume of:

    1/sqrt(2) * 1/sqrt(2) * 1/sqrt(2) = 1/( 2*sqrt(2) )

which is clearly smaller than the original "solution".

The paper of Martin and Stephenson that I referred to in my earlier
posting mentions that the bounding rectangle of minimum area (and I
think minimum perimeter) must be adjacent to one of the edges of the
2D convex hull.  I had incorrectly assumed that this property could
be extended to 3 dimensions and would work for any metric!  The extension
to any metric was clearly a case of faulty (stupid!) reasoning on my
part.  However, it was somewhat surprising that the metrics that do
work for 2 dimensions using the convex hull approach (rectangle adjacent
to one of the edges works for minimum area and maybe perimeter) don't
work analogously in 3 dimensions (box adjacent to one of the faces doesn't
work for minimum volume or area).  It was only after reading Cory Pye's
posting that I began to think harder about the problem, and discovered
the alternate solution for the tetrahedron.

With all this in mind, I would now like to propose an addendum to my
original solution.  I will not claim it works all the time, as I don't
have a proof, and I would be interested if anyone can find a counter-example.
Consider all the bounding boxes formed from planes adjacent to one face
of the 3D convex hull as before.  In addition, consider the following
set of bounding boxes.  For each pair of non-adjacent edges of the
3D convex hull, form the pair of planes going through one edge and parallel
to the other edge.  If either of these planes penetrates the convex
hull, reject this pair.  Otherwise, project all the points onto one of
the planes and form the 2D bounding rectangle for these points using
the 2D convex hull as before.  Consider all the bounding boxes formed
from this approach (planes coincident with pairs of edges) and the bounding
boxes from the original approach (planes coincident with a face and its
furthest point) and select the box of minimum volume (or maybe area).
Once again, many improvements may be envisioned to the above algorithm
to improve its efficiency.  A solution for the VDW surface of the molecule
may be similarly constructed (I think) by constructing the convex hull
of the VDW surface by generating planes which are tangent to triplets
of the VDW spheres and for which all the remaining spheres lie on one
side of the plane.  The intersections of these planes defining the convex
hull for the VDW surface define a new set of points, faces, and edges 
to which we can apply the above algorithm.  

Two more special cases need to be considered.  For a planar molecule such as 
benzene, we need to construct additional planes to define the VDW convex hull 
by constructing pairs of planes tangent to 2 of the spheres and which are 
perpendicular to the parallel bounding planes above and below the plane 
of the atoms.  For a linear molecule, the problem has the trivial solution
of 2 planes tangent to the 2 spheres at the ends of the molecule
and perpendicular to the line going through the atoms.  The 4 remaining
planes are chosen to be tangent to the largest VDW sphere of the atoms,
perpendicular to the first 2 planes, and perpendicular to each other.

Regards,

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