7
$\begingroup$

How to find the smallest triangulation of the n-dimensional cube into n- simplices?

It is known, for example, that the 4D cube (the hypercube) may be partitioned into 16 4-simplices, and this is minimal. But the minimum number is unknown except for the few small values of n that have yielded to exhaustive computer searches.

(These tags not available for me : hypercube , computer search)

$\endgroup$
1
  • $\begingroup$ @AlexRavsky Thanks for editing tags. $\endgroup$
    – Zia
    Aug 24 '13 at 16:38
8
$\begingroup$

This is a hard research question. As achille hui says, one of the best lower bounds for the number of n-simplices known is (roughly) $2^n n! /n^{n/2}$, obtained by Hadamard's inequality, which gives you an upper bound on the volume that a simplex contained in the cube can have. (achille seems to be forgetting a factor of $2^n$, which arises from the fact that Hadamard's inequality is about the $[-1,1]^n$ cube, rather than the $[0,1]$ cube).

This "Hadamard bound" was improved by Warren D. Smith by using Hiperbolic volume and very recently by Alexey Glazyrin. They change the $2^n$ factor to, respectively, $6^{n/2}$ and $e^n$ (http://www.sciencedirect.com/science/article/pii/S019566989990327X, http://arxiv.org/abs/0910.4200).

In terms of actual constructions of triangulations with "few" simplices, the smallest size of a triangulation is known only up to dimension 7. It was computed by Anderson and Hughes (http://www.sciencedirect.com/science/article/pii/0012365X95000758) and it has $1493$ simplices.

For high-dimensional cubes, there is a "simple but relatively efficient" trick by Haiman (http://link.springer.com/article/10.1007%2FBF02574690) that basically says: If you can triangulate an $n$-cube with $\alpha^n n!$ simplices for a certain dimension, then by taking Cartesian products you can triangulate every $N$-cube ($N$ is now consider very big) also with $\alpha^N N!$ simplices. The best value for $\alpha$ known so far is obtained for the minimum triangulation of the $7$-cube, $1493 = 0.840^7 7!$. That is, Haiman's trick gives you triangulations with $0.840^N N!$ simplices.

With a more elaborate argument I, with D. Orden, constructed triangulations of the $N$-cube with (asymptotically), $0.816^N N!$ simplices (http://link.springer.com/article/10.1007%2Fs00454-003-2845-5, http://arxiv.org/abs/math.CO/0204157).

For cubes of small dimension, apart of the Anderson-Hughes paper mentioned above I would cite this paper of Bliss and Su, dealing with lower bounds: http://link.springer.com/article/10.1007%2Fs00454-004-1128-0, http://arxiv.org/abs/math/0310142

Summing up, I would say that so far "sophisticated ideas" provide only slight improvements to "simple ideas" (by "simple" I mean Hadamard for lower bounds and Haiman for explicit constructions / upper bounds).

$\endgroup$
2
$\begingroup$

Let $S(n)$ be the minimal number of simplices in the triangulation of an $n$-dimensional cube. It seems the following.

Since an $n$-dimensional cube has $2^n$ vertices and an $n$-simplex has $n+1$ vertices, we see that $S(n)\ge 2^n/(n+1).$

A triangulation of an $n$-dimensional cube induces a triangulation of each of $(n-1)$-dimensional face of the $n$-cube. Since each such a face has at least $S(n-1)$ $(n-1)$-simplices, and each $n$-simplex has $n+1$ $(n-1)$-dimensional faces, we have that $S(n)\ge S(n-1)\cdot 2n/(n+1).$

Moreover, if we count (1-dimensional) edges instead of $(n-1)$-dimensional faces, we obtain the bound like $S(n)\ge (2n(n-1)S(n-1)-2^n)/(n+1)$ (each $k$-simplex has $k(k+1)/2$ edges, each $(n-1)$-dimensional face yields $S(n-1)$ edges and the edges of the $n$-cube are counted twice. This bound can be improved, because every edge of the triangulation of the $n$-cube which is not an edge of the $n$-cube, belongs to at least two simplices of the triangulation. Then we have a bound $S(n)\ge (4n(n-1)S(n-1)-3\cdot 2^n)/(n+1).$

Moreover, the bound $S(n)\ge S(n-1)\cdot 2n/(n+1)$ can be improved too, because an $n$-dimensional cube has $n$-pairs of parallel $(n-1)$-dimensional faces and each simplex of the triangulation cannot have parallel $(n-1)$-dimensional faces. So it has an $(n-1)$-dimensional face which not lies on an $(n-1)$-dimensional face of the cube. Therefore we have a bound $S(n)\ge 2S(n-1)$.

$\endgroup$
1
  • 2
    $\begingroup$ An alternate lower bound for $S(n)$ can be obtained using Hadamard's upper bound for volume of $n$-simplex inside a unit cube $\frac{\sqrt{n}^n}{n!}$. This implies $S(n) \ge \frac{n!}{\sqrt{n}^n}$ which overtake the first estimate $\frac{2^n}{n+1}$ here at $n \ge 16$. $\endgroup$ Aug 24 '13 at 13:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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