On the complexity of computing mixed volumes. (English) Zbl 0909.68193

Dyer, Martin; Gritzmann, Peter; Hufnagel, Alexander

SIAM J. Comput. 27, No. 2, 356-400 (1998).

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