Minimal triangulations of simplotopes
Tyler Seacrest, Francis Edward Su · arXiv (Cornell University) · 2009
We derive lower bounds for the size of simplicial covers of simplotopes, which are products of simplices. These also serve as lower bounds for triangulations of such polytopes, including triangulations with interior vertices. We establish that a minimal triangulation of a product of two simplices is given by a vertex triangulation, i.e., one without interior vertices. For products of more than two simplices, we produce bounds for products of segments and triangles. Our analysis yields linear programs that arise from considerations of covering exterior faces and exploiting the product structure of these polytopes. Aside from cubes, these are the first known lower bounds for triangulations of simplotopes with three or more factors. We also construct a minimal triangulation for the product of a triangle and a square, and compare it to our lower bound.