Return to Colloquia & Seminar listing
Asymptotically size-efficient triangulations of the $d$-cube
Algebra & Discrete Mathematics| Speaker: | David Orden, Universidad de Cantabria |
| Location: | 0 Kerr |
| Start time: | Tue, Oct 16 2001, 10:00AM |
Description
We describe a method to triangulate $I^l\times I^{n-1}$ which is
very useful to obtain triangulations of the
$d$-cube $I^d$ of good asymptotic efficiency. The main idea is to triangulate
$I^l\times I^{n-1}$ from a triangulation of $I^{n-1}$ and another one of
$I^l\times\Delta^{m-1}$, where $\Delta^{m-1}$ is a simplex of
dimension $m-1$, which is supposed to be smaller than $n-1$.This last one will induce a
triangulation of $I^l\times\Delta^{n-1}$, which in addition to the known triangulation of
$I^{n-1}$ gives a triangulation of $I^{l+n-1}$.
Using a convenient triangulation of
$I^3\times\Delta^{2}$ with 38 simplices we obtain that, asymptotically,
the $d$-cube can be triangulated with $0.816^d d!$ simplices, instead of the
$0.840^d d!$ achievable before.