Minimal half-spaces and external representation of tropical polyhedra

Abstract

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.

19 pages, 4 figures, example added with a new figure, figures improved, references updated

References in corpus (6)

• Duality and separation theorems in idempotent semimodules
• The Minkowski Theorem for Max-plus Convex Sets
• The number of extreme points of tropical polyhedra
• The tropical analogue of polar cones
• The tropical double description method
• Cyclic projectors and separation theorems in idempotent convex geometry

Cited by in corpus (22)

• Tropical polyhedra are equivalent to mean payoff games
• Log-barrier interior point methods are not strongly polynomial
• Tropicalizing the simplex algorithm
• Computing the vertices of tropical polyhedra using directed hypergraphs
• The number of extreme points of tropical polyhedra
• Weighted digraphs and tropical cones
• Tropical polar cones, hypergraph transversals, and mean payoff games
• The tropical double description method
• A Tropical Approach to Neural Networks with Piecewise Linear Activations
• Solving generic nonarchimedean semidefinite programs using stochastic game algorithms
• Tropical Fourier-Motzkin elimination, with an application to real-time verification
• Minimal external representations of tropical polyhedra
• Tropical Geometry and Mechanism Design
• Linear programs and convex hulls over fields of Puiseux fractions
• On $2\times 2$ Tropical Commuting Matrices
• Tropical Gaussians: A Brief Survey
• Tropical Geometry and Piecewise-Linear Approximation of Curves and Surfaces on Weighted Lattices
• Face posets of tropical polyhedra and monomial ideals
• Asymmetric tropical distances and power diagrams
• Signed tropical convexity
• Tropical convex hulls of polyhedral sets
• Gérard-Levelt membranes