Embedding Stacked Polytopes on a Polynomial-Size Grid
Embedding Stacked Polytopes on a Polynomial-Size Grid
复制标题
在多项式大小的网格上嵌入堆叠多面体
DOI：
10.1007/s00454-017-9887-6
复制
发表时间：
--
影响因子：
0.8
通讯作者：
A. Schulz
中科院分区：
文献类型：
--
作者：
E. D. Demaine;A. Schulz
堆叠操作将广告单纯形添加到单纯形多面体的面的顶部，同时保持多面体的凸性。 stackedd-polytope 是通过 ad-simplex 和一系列堆叠操作获得的多胞形。我们证明，对于一个固定的堆叠多面体，可以用非负整数坐标来实现。坐标以 为边界，但一个轴除外，坐标以 为边界。所描述的实现可以用简单的算法来计算。多面体的实现是通过在大网格上产生嵌入的提升技术来实现的。我们建立了一种舍入方案，将顶点放置在更稀疏的网格上，同时保持嵌入的凸性。
A stacking operation adds ad-simplex on top of a facet of a simpliciald-polytope while maintaining the convexity of the polytope. A stackedd-polytope is a polytope that is obtained from ad-simplex and a series of stacking operations. We show that for a fixeddevery stackedd-polytope withnvertices can be realized with nonnegative integer coordinates. The coordinates are bounded by, except for one axis, where the coordinates are bounded by. The described realization can be computed with an easy algorithm. The realization of the polytopes is obtained with a lifting technique which produces an embedding on a large grid. We establish a rounding scheme that places the vertices on a sparser grid, while maintaining the convexity of the embedding.
登录
查看更多内容
DOI：
--
发表时间：
2006
期刊：
影响因子：
--
作者：
Ares Ribó Mor
通讯作者：
Ares Ribó Mor
影响因子：
0.8
作者：
Ankur Moitra;F. Leighton
通讯作者：
Ankur Moitra;F. Leighton
多面体的实现空间
影响因子：
0.8
作者：
Jürgen Richter
通讯作者：
Jürgen Richter
DOI：
10.1007/978-3-642-15775-2_10
发表时间：
2009-12
期刊：
--
影响因子：
--
作者：
K. Buchin;A. Schulz
通讯作者：
K. Buchin;A. Schulz
影响因子：
1.1
作者：
J. Hopcroft;P. J. Kahn
通讯作者：
P. J. Kahn