From: kfoster@rainbow.rmii.com (Kurt Foster)
Newsgroups: sci.math
Subject: Re: Cube -> pyramids?
Date: 17 May 1996 14:10:21 GMT
Organization: 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.math
Subject: Re: Cube -> pyramids?
Date: 17 May 1996 10:17:30 -0700
Organization: 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 -0500
Newsgroups: sci.math
Subject: 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 -0800
Newsgroups: sci.math
Subject: 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 -0500
Newsgroups: sci.math
Subject: 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 GMT
Newsgroups: sci.math
Subject: 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 -0800
Newsgroups: sci.math
Subject: 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 cubes
Date: 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 GMT
Newsgroups: sci.math
Subject: 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