  Already for bivariate tropical polynomials, factorization is an NP-Complete
problem. In this paper, 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.
