On the Hardness of Computing Intersection, Union and Minkowski Sum of Polytopes
On the Hardness of Computing Intersection, Union and Minkowski Sum of Polytopes
复制标题
论多胞形交集、并集和闵可夫斯基和的计算难度
DOI：
--
复制
发表时间：
2008
影响因子：
0.8
通讯作者：
Hans Raj Tiwary
中科院分区：
文献类型：
--
作者：
Hans Raj Tiwary
对于多面体P1，P2 <$$> d，我们考虑交集P1 <$P2，并CH（P1 <$P2）的船体，以及Minkowski和P1+P2。对于Minkowski和，证明了如果P1和P2由小平面指定，或者P1由顶点指定，P2是由小平面指定的多面体锥，则P1+P2的小平面计数是NP-难的.对于交，我们证明了计算两个多面体的交的顶点或刻面是NP-难的，如果其中一个由顶点给定，另一个由刻面给定。此外，计算顶点给定的两个多面体的交集的顶点被证明是NP-困难的。类似的结果计算凸船体的工会两个多面体遵循极对偶。所有的硬度的结果建立显示，适当的决策版本，为这些问题中的每一个，是NP完全的。
For polytopes P1,P2⊂ℝd, we consider the intersection P1∩P2, the convex hull of the union CH(P1∪P2), and the Minkowski sum P1+P2. For the Minkowski sum, we prove that enumerating the facets of P1+P2 is NP-hard if P1 and P2 are specified by facets, or if P1 is specified by vertices and P2 is a polyhedral cone specified by facets. For the intersection, we prove that computing the facets or the vertices of the intersection of two polytopes is NP-hard if one of them is given by vertices and the other by facets. Also, computing the vertices of the intersection of two polytopes given by vertices is shown to be NP-hard. Analogous results for computing the convex hull of the union of two polytopes follow from polar duality. All of the hardness results are established by showing that the appropriate decision version, for each of these problems, is NP-complete.