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: Tue Feb 4 09:44:28 CET 2014