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 |

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.