6 1. TROPICS (0, 0) x1 0 2 (1, −1) 1 + x2 2x1 + 2x2 Figure 5. 0 ⊕ (0 x1) ⊕ (1 x2) ⊕ (0 x1 x1 x2 x2) (0, 1) ˜ S (3, 2) (1, 0) (2, 0) 0 1 2 3 ΔS Figure 6 the convex hull of S in NR. The coeﬃcients an then define a function ϕ : ΔS → R as follows. We consider the upper convex hull ˜ S of the set ˜ = {(n, an) | n ∈ S} ⊆ NR × R, namely ˜ S = {(n, a) ∈ NR × R | there exists (n, a ) ∈ Conv( ˜) with a ≥ a }. We then define ϕ(n) = min{a ∈ R | (n, a) ∈ ˜ S }. For example, considering the univariate tropical polynomial f = 1 ⊕ (0 x) ⊕ (0 x2) ⊕ (2 x3), we get ΔS and ˜ S as depicted in Figure 6, with the lower boundary of ˜ S being the graph of ϕ. This picture yields a polyhedral decomposition of ΔS: Definition 1.3. A (lattice) polyhedral decomposition of a (lattice) polyhedron Δ ⊆ NR is a set P of (lattice) polyhedra in NR called cells such that

Purchased from American Mathematical Society for the exclusive use of nofirst nolast (email unknown) Copyright 2011 American Mathematical Society. Duplication prohibited. Please report unauthorized use to cust-serv@ams.org. Thank You! Your purchase supports the AMS' mission, programs, and services for the mathematical community.