On The Complexity of Computing Mixed Volumes

DOI10.1137/S0097539794278384zbMath0909.68193OpenAlexW2005392884MaRDI QIDQ4388877

Martin Dyer, Alexander Hufnagel, Peter Gritzmann

Publication date: 10 May 1998

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/s0097539794278384

zbMATH Keywords

volumecomputational complexityNewton polytopeapproximationzonotopepolytoperandomized algorithmconvex bodypolynomial-time algorithmpolynomial equationspartial orderpermanentNP-hardnesscomputationdeterministic algorithmmixed volumesparallelotopecomputational convexitylattice point enumerator\(\# P\)-hardnessdeterminant problems

Mathematics Subject Classification ID

Convex programming (90C25) Computational aspects related to convexity (52B55) Nonlinear programming (90C30) Combinatorics in computer science (68R05) Computer graphics; computational geometry (digital and algorithmic aspects) (68U05) Parallel algorithms in computer science (68W10) Mixed volumes and related topics in convex geometry (52A39) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Convex sets in (n) dimensions (including convex hypersurfaces) (52A20)

Related Items

Extensions of the Kahn-Saks inequality for posets of width two, The Blaschke-Steinhardt point of a planar convex set, A practical volume algorithm, Largest \(j\)-simplices in \(n\)-polytopes, Stochastic Billiards for Sampling from the Boundary of a Convex Set, Combinatorial mixed valuations, Mixed-volume computation by dynamic lifting applied to polynomial system solving, Computing mixed volume and all mixed cells in quermassintegral time, Unmixing the mixed volume computation, Sparse resultants and straight-line programs, The convex hull of parking functions of length n, Efficiently counting affine roots of mixed trigonometric polynomial systems, An efficient tree decomposition method for permanents and mixed discriminants, Volume of convex polytopes equals mixed volume of simplices, Computing tropical resultants, (Deterministic) algorithms that compute the volume of polytopes, On the possibilistic approach to linear regression models involving uncertain, indeterminate or interval data, Elimination for generic sparse polynomial systems, A systematic framework for solving geometric constraints analytically, On the reverse Loomis-Whitney inequality, A Polyhedral Method for Solving Sparse Polynomial Systems, Approximation of convex sets by polytopes, Solving degenerate sparse polynomial systems faster, A polynomial-time algorithm to approximate the mixed volume within a simply exponential factor, An Implementation of Exact Mixed Volume Computation, How to count efficiently all affine roots of a polynomial system, Toric intersection theory for affine root counting, Some speed-ups and speed limits for real algebraic geometry, Heat flow and a faster algorithm to compute the surface area of a convex body