UC Davis Mathematics

Mathematics Colloquia and Seminars

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.