From: zare@cco.caltech.edu (Douglas J. Zare) Subject: Re: Triangulation of cubes Date: 31 Dec 1998 20:39:17 GMT Newsgroups: sci.math Keywords: Counting simplices needed to dissect n-cubes John Kasdan wrote: >David Eppstein wrote: >>kasdan@columbia.edu (John Kasdan) writes: >>> The n-dimensional cube, C^n, can be dissected into n! simplices. >>> .... if d_n is the minimal number of simplices in a >>> dissection of C^n, what is known about the sequence {d_n}? The first few terms can be found in (from Math Reviews) -- 97g:90083 90C08 (05C10) Hughes, Robert B.(1-BOISE); Anderson, Michael R. Simplexity of the cube. (English. English summary) Discrete Math. 158 (1996), no. 1-3, 99--150. -- >>You can get n!/c^n for some c>1, e.g. by using Cartesian products of the >>5-tetrahedron triangulation of the 3-cube or the 16-tetrahedron >>triangulation of the 4-cube. >> > >Can you explain that a little more? In general, the product of two >simplices is not a simplex (otherwise d_n would equal 1 for all n), so >what is the Cartesian product of a triangulation? (And is there a >good description of the 16-tetrahedron triangulation of the 4-cube?) From Math Reviews: -- 92e:52011 52A37 Haiman, Mark(1-MIT) A simple and relatively efficient triangulation of the $n$-cube. Discrete Comput. Geom. 6 (1991), no. 4, 287--289. An $n$-cube, $I\sp n$, is "triangulated" if it is the union of $n$-simplices which are disjoint on interiors and whose vertices are the vertices of $I\sp n$. The author gives an elegant way of triangulating the cube $I\sp {kn}$ once a triangulation of $I\sp n$ is known. He shows that if $I\sp n$ can be decomposed into $T(n)$ simplices then $I\sp {kn}$ can be decomposed into $\rho\sp {kn}(kn)!$ simplices, where $\rho=(T(n)/n!)\sp {1/n}<1$. -- >>There is a lower bound of something like sqrt(n!) based on volume >>arguments (i.e. the ratio between the volume of the d-cube and the max >>volume of a d-simplex with 0-1 vertex coordinates, closely related to >>Hadamard matrices). I vaguely recollect that you can slightly improve >>this (again by c^n for some c>1) by using hyperbolic volume of ideal >>d-cubes and ideal simplices. >>[...] The naive Euclidean estimate is worst when a Hadamard matrix exists, and in 3-dimensions there is a tetrahedron with 1/3 of the volume of a cube so the bound is 3. Regular ideal hyperbolic tetrahedra have volume 1/5 of the volume of the cube, so the hyperbolic estimate is 5, which is sharp since the regular ideal cube can be decomposed into 5 regular ideal tetrahedra. "Marshall, T. H. Volume formulae for regular hyperbolic cubes. Conform. Geom. Dyn. 2 (1998), 25--28 (electronic)." is available on the web. Douglas Zare ============================================================================== From: eppstein@euclid.ics.uci.edu (David Eppstein) Subject: Re: Triangulation of cubes Date: 2 Jan 1999 12:06:57 -0800 Newsgroups: sci.math kasdan@columbia.edu (John Kasdan) writes: >(And is there a >good description of the 16-tetrahedron triangulation of the 4-cube?) Doug Zare answered the rest of your questions, but I think not this one. It's pretty similar to the 5-tetrahedron triangulation of the 3-cube. Recall that that works by cutting off every other corner of the cube; the remaining piece in the middle turns out to be a regular tetrahedron. So, let's try doing the same thing in four dimensions. Cut off every other corner of a 4-cube. The 4-cube has 16 corners, so you cut off 8 simplices this way. What's the shape of the piece left over in the middle? It has 8 tetrahedral faces (where you cut off a corner of the cube), and some more faces (subsets of the original faces of the cube you started with). The 4-cube has 8 faces, and after you cut the corners off these faces turn into regular tetrahedra. So the left over piece has 16 regular-tetrahedron faces. It's one of the six regular 4-polytopes, the 16-cell! The 16-cell is easiest to visualize with the help of a Schlegel diagram: form a regular tetrahedron in 3-space, and nest inside it a regular tetrahedron in the opposite orientation (so that each vertex of the inner tetrahedron is near the middle of a face of the outer tetrahedron), think of the inner tetrahedron as being opaque and the outer one as being transparent, and connect every pair of inner and outer vertices that can see each other. Two of the faces of the 16-cell are the tetrahedra you started with. Eight more are formed by connecting a face of one tetrahedron to a vertex of the other, and the remaining six connect an edge of one tetrahedron to an edge of the other. To finish the 4-cube's triangulation, just connect one of the 16-cell's vertices with each of the opposite faces. Each vertex is opposite 8 faces of the 16-cell (because the other 8 faces touch the vertex, as you can see from the Schlegel diagram). So this step forms 8 more simplices, which added to the 8 corners you cut off give a total of 16. It isn't so simple to extend this idea to higher dimensions. E.g., if you cut off every other corner of a 5-cube, you get a non-regular polytope, with 16 4-simplex faces and 10 16-cell faces. -- David Eppstein UC Irvine Dept. of Information & Computer Science eppstein@ics.uci.edu http://www.ics.uci.edu/~eppstein/