2009/04/30 by Xavier Allamigeon, Stéphane Gaubert, Stephane Gaubert +2 · 3 citations
Computer Science · Mathematics · #Characterization (materials science) #Combinatorics #Connected component #Discrete mathematics #Dual polyhedron #Formal Methods in Verification #Graph #Hypergraph #Hyperplane #Intersection (aeronautics) #Logic, programming, and type systems #Mathematics #Polyhedron #Polynomial and algebraic computation #Reachability #Representation (politics) #Vertex (graph theory) #math.CO #msc:05B35 #msc:52B55 #msc:68Q25 #msc:68U05
paper · pdf · doi:10.1007/s00454-012-9469-6
published as Discrete & Computational Geometry, March 2013, Volume 49, Issue 2, pp 247-279 · 29 pages (A4), 10 figures, 1 table; v2: Improved algorithm in section 5 (using directed hypergraphs), detailed appendix; v3: major revision of the article (adding tropical hyperplanes, alternative method by arrangements, etc); v4: minor revision
openalex publication_date 2012/11/20 · arxiv created 2013/02/12 · arxiv updated 2013/02/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
We establish a characterization of the vertices of a tropical polyhedron defined as the intersection of finitely many half-spaces. We show that a point is a vertex if, and only if, a directed hypergraph, constructed from the subdifferentials of the active constraints at this point, admits a unique strongly connected component that is maximal with respect to the reachability relation (all the other strongly connected components have access to it). This property can be checked in almost linear-time. This allows us to develop a tropical analogue of the classical double description method, which computes a minimal internal representation (in terms of vertices) of a polyhedron defined externally (by half-spaces or hyperplanes). We provide theoretical worst case complexity bounds and report extensive experimental tests performed using the library TPLib, showing that this method outperforms the other existing approaches.