Minimal half-spaces and external representation of tropical polyhedra
Minimal half-spaces and external representation of tropical polyhedra
复制标题
热带多面体的最小半空间和外部表示
DOI：
10.1007/s10801-010-0246-4
复制
发表时间：
2009
影响因子：
0.8
通讯作者：
Ricardo D. Katz
中科院分区：
文献类型：
--
作者：
S. Gaubert;Ricardo D. Katz
给出了含有给定热带多面体的极小热带半空间的一个刻画，由此得到了一个反例，证明了这种极小半空间的个数可以是无穷的，反驳了热带文献中的一些说法，并反驳了F。我们还建立了Minkowski-Weyl定理的一个类比，表明热带多面体可以在内部(用极值点和射线)或外部(用包含它的半空间)等价地表示。多面体的标准外部表示原来是由其热带极地的极端元素提供的。我们刻画了这些极端元素的特征，特别表明它们是由支持向量决定的。
We give a characterization of the minimal tropical half-spaces containing a given tropical polyhedron, from which we derive a counter-example showing that the number of such minimal half-spaces can be infinite, contradicting some statements which appeared in the tropical literature, and disproving a conjecture of F. Block and J. Yu. We also establish an analogue of the Minkowski–Weyl theorem, showing that a tropical polyhedron can be equivalently represented internally (in terms of extreme points and rays) or externally (in terms of half-spaces containing it). A canonical external representation of a polyhedron turns out to be provided by the extreme elements of its tropical polar. We characterize these extreme elements, showing in particular that they are determined by support vectors.