Linear and Rational Factorization of Tropical Polynomials

    For tropical polynomials, factorization is already an NP-Complete problem for the bivariate ones. We give an efficient algorithm for factorization and rational factorization of a rich class of tropical polynomials in n variables. Special families of these polynomials have appeared in economics, discrete convex analysis, and combinatorics. Our theorems rely on an intrinsic characterization of regular mixed subdivisions of integral polytopes, and lead to many open problems of interest in discrete geometry. We illustrate our implementation with many examples.