A randomized polynomial-time algorithm for approximating the volume of a convex body K in n -dimensional Euclidean space is presented. The proof of correctness of the algorithm relies on recent theory of rapidly mixing Markov chains and isoperimetric inequalities to show that a certain random walk can be used to sample nearly uniformly from within K .
We show that computing the volume of a polyhedron given either as a list of facets or as a list of vertices is as hard as computing the permanent of a matrix.