Subject: Summary: Smallest rectangular Box

From: <[email-masked]>
Date: Wed, 12 Jun 1996 11:28:55 +0200 (MET DST)

> Dear CCL'ers,
 > I've got the problem to find the smallest possible rectangular Box
 > around a set of points (atoms) in space. Any suggestions or ideas
 > are wellcome. I'll summerize the results.
 > 
 > Heiko Gerwens

##########################################################################
##########################################################################

I'd try this, and be prepared to be wrong.  First off, simply do the
usual inertial frame transformation on the points, ie:

	1) Translate the points so their center of gravity coincides
	with the origin.

	2) Rotate the points around the origin to align the inertial
	frame of the points.

Now, minimize the volume of the axis aligned parallelpiped containing
the points while rotating the points about the origin.  Ie, minimize

	V = (max(x_i)-min(x_i))*(max(y_i)-min(y_i))*(max(z_i)-min(z_i))

It's possible that the inertial alignment will be the minimum.

Finally, project the parallelpiped back into the original coordinate
system. 

-- rec -- Return-Path: <[email-masked]>

##########################################################################
##########################################################################

One approach is to do eigen analysis on the X'X matrix - the three eigen-
vectors are the major axes of 'an' enclosing box - for a flat or a long
molecule, this would be close to the smallest - for other shapes, it is
necessary to either systematically rotate the box from the starting position,
or use some optimization scheme (maybe GA?) to find the smallest enclosing
box.  There may be some way to take advantage of the molecule as a tree -
I'm not sure...

Return-Path: <[email-masked]>

##########################################################################
##########################################################################

	Assign unit mass to the points, and find the xyz-s that diagonlize the
"momnet-of-inertia" tensor.  the extrema should define the box you are looking
for.  If you need to preserve the original coordinates, save the transformation
and apply its inverse.

++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
                           FREDERIC A. VAN-CATLEDGE

Scientific Computing Division         ||   Office: (302) 695-1187 or 529-2076
Central Research & Development Dept.  ||          
The DuPont Company                    ||      FAX: (302) 695-9658
P. O. Box 80320                       ||
Wilmington DE 19880-0320              || Internet: [email-masked] 
--------------------------------------------------------------------------------
Opinions expressed in this electronic message should ***> NOT <*** be taken to 
represent the official position(s) of the DuPont Company.  

*****> ANY OPINIONS EXPRESSED ARE THE PERSONAL VIEWS OF THE AUTHOR ONLY. <*****
++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++

##########################################################################
##########################################################################

1) Transfrom your molecule into the principal axis coordinate system (i.e.,
the system in which the moment of inertia is diagonal)
2) Maximal and minimal values of atomic X, Y and Z should in principle
define the smallest rectangular box

Hope that helps,

Robert Fraczkiewicz
University of Texas Medical Branch
Return-Path: <[email-masked]>