Minkowski sums of polytopes
Minkowski sums of polytopes
复制标题
多面体的闵可夫斯基和
DOI：
--
复制
发表时间：
2007
期刊：
影响因子：
--
通讯作者：
Koichi Ito
中科院分区：
文献类型：
--
作者：
Y. Yamashita;Jyunji Mayumi;Yuhsuke Kawakami;Koichi Ito
Minkowski和是一种非常简单的几何运算，在许多不同的领域都有应用。特别是，Minkowski总和的多面体已被证明是感兴趣的工业界和学术界。本文从组合性质和计算方面对这些和进行了研究。特别是，我们给了一个意想不到的线性关系之间的f-向量的闵可夫斯基和它的被加数，只要这些是相对一般的位置。我们进一步建立了与被加数有关的Minkowski和的最大面数的一些界，这取决于维数和被加数的个数。然后，我们研究了一个特定的Minkowski和族，该族包括对我们称之为与其对偶完全中心的多面体求和。我们表明，该结果的面格可以完全从被加数的面格推导出来。最后，我们提出了一个算法，有效地计算顶点的Minkowski和多面体。我们表明，时间复杂度是线性的输出固定大小的输入，所需的内存大小是独立的输出的大小。我们还回顾了各种算法计算不同的面孔的总和，比较他们的优缺点。
Minkowski sums are a very simple geometrical operation, with applications in many different fields. In particular, Minkowski sums of polytopes have shown to be of interest to both industry and the academic world. This thesis presents a study of these sums, both on combinatorial properties and on computational aspects. In particular, we give an unexpected linear relation between the f-vectors of a Minkowski sum and that of its summands, provided these are relatively in general position. We further establish some bounds on the maximum number of faces of Minkowski sums with relation to the summands, depending on the dimension and the number of summands. We then study a particular family of Minkowski sums, which consists in summing polytopes we call perfectly centered with their own duals. We show that the face lattice of the result can be completely deduced from that of the summands. Finally, we present an algorithm for efficiently computing the vertices of a Minkowski sum of polytopes. We show that the time complexity is linear in terms of the output for fixed size of the input, and that the required memory size is independent of the size of the output. We also review various algorithms computing different faces of the sum, comparing their strong and weak points.