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 congruentdisjoint tetrahedra, meeting in a common edge along the long diagonal ofthe cube. If you give up congruence, you can reduce this number to five:just cut off every other corner of the cube, leaving a regulartetrahedron in the middle.This raises an interesting open question for higher dimensionalhypercubes: what is the minimum number of simplices into which they canbe cut? The long-diagonal construction generalizes to d! simplices in ddimensions, which can be reduced to O(d!/k^d) for some k by usingCartesian products of the five-tetrahedron solution. There is also alower bound of Omega(sqrt d! k^d) for another constant k coming fromvolume arguments (What is the largest simplex you can fit into ahypercube? This is equivalent to asking what's the largest determinantyou can get with a 0-1 matrix, and is answered by the theory of Hadamardmatrices.) Both bounds can be tightened slightly but there stillremains a big gap between them. I'm not sure if it makes a differencewhether 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'tsubdivide a cube into finitely many regular tetrahedra.-- David Eppstein UC Irvine Dept. of Information & Computer Scienceeppstein@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 anypermutation P=(j_1,...,j_n) of (1,...,n) and let S_J be the set ofpoints 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 adissection of C^n. For example, the cube in 3 space can be cut upinto 5 tetrahedrons. (See http://www.columbia.edu/~law9023/cubes.htmlfor a crude illustration of this.)So my question is: if d_n is the minimal number of simplices in adissection of C^n, what is known about the sequence {d_n}? If this issomething I could have found in the Handbook of Integer Sequences, Iapologize 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 the5-tetrahedron triangulation of the 3-cube or the 16-tetrahedrontriangulation of the 4-cube.There is a lower bound of something like sqrt(n!) based on volumearguments (i.e. the ratio between the volume of the d-cube and the maxvolume of a d-simplex with 0-1 vertex coordinates, closely related toHadamard matrices). I vaguely recollect that you can slightly improvethis (again by c^n for some c>1) by using hyperbolic volume of ideald-cubes and ideal simplices.As far as I know, the big gap between these upper and lower bounds hasnot been narrowed.-- David Eppstein UC Irvine Dept. of Information & Computer Scienceeppstein@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 twosimplices is not a simplex (otherwise d_n would equal 1 for all n), sowhat is the Cartesian product of a triangulation? (And is there agood 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 thevertices of $I\sp n$. The author gives an elegant way of triangulating thecube $I\sp {kn}$ once a triangulation of $I\sp n$ isknown. He shows that if $I\sp n$ can be decomposed into $T(n)$ simplicesthen $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, andin 3-dimensions there is a tetrahedron with 1/3 of the volume of a cube sothe bound is 3. Regular ideal hyperbolic tetrahedra have volume 1/5 of thevolume of the cube, so the hyperbolic estimate is 5, which is sharp sincethe 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 8tetrahedral faces (where you cut off a corner of the cube), and somemore 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 facesturn into regular tetrahedra. So the left over piece has 16regular-tetrahedron faces. It's one of the six regular 4-polytopes, the16-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 regulartetrahedron in the opposite orientation (so that each vertex of theinner tetrahedron is near the middle of a face of the outertetrahedron), think of the inner tetrahedron as being opaque and theouter one as being transparent, and connect every pair of inner andouter vertices that can see each other. Two of the faces of the 16-cellare the tetrahedra you started with. Eight more are formed byconnecting a face of one tetrahedron to a vertex of the other, and theremaining six connect an edge of one tetrahedron to an edge of theother.To finish the 4-cube's triangulation, just connect one of the 16-cell'svertices with each of the opposite faces. Each vertex is opposite 8faces of the 16-cell (because the other 8 faces touch the vertex, as youcan see from the Schlegel diagram). So this step forms 8 moresimplices, 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., ifyou cut off every other corner of a 5-cube, you get a non-regularpolytope, with 16 4-simplex faces and 10 16-cell faces.-- David Eppstein UC Irvine Dept. of Information & Computer Scienceeppstein@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 cellsof the form (simplex in one triangulation) times (simplex in the other).Of course, these cells are not themselves simplices, for instance theproduct of a 1-simplex(=line segment) and 2-simplex(=triangle) is atriangular prism rather than a tetrahedron. So, you have tofurther 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 Scienceeppstein@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 thevertices of $I\sp n$. The author gives an elegant way of triangulating thecube $I\sp {kn}$ once a triangulation of $I\sp n$ isknown. He shows that if $I\sp n$ can be decomposed into $T(n)$ simplicesthen $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, andin 3-dimensions there is a tetrahedron with 1/3 of the volume of a cube sothe bound is 3. Regular ideal hyperbolic tetrahedra have volume 1/5 of thevolume of the cube, so the hyperbolic estimate is 5, which is sharp sincethe 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