Skip to main content
3 of 3
fixed broken link to springerlink.com; added full citations in tooltips; used displaystyle formatting for displayed formula; added apostrophe to shortened year

Triangulating hypercubes

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.