**Motivation:** I'm working on a computational problem at the moment, and have some very good routines for natively working with simplicial complexes and calculating homology, but the structures I'm dealing with arise naturally as cubical complexes.


**Problem:** Is there an efficient way to triangulate the n-cube, i.e. calculate a (relatively) small list of n-simplices on the same vertices as the cube, and which define a simplicial complex spanning the cube?


I've done some reference-chasing and there seems to be no decently-sharp estimate (as an upper or lower bound) for the asymptotic complexity of the problem, although the best upper-bounds I'm aware of (for the size of the smallest solution-set) seem to indicate something exponentially smaller than factorial ([see Haiman, '91](https://doi.org/10.1007/BF02574690 "Haiman, M. A simple and relatively efficient triangulation of the n-cube. Discrete Comput Geom 6, 287–289 (1991). zbMATH review at https://zbmath.org/?q=an:0727.68044")). This paper also exhibits a lower bound, given below


$$\frac{2^n\,n!}{(n+1)^{(n+1)/2}}$$


[Orden and Santos](https://arxiv.org/abs/math/0204157 "Orden, D., Santos, F. Asymptotically Efficient Triangulations of the d-Cube. Discrete Comput Geom 30, 509–528 (2003). doi:10.1007/s00454-003-2845-5. zbMATH review at https://zbmath.org/?q=an:1042.52009") improved the upper bound somewhat, by reducing the base of the exponential.



Triangulating hypercubes
For the question as stated, it's a big open problem to triangulate the $n$-cube, and the papers that you cite are basically the state of the art. The lower bound that you give is simply a matter of comparing the volume of an $n$-cube to the volume of the largest possible $n$-simplex inside it, only with the extra idea due to Warren Smith to work in hyperbolic geometry rather than in Euclidean geometry. As you should notice, this lower bound is exponential, while all of the upper bounds are factorial. The upper bound comes from the following simple idea of Haiman: Suppose that you have good triangulations of some low-dimensional cubes. Then you can take their Cartesian product and use the standard step triangulation of a product of simplices. Using for example the triangulation of a 3-cube with 5 simplices instead of the usual 6, this immediately gives you a small exponential gain over the $n!$ answer using the standard step triangulation. Orden and Santos offer a slight improvement of Haiman's idea.


Combinatorialists take this summary of results as an invitation to do better. The upper and lower bounds are very far apart.


If your ultimate goal is to compute homology in high dimensions, then you are much better off NOT triangulating the cubes. It is computationally superior to make chain complexes directly from the cubical complex, and then use the same integer linear algebra that you would have used otherwise.


