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/