A simple and relatively efficient triangulation of the n-cube. (English) Zbl 0727.68044

By means of simple construction it is shown that there exists a triangulation of the n-cube with \(O(\rho^\wedge nn!)\) simplices, \(\rho <1\). This improves previous estimates.

MathOverflow Questions:

Triangulating hypercubes


68Q25 Analysis of algorithms and problem complexity
05B45 Combinatorial aspects of tessellation and tiling problems
52C22 Tilings in \(n\) dimensions (aspects of discrete geometry)
Full Text: DOI EuDML


[1] Billera, L. J.; Cushman, R.; Sanders, J. A., The Stanley decomposition of the harmonic oscillator, Nederl. Akad. Wetensch. Proc. Ser. A, 91, 375-393, (1988) · Zbl 0669.15006
[2] Cottle, R. W., Minimal triangulations of the 4-cube, Discrete Math., 40, 25-29, (1982) · Zbl 0483.52005
[3] Lee, C.; Goodman, J. E. (ed.); Lutwak, E. (ed.); Malkevitch, J. (ed.); Pollack, R. (ed.), Triangulating the \(d\)-cube, 205-211, (1985), New York
[4] C. Lee, Some notes on triangulating polytopes, inProc. 3. Kolloquium über Diskrete Geometrie, Institut für Mathematik, Universität Salzburg (1985), pp. 173-181.
[5] P. S. Mara, Triangulations of the Cube, M, S. Thesis, Colorado State University (1972).
[6] Sallee, J. F., A triangulation of the \(n\)-cube, Discrete Math., 40, 81-86, (1982) · Zbl 0483.52003
[7] Sallee, J. F., Middle-cut triangulations of the \(n\)-cube, SIAM J. Algebraic Discrete Methods, 5, 407-419, (1984) · Zbl 0543.52004
[8] W. D. Smith, Polytope triangulations in \(d\)-space, improving Hadamard’s inequality and maximal volumes of regular polytopes in hyperbolic \(d\)-space. Manuscript, Princeton, NJ (September 1987).
[9] Stanley, R. P., Decompositions of rational convex polytopes, Ann. Discrete Math., 6, 333-342, (1980) · Zbl 0812.52012
[10] R. P. Stanley,Enumerative Combinatorics, Vol. I, Wadsworth & Brooks/Cole, Monterey, CA (1986). · Zbl 0608.05001
[11] M. J. Todd,The Computation of Fixed Points and Applications, Lecture Notes in Economics and Mathematical Systems, Vol. 124, Springer-Verlag, Berlin (1976). · Zbl 0332.54003
[12] B. Von Hohenbalken, How To Simplicially Partition a Polytope, Research Paper No. 79-17, Department of Economics, University of Alberta, Edmonton (1979).
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.