Geodesic
Minimal half-spaces and external representation of tropical polyhedra
Journal of Algebraic Combinatorics, Tome 33 (2011) no. 3, pp. 325-348.

Voir la notice de l'article provenant de la source Electronic Library of Mathematics

Summary: 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.
Keywords: keywords max-plus semiring, max-plus convexity, tropical convexity, polyhedra, polytopes, Minkowski-Weyl theorem, supporting half-spaces 
@article{JAC_2011__33_3_a7,
     author = {Gaubert, St\'ephane and Katz, Ricardo D.},
     title = {Minimal half-spaces and external representation of tropical polyhedra},
     journal = {Journal of Algebraic Combinatorics},
     pages = {325--348},
     publisher = {mathdoc},
     volume = {33},
     number = {3},
     year = {2011},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/JAC_2011__33_3_a7/}
}
TY  - JOUR
AU  - Gaubert, Stéphane
AU  - Katz, Ricardo D.
TI  - Minimal half-spaces and external representation of tropical polyhedra
JO  - Journal of Algebraic Combinatorics
PY  - 2011
SP  - 325
EP  - 348
VL  - 33
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/JAC_2011__33_3_a7/
LA  - en
ID  - JAC_2011__33_3_a7
ER  - 
%0 Journal Article
%A Gaubert, Stéphane
%A Katz, Ricardo D.
%T Minimal half-spaces and external representation of tropical polyhedra
%J Journal of Algebraic Combinatorics
%D 2011
%P 325-348
%V 33
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/item/JAC_2011__33_3_a7/
%G en
%F JAC_2011__33_3_a7
Gaubert, Stéphane; Katz, Ricardo D. Minimal half-spaces and external representation of tropical polyhedra. Journal of Algebraic Combinatorics, Tome 33 (2011) no. 3, pp. 325-348. http://geodesic.mathdoc.fr/item/JAC_2011__33_3_a7/