Subject: Smallest rectangular box

From: [email-masked] (Cory C. Pye)
Date: Thu, 13 Jun 96 17:46:54 -0230

To solve the bounding box problem:
Step 1: Metric:
Decide on a metric to define smallest. One that works well is the volume of  
the box. V(d1,d2,d3)=d1*d2*d3. Another would be that the largest dimension of 
the box be as small as possible which would imply that (without loss of 
generality) V(d1,d2,d3)=d1 subject to d1>d2>d3 . We use the former.
(It is implicit that d1,d2,d3 >= 0)

Step 2: Define your constraints: 
Linear Algebra: Let n_i be the unit normal vectors of the 3 families 
of planes defining the possible boxes. A plane containing a boundary would 
be generally expressed as <n1 , (P-P0)> = 0, (where <,>=dot product,
P0 is any chosen point in the plane and P is any other point in the 
plane). The line given by P(k1)=k1*n1 (passing through the origin) must intersect
the plane, and we choose this point to be P0, since 
<n1, k1*n1>=k1*<n1,n1>=k1*1=k1 (i.e. the plane is k1 units away from the origin).
This choice of P0 allows us to define the two parallel planes as 
<n1,P>=k1
<n1,P>=k1+d1 
where d1 is one of the dimension of the box. 
Similarly,
<n2,P>=k2
<n2,P>=k2+d2
and 
<n3,P>=k3
<n3,P>=k3+d3
With the proviso that <n1,n2>=<n1,n3>=<n2,n3>=0, 
which ensures that the planes are mutually perpendicular, the constraints are
If we have N points x1,...,xn, for each xi,
k1 < <n1,xi>  < k1+d1
k2 < <n2,xi>  < k2+d2
k3 < <n3,xi>  < k3+d3
giving 6*N inequality constraints and 3 equality constraints.
We note that the matrix formed by N=[n1,n2,n3] is orthogonal, i.e. N^{-1}=N^{t}.

Thus the problem can be restated as,
for a collection of N points x_i, find an orthogonal matrix N and 2 vectors
k = [k1:k2:k3]^{T} and d = [d1:d2:d3]^{T} such that d1*d2*d3 is minimized subject
to the conditions:

 0 < N*x_i - k < d (componentwise)

N corresponds geometrically to a rotation and k to a translation matrix of the 
points.

The problem is solved for less than 4 points, since for three points, 
the dimension normal to the plane defined by these points is zero, for two 
points, any direction perpendicular to the line, and for one point, any 
dimension.

Discussion of other postings:
This makes the point by [email-masked] irrelevant since the `opposite 
corners' are equivalent to the opposite sides (case N=2).

>Surely this is not correct. Consider the trivial case of two points. The
>smallest bounding rectangle will have the two points at opposite corners.

The point by [email-masked] is valid. The convex hull of the
set would have to be enclosed by this box, and could reduce the dimensionality
of the problem considerably, since only the points on the hull would need to be
considered in the constraints. The faces are probably not related however, since 
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.

>to get an idea of  a correct answer.   I  think  the  faces of the
>rectangular  box  are  related to the faces of the boundary of the
>convex hull of the point set.

Many of the points relating to principal axes would not apply because V is not
quadratic.

A nonlinear optimization method with constraints may be needed to solve this 
problem, which might not have an analytic solution determinable a priori.
Using the second metric would probably have an analytic solution relating to
the principal axes, since the problem is then quadratic.
   *************
 *****************  !  Cory C. Pye
***   **    **  **  !  Graduate Student and Unpaid Sys Admin
**   *  ****        !  Theoretical and Computational Chemistry
**      *  *        !  [email-masked]
**      *  *        !  http://www.ucs.mun.ca/~cory/index.html
***     *  *    **  !
 *****************  !  Les Hartree-Focks
   *************    !  (Apologies to Montreal Canadien Fans)