# An Efficient Computation of Mixed Volume

### Ioannis Emiris

###
EECS Department

University of California, Berkeley

Technical Report No. UCB/CSD-93-734

April 1993

### http://www.eecs.berkeley.edu/Pubs/TechRpts/1993/CSD-93-734.pdf

The Mixed Volume of
*n* polytopes in
*n*-dimensional space is a multilinear function with respect to Minkowski addition and scalar multiplication that generalizes the notion of volume. The current interest in efficient methods for computing it is mainly due to Bernstein's theorem which bounds the number of common roots of a system of polynomial equations by the Mixed Volume of the respective Newton polytopes. In this paper we propose an algorithm that uses polyhedral techniques to significantly improve upon the efficiency of the method based on evaluating the inclusion-exclusion formula and obtain a practical algorithm.

BibTeX citation:

@techreport{Emiris:CSD-93-734, Author = {Emiris, Ioannis}, Title = {An Efficient Computation of Mixed Volume}, Institution = {EECS Department, University of California, Berkeley}, Year = {1993}, Month = {Apr}, URL = {http://www.eecs.berkeley.edu/Pubs/TechRpts/1993/6027.html}, Number = {UCB/CSD-93-734}, Abstract = {The Mixed Volume of <i>n</i> polytopes in <i>n</i>-dimensional space is a multilinear function with respect to Minkowski addition and scalar multiplication that generalizes the notion of volume. The current interest in efficient methods for computing it is mainly due to Bernstein's theorem which bounds the number of common roots of a system of polynomial equations by the Mixed Volume of the respective Newton polytopes. In this paper we propose an algorithm that uses polyhedral techniques to significantly improve upon the efficiency of the method based on evaluating the inclusion-exclusion formula and obtain a practical algorithm.} }

EndNote citation:

%0 Report %A Emiris, Ioannis %T An Efficient Computation of Mixed Volume %I EECS Department, University of California, Berkeley %D 1993 %@ UCB/CSD-93-734 %U http://www.eecs.berkeley.edu/Pubs/TechRpts/1993/6027.html %F Emiris:CSD-93-734