Minimal enclosing parallelepiped in 3D



We investigated the problem of finding a minimal volume parallelepiped enclosing a given set of n three-dimensional points. Using two mathematical properties of these parallelepipeds, we derived algorithms of theoretical complexity O(n^6). Experiments showed that in practice our quickest algorithm runs in O(n^2) (at least for n <= 100000). (See our paper for the algorithm description.)

The parallelepiped library is the implementation of our quickest algorithm, which is available under the GNU General Public License.

Download the parallelepiped library.


Frédéric Vivien
Last modified: Wed Oct 1 09:24:40 CEST 2003