Triangulating hypercubes - MathOverflow

Triangulating hypercubes

2011-02-10T12:58:43Z

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). This paper also exhibits a lower bound, given below

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

Orden and Santos improved the upper bound somewhat, by reducing the base of the exponential.

Answer by Scott Carter for Triangulating hypercubes

2011-02-10T13:05:06Z

If you think of the $n$-cube as unordered sequences of points from $[0,1]$, and the $n$-symplex as an ordered sequence of points from $[0,1]$, then it is easy to see how to decompose the $n$-cube into $n!$ simplices each of hyper-volume $1/n!$. I am not sure that this is a triangulation --- no opinion at this writing, but if not, then try subdivision.

Answer by Greg Kuperberg for Triangulating hypercubes

2011-02-10T13:23:12Z

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.

Answer by Matthew Kahle for Triangulating hypercubes

2011-02-10T16:12:03Z

In case it is helpful for your computational problem, note that the freely available software CHomP will compute homology of cubical complexes.

http://chomp.rutgers.edu/