Dyer, Martin; Gritzmann, Peter; Hufnagel, Alexander On the complexity of computing mixed volumes. (English) Zbl 0909.68193 SIAM J. Comput. 27, No. 2, 356-400 (1998). Summary: This paper gives various (positive and negative) results on the complexity of the problem of computing and approximating mixed volumes of polytopes and more general convex bodies in arbitrary dimension.On the negative side, we present several \(\#\)P-hardness results that focus on the difference of computing mixed volumes versus computing the volume of polytopes. We show that computing the volume of zonotopes is \(\#\)P-hard (while each corresponding mixed volume can be computed easily) but also give examples showing that computing mixed volumes is hard even when computing the volume is easy.On the positive side, we derive a randomized algorithm for computing the mixed volumes \[ V(\overbrace{K_1,\dots, K_1}^{m_1},\overbrace{K_2,\dots, K_2}^{m_2},\dots,\overbrace{K_s,\dots, K_s}^{m_s}) \] of well-presented convex bodies \(K_1,\dots, K_s\), where \(m_1,\dots, m_s\in\mathbb{N}_0\) and \(m_1\geq n-\psi(n)\) with \(\psi(n)= o\left({\log n\over \log\log n}\right)\). The algorithm is an interpolation method based on polynomial-time randomized algorithms for computing the volume of convex bodies.This paper concludes with applications of our results to various problems in discrete mathematics, combinatorics, computational convexity, algebraic geometry, geometry of numbers, and operations research. Cited in 1 ReviewCited in 29 Documents MSC: 68U05 Computer graphics; computational geometry (digital and algorithmic aspects) 52A39 Mixed volumes and related topics in convex geometry 52B55 Computational aspects related to convexity 68W10 Parallel algorithms in computer science 68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.) 68R05 Combinatorics in computer science 52A20 Convex sets in \(n\) dimensions (including convex hypersurfaces) 90C30 Nonlinear programming 90C25 Convex programming Keywords:computational convexity; volume; mixed volumes; convex body; polytope; zonotope; parallelotope; computation; approximation; computational complexity; deterministic algorithm; randomized algorithm; polynomial-time algorithm; NP-hardness; \(\# P\)-hardness; permanent; determinant problems; lattice point enumerator; partial order; Newton polytope; polynomial equations PDFBibTeX XMLCite \textit{M. Dyer} et al., SIAM J. Comput. 27, No. 2, 356--400 (1998; Zbl 0909.68193) Full Text: DOI