Exposition of an approximation algorithm for mixed volumes of a constant number of convex bodies

Abstract

We study $\epsilon$-relative approximation of mixed volumes of a fixed number $k$ of full-dimensional convex bodies in ${\mathbb{R}}^n$, given membership oracles and a known bound $B_n\subseteq K_i\subseteq R_0{B}_n$. We present a randomized algorithm that estimates any prescribed mixed volume within relative error $\epsilon$ with probability at least $1-\delta$, using polynomially many oracle calls and bit operations in $n$, $\log R_0$, ${\epsilon }^{-1}$, and $\log {\delta }^{-1}$ for fixed $k$.

27 pages