JOURNAL OF COMBINATORIAL THEORY SERIES A | 卷:120 |
Minimal external representations of tropical polyhedra | |
Article | |
Allamigeon, Xavier1,2  Katz, Ricardo D.3  | |
[1] Ecole Polytech, INRIA, F-91128 Palaiseau, France | |
[2] Ecole Polytech, CMAP, F-91128 Palaiseau, France | |
[3] Univ Nacl Rosario, CONICET, Inst Matemat Beppo Levi, RA-2000 Rosario, Santa Fe, Argentina | |
关键词: Tropical convexity; Max-plus convexity; Polyhedra; Polytopes; Supporting half-spaces; External representations; Cell complexes; | |
DOI : 10.1016/j.jcta.2013.01.011 | |
来源: Elsevier | |
【 摘 要 】
Tropical polyhedra are known to be representable externally, as intersections of finitely many tropical half-spaces. However, unlike in the classical case, the extreme rays of their polar cones provide external representations containing in general superfluous half-spaces. In this paper, we prove that any tropical polyhedral cone in R-n (also known as tropical polytope in the literature) admits an essentially unique minimal external representation. The result is obtained by establishing a (partial) anti-exchange property of half-spaces. Moreover, we show that the apices of the half-spaces appearing in such non-redundant external representations are vertices of the cell complex associated with the polyhedral cone. We also establish a necessary condition for a vertex of this cell complex to be the apex of a non-redundant half-space. It is shown that this condition is sufficient for a dense class of polyhedral cones having generic extremities. (c) 2013 Elsevier Inc. All rights reserved.
【 授权许可】
Free
【 预 览 】
Files | Size | Format | View |
---|---|---|---|
10_1016_j_jcta_2013_01_011.pdf | 1064KB | download |