Approximation algorithm for mixed volumes of a constant number of convex bodies

Abstract

We study the computation of mixed volumes of convex sets given as rational subspace sections of bodies described by membership oracles. The sets need not have nonempty interior. For positive multiplicities ${\alpha }_1+\cdots +{\alpha }_k=n$, we give a randomized algorithm that computes a relative $\epsilon$-approximation with probability at least $1-\delta$. Its running time is polynomial in Gurvits' factor ${\Gamma }_{\alpha }=(n^n/n!){\prod }_i{\alpha }_i!/{\alpha }_i^{{\alpha }_i}$, the input presentation length, and ${\epsilon }^{-1}$, and linear in $1+\log {\delta }^{-1}$, with degree independent of $k$. The running-time bound holds for every choice of the random bits, and zero mixed volumes are detected exactly. We extend the capacity-scaling and sampling method of Narayanan--Roy by using rational projections and a smooth mixed Monge--Ampère representation. In particular, the algorithm runs in randomized polynomial time when the number of distinct convex sets is bounded above by a constant.

arXiv comment42 pages