A Lower Bound Technique for Triangulations of Simplotopes
A Lower Bound Technique for Triangulations of Simplotopes
复制标题
Simplotope三角剖分的下界技术
DOI：
10.1137/140972020
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
F. Su
中科院分区：
文献类型：
--
作者：
Tyler Seacrest;F. Su
单纯形的乘积，称为单纯形，以及它们的三角剖分在博弈论和优化的算法应用中自然出现。我们开发的技术，以获得下界的大小单纯覆盖和三角形的simplotopes，包括那些内部顶点。我们建立了两个单形的乘积的最小三角剖分由顶点三角剖分给出，即，一个没有内部顶点的对于两个以上单形的乘积，我们给出了线段和三角形乘积的界。除了立方体，这些是第一个已知的三个或三个以上的因子的单形三角剖分的下界，我们的技术建议扩展到其他种类的单形的产品。我们还构造了一个最小的三角形的大小为10的三角形和正方形的产品使用我们的下限。
Products of simplices, called simplotopes, and their triangulations arise naturally in algorithmic applications in game theory and optimization. We develop techniques to derive lower bounds for the size of simplicial covers and triangulations of simplotopes, including those 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. Aside from cubes, these are the first known lower bounds for triangulations of simplotopes with three or more factors, and our techniques suggest extensions to products of other kinds of simplices. We also construct a minimal triangulation of size 10 for the product of a triangle and a square using our lower bound.
Dyck 路径三角剖分和可扩展性
DOI：
10.1016/j.jcta.2014.10.009
发表时间：
2015
期刊：
J. Comb. Theory, Ser. A
影响因子：
--
作者：
Cesar Ceballos;Arnau Padrol;Camilo Sarmiento
通讯作者：
Camilo Sarmiento