The Middle-Cut Triangulations of the n -Cube
John F. Sallee · SIAM Journal on Algebraic and Discrete Methods · 1984
This paper is concerned with the asymptotic behavior of $\varphi (n)$, the minimum number of simplices required to triangulate the n-cube. Such triangulations are of special interest in connection with algorithms for approximating fixed points of continuous mappings. The standard triangulations of $I^n $ use $n!$ simplices. Let $H(n,m) = \{ x \in R^n :\sum {x_i = m\} } $. Then $H(n,m)$ divides $I^n $ into two polytopes which are then triangulated in a certain fashion. If $K(n,m)$ is the cardinality of this triangulation, then lim $K ( n, n/2 ) /n! = 0$. Hence $\varphi (n)$ is $o(n!)$. Another measure of the efficiency of a triangulation is the diameter of the dual graph and it is shown that this is $O(n^2 )$ for the above triangulation. Finally, a pivoting algorithm for the middle-cut triangulations of the n-cube is also presented.