The aim of this paper is to present a flexible approach for the efficient computation of the mixed volume of a tuple of polytopes. In order to compute the mixed volume, a mixed subdivision of the tuple of polytopes is needed, which can be obtained by embedding the polytopes in a higher dimensional space, i.e., by lifting them. Dynamic lifting is opposed to the static approach. This means that one considers one point at a time and only fixes the value of the lifting function when the point really influences the mixed volume. For this purpose, conservative lifting functions have been developed. This provides us with a deterministic manipulation of the lifting for computing mixed volumes, which rules out randomness conditions. Cost estimates for the algorithm are given. The implications of dynamic lifting on polyhedral homotopy methods for the solution of polynomial systems are investigated and applications are presented.
Keywords. Newton polytopes, mixed volumes, subdivisions, polyhedral homotopy continuation, polynomial systems
AMS subject classification. 14Q99, 52A39, 52B30, 65H10.
Discrete Comput. Geom. 16(1): 69-112, 1996.