6
$\begingroup$

Given an $n$-cube with unit volume, is there any algorithm that generates a $n$-simplex that covers the $n$-polytope?

$\endgroup$

1 Answer 1

5
$\begingroup$

There is a nontrivial algorithm in $\mathbb{R}^3$ for the minimum volume tetrahedron circumscribing an arbitrary polyhedron (i.e., not specifically a cube):

Zhou, Yunhong, and Subhash Suri. "Algorithms for a minimum volume enclosing simplex in three dimensions." SIAM Journal on Computing 31.5 (2002): 1339-1357. (ACM link.)
                SuriFig6

This work relies on a beautiful theorem of Victor Klee, valid in all dimensions, that implies touching at facet centroids (as one can see in the above figure):

V. Klee, Facet-centroids and volume minimization, Studia Sci.Math.Hungar., 21 (1986), pp.143–147.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.