Minimal enclosing parallelepiped in 3D

1 REMAP - Regularity and massive parallel computing
Inria Grenoble - Rhône-Alpes, LIP - Laboratoire de l'Informatique du Parallélisme
Abstract : We investigate the problem of finding a minimal volume parallelepiped enclosing a given set of n three-dimensional points. We give two mathematical properties of these parallelepipeds, from which we derive two algorithms of theoretical complexity O(n^6). Experiments show that in practice our quickest algorithm runs in O(n^2) (at least for $n \leq 10^5$n 10^5). We also present our application in structural biology.
Keywords :
Document type :
Reports
Domain :
Complete list of metadata

https://hal.inria.fr/inria-00071901
Contributor : Rapport De Recherche Inria Connect in order to contact the contributor
Submitted on : Tuesday, May 23, 2006 - 7:12:29 PM
Last modification on : Wednesday, March 2, 2022 - 1:28:06 PM

Identifiers

• HAL Id : inria-00071901, version 1

Citation

Frédéric Vivien, Nicolas Wicker. Minimal enclosing parallelepiped in 3D. [Research Report] RR-4685, LIP RR-2002-49, INRIA, LIP. 2002. ⟨inria-00071901⟩

Record views