# Polynomial-time algorithm for approximating the volume of convex bodies

The main result of the paper is a randomized algorithm for finding an ${\displaystyle \epsilon }$ approximation to the volume of a convex body ${\displaystyle K}$ in ${\displaystyle n}$-dimensional Euclidean space by assuming the existence of a membership oracle. The algorithm takes time bounded by a polynomial in ${\displaystyle n}$, the dimension of ${\displaystyle K}$ and ${\displaystyle 1/\epsilon }$.
The algorithm is a sophisticated usage of the so-called Markov chain Monte Carlo (MCMC) method. The basic scheme of the algorithm is a nearly uniform sampling from within ${\displaystyle K}$ by placing a grid consisting ${\displaystyle n}$-dimensional cubes and doing a random walk over these cubes. By using the theory of rapidly mixing Markov chains, they show that it takes a polynomial time for the random walk to settle down to being a nearly uniform distribution.