Abstract
Minkowski's mixed volume is a generalization of the ordinary n-volume to n-tuples of convex bodies. According to Bernstein's Theorem, the number of non-zero isolated complex solutions of a system of n polynomials in n variables is at most n! times the mixed volume of the convex hull of the support of each polynomial.
This invariant plays therefore an important role in polynomial solving, and a related object (a mixed subdivision) can be used as a starting system for homotopy algorithms.
I will present a new algorithm for mixed volume and mixed subdivision computation. The basic idea behind this algorithm is to explore a finite number of toric varieties. Its complexity can be bounded in terms of certain mixed volumes. In case all of the polytopes are n-dimensional, this algorithm is output sensitive.