Complexity of polytope volume computation

From MaRDI portal





The author surveys recent complexity results of computing the volume \(V(P)\) of a convex polytope \(P\) in \(\mathbb{R}^ n\). In Part 1 the differentiability properties of \(V(P \cap H(t))\), \(-\infty<t<+\infty\), are investigated where \(H(t)\) is a halfspace of the form \(\{x:x \cdot a \leq t\}\). In Part 2 exact volume computation is discussed and Part 3 contains a description of the randomized algorithm of Dyer, Frieze and Kannan. For the entire collection see [Zbl 0773.00009].




Cited in
(29)








This page was built for publication: Complexity of polytope volume computation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3138745)