From:kfoster@rainbow.rmii.com (Kurt Foster)Newsgroups:sci.mathSubject:Re: Cube -> pyramids?Date:17 May 1996 14:10:21 GMTOrganization:Rocky Mountain Internet Inc.

Rouben Rostamian (rouben@math.umbc.edu) wrote: : Q: Is it possible to subdivide a cube into congruent : and disjoint tetrahedra? : Let's see. You can easily divide the cube into 6 congruent and disjoint pyramids, each having one face of the cube as a base, and the center of the cube as a vertex. They're not tetrahedra, though, since they have 5 faces (the base, plus 4 slanting sides) instead of 4. No problem, just bisect each of these pyramids along a plane which contains its vertex and a diagonal of its base. That subdivides the cube into 12 congruent and disjoint tetrahedra. They're not REGULAR tetrahedra, but the question didn't say they had to be. If you specify regular tetrahedra, I'm not sure whether the task is possible, but I doubt it. I think it's been proved that if you subdivide a cube into finitely many pieces using plane cuts, then you can't reassemble the pieces into a regular tetrahedron.

From:eppstein@ics.uci.edu (David Eppstein)Newsgroups:sci.mathSubject:Re: Cube -> pyramids?Date:17 May 1996 10:17:30 -0700Organization:UC Irvine Department of ICS

Rouben Rostamian (rouben@math.umbc.edu) wrote: : Is it possible to subdivide a cube into congruent : and disjoint tetrahedra? kfoster@rainbow.rmii.com (Kurt Foster) replies: : You can easily divide the cube into 6 congruent and disjoint pyramids, : each having one face of the cube as a base, and the center of the cube : as a vertex ... just bisect each of these pyramids along a plane which : contains its vertex and a diagonal of its base. That subdivides the : cube into 12 congruent and disjoint tetrahedra. They're not REGULAR : tetrahedra, but the question didn't say they had to be. Actually, it's possible to subdivide a cube into only six congruent disjoint tetrahedra, meeting in a common edge along the long diagonal of the cube. If you give up congruence, you can reduce this number to five: just cut off every other corner of the cube, leaving a regular tetrahedron in the middle. This raises an interesting open question for higher dimensional hypercubes: what is the minimum number of simplices into which they can be cut? The long-diagonal construction generalizes to d! simplices in d dimensions, which can be reduced to O(d!/k^d) for some k by using Cartesian products of the five-tetrahedron solution. There is also a lower bound of Omega(sqrt d! k^d) for another constant k coming from volume arguments (What is the largest simplex you can fit into a hypercube? This is equivalent to asking what's the largest determinant you can get with a 0-1 matrix, and is answered by the theory of Hadamard matrices.) Both bounds can be tightened slightly but there still remains a big gap between them. I'm not sure if it makes a difference whether you allow additional vertices (as in your 12-tetrahedron solution) or just stick with the original set of 2^d vertices. : If you specify regular tetrahedra, I'm not sure whether the task is : possible, but I doubt it. I think it's been proved that if you subdivide : a cube into finitely many pieces using plane cuts, then you can't : reassemble the pieces into a regular tetrahedron. This was Hilbert's Third Problem, and is as you say impossible. See http://www.cco.caltech.edu/~zare/dehninvstuff.html for a proof (involving so-called Dehn invariants). The same theory shows that you can't subdivide a cube into finitely many regular tetrahedra. -- David Eppstein UC Irvine Dept. of Information & Computer Science eppstein@ics.uci.edu http://www.ics.uci.edu/~eppstein/

From:kasdan@columbia.edu (John Kasdan)Date:27 Dec 1998 15:46:21 -0500Newsgroups:sci.mathSubject:Triangulation of cubes

The n-dimensional cube, C^n, can be dissected into n! simplices. (Proof: let the coordinates of R^n be x_1,...,x_n. Take any permutation P=(j_1,...,j_n) of (1,...,n) and let S_J be the set of points in R^n with 0 <= x_{j_1} <= x_{j_2} <= ... <= x_{j_n} <=1. The n! S_J's provide the dissection.) However n! is not necessarily the minimum number of simplices in a dissection of C^n. For example, the cube in 3 space can be cut up into 5 tetrahedrons. (See http://www.columbia.edu/~law9023/cubes.html for a crude illustration of this.) So my question is: if d_n is the minimal number of simplices in a dissection of C^n, what is known about the sequence {d_n}? If this is something I could have found in the Handbook of Integer Sequences, I apologize but I don't have immediate access to that book. /KAS

From:eppstein@euclid.ics.uci.edu (David Eppstein)Date:28 Dec 1998 15:26:20 -0800Newsgroups:sci.mathSubject:Re: Triangulation of cubes

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}? 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. 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. As far as I know, the big gap between these upper and lower bounds has not been narrowed. -- David Eppstein UC Irvine Dept. of Information & Computer Science eppstein@ics.uci.edu http://www.ics.uci.edu/~eppstein/

From:kasdan@columbia.edu (John Kasdan)Date:31 Dec 1998 13:30:01 -0500Newsgroups:sci.mathSubject:Re: Triangulation of cubes

In article <76942s$388@euclid.ics.uci.edu>, David Eppstein <eppstein@euclid.ics.uci.edu> 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}? > >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?) >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. > >As far as I know, the big gap between these upper and lower bounds has >not been narrowed. >-- >David Eppstein UC Irvine Dept. of Information & Computer Science >eppstein@ics.uci.edu http://www.ics.uci.edu/~eppstein/

From:zare@cco.caltech.edu (Douglas J. Zare)Date:31 Dec 1998 20:39:17 GMTNewsgroups:sci.mathSubject:Re: Triangulation of cubes

John Kasdan <kasdan@columbia.edu> wrote: >David Eppstein <eppstein@euclid.ics.uci.edu> 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)Date:2 Jan 1999 12:06:57 -0800Newsgroups:sci.mathSubject:Re: Triangulation of cubes

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/

From:David Eppstein <eppstein@ics.uci.edu>To:John Kasdan <kasdan@columbia.edu>Subject:Re: Triangulation of cubesDate:Wed, 6 Jan 1999 09:40:25 -0800 (PST)

John Kasdan writes: > He may well have, but my newfeed hasn't gotten it yet. Are you sure > he posted it and didn't just mail it to you? In any case, I would > still like a description, or at least a reference, to "the cartesian > product of a triangulation" if it wouldn't be too much trouble. A short answer: the product of a triangulation is simply the set of cells of the form (simplex in one triangulation) times (simplex in the other). Of course, these cells are not themselves simplices, for instance the product of a 1-simplex(=line segment) and 2-simplex(=triangle) is a triangular prism rather than a tetrahedron. So, you have to further subdivide the cells to get a triangulation again. I'm including a copy of Zare's message again for you below. One other reference on this sort of subject (products of triangulations, that is, not so much cube triangulation) is my own paper, "Dihedral bounds for mesh generation in high dimensions", http://www.ics.uci.edu/~eppstein/pubs/BerCheEpp-SODA-95.pdf -- David Eppstein UC Irvine Dept. of Information & Computer Science eppstein@ics.uci.edu http://www.ics.uci.edu/~eppstein/

From:zare@cco.caltech.edu (Douglas J. Zare)Date:31 Dec 1998 20:39:17 GMTNewsgroups:sci.mathSubject:Re: Triangulation of cubes

John Kasdan <kasdan@columbia.edu> wrote: >David Eppstein <eppstein@euclid.ics.uci.edu> 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