In the

analysis of algorithms In computer science, the analysis of algorithms is the process of finding the computational complexity of algorithms—the amount of time, storage, or other resources needed to execute them. Usually, this involves determining a function that r ...

, several authors have studied the computation of the

volume Volume is a measure of regions in three-dimensional space. It is often quantified numerically using SI derived units (such as the cubic metre and litre) or by various imperial or US customary units (such as the gallon, quart, cubic inch) ...

of high-dimensional convex bodies, a problem that can also be used to model many other problems in

combinatorial enumeration Enumerative combinatorics is an area of combinatorics that deals with the number of ways that certain patterns can be formed. Two examples of this type of problem are counting combinations and counting permutations. More generally, given an inf ...

. Often these works use a black box model of computation in which the input is given by a subroutine for testing whether a point is inside or outside of the convex body, rather than by an explicit listing of the vertices or faces of a

convex polytope A convex polytope is a special case of a polytope, having the additional property that it is also a convex set contained in the n-dimensional Euclidean space \mathbb^n. Most texts. use the term "polytope" for a bounded convex polytope, and the wo ...

. It is known that, in this model, no

deterministic algorithm In computer science, a deterministic algorithm is an algorithm that, given a particular input, will always produce the same output, with the underlying machine always passing through the same sequence of states. Deterministic algorithms are by fa ...

can achieve an accurate approximation, and even for an explicit listing of faces or vertices the problem is #P-hard. However, a joint work by Martin Dyer, Alan M. Frieze and Ravindran Kannan provided a randomized

polynomial time approximation scheme In computer science (particularly algorithmics), a polynomial-time approximation scheme (PTAS) is a type of approximation algorithm for optimization problems (most often, NP-hard optimization problems). A PTAS is an algorithm which takes an insta ...

for the problem, providing a sharp contrast between the capabilities of randomized and deterministic algorithms. The main result of the paper is a randomized algorithm for finding an

\varepsilon

approximation to the volume of a convex body

K

n

-dimensional Euclidean space by assuming the existence of a membership

oracle An oracle is a person or thing considered to provide insight, wise counsel or prophetic predictions, most notably including precognition of the future, inspired by deities. If done through occultic means, it is a form of divination. Descript ...

. The algorithm takes time bounded by a polynomial in

n

, the dimension of

K

and

1/\varepsilon

. The algorithm combines two ideas: *By using a

Markov chain Monte Carlo In statistics, Markov chain Monte Carlo (MCMC) is a class of algorithms used to draw samples from a probability distribution. Given a probability distribution, one can construct a Markov chain whose elements' distribution approximates it – that ...

(MCMC) method, it is possible to generate points that are nearly uniformly randomly distributed within a given convex body. The basic scheme of the algorithm is a nearly uniform sampling from within

K

by placing a grid consisting of

n

-dimensional cubes and doing a

random walk In mathematics, a random walk, sometimes known as a drunkard's walk, is a stochastic process that describes a path that consists of a succession of random steps on some Space (mathematics), mathematical space. An elementary example of a rand ...

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. *By using

rejection sampling In numerical analysis and computational statistics, rejection sampling is a basic technique used to generate observations from a distribution. It is also commonly called the acceptance-rejection method or "accept-reject algorithm" and is a type o ...

, it is possible to compare the volumes of two convex bodies, one nested within another, when their volumes are within a small factor of each other. The basic idea is to generate random points within the outer of the two bodies, and to count how often those points are also within the inner body. The given convex body can be approximated by a sequence of nested bodies, eventually reaching one of known volume (a hypersphere), with this approach used to estimate the factor by which the volume changes at each step of this sequence. Multiplying these factors gives the approximate volume of the original body. This work earned its authors the 1991

Fulkerson Prize The Fulkerson Prize for outstanding papers in the area of discrete mathematics is sponsored jointly by the Mathematical Optimization Society (MOS) and the American Mathematical Society (AMS). Up to three awards of $1,500 each are presented at e ...

Improvements

Although the time for this algorithm is polynomial, it has a high exponent. Subsequent authors improved the running time of this method by providing more quickly mixing Markov chains for the same problem.

Generalizations

The polynomial-time approximability result has been generalized to more complex structures such as the union and intersection of objects. This relates to Klee's measure problem.

References

{{reflist, refs= {{citation , last1 = Applegate , first1 = David , author1-link = David Applegate , last2 = Kannan , first2 = Ravi , author2-link = Ravindran Kannan , contribution = Sampling and Integration of Near Log-concave Functions , doi = 10.1145/103418.103439 , isbn = 978-0-89791-397-3 , location = New York, NY, USA , pages = 156–163 , publisher = ACM , title = Proceedings of the Twenty-Third Annual ACM Symposium on Theory of Computing (STOC '91) , year = 1991, s2cid = 15432190 , doi-access = free {{citation , last1 = Bárány , first1 = Imre , author1-link = Imre Bárány , last2 = Füredi , first2 = Zoltán , author2-link = Zoltán Füredi , doi = 10.1007/BF02187886 , issue = 4 , journal = Discrete and Computational Geometry , mr = 911186 , pages = 319–326 , title = Computing the volume is difficult , volume = 2 , year = 1987, doi-access = free , hdl = 1813/8572 , hdl-access = free {{citation , last1 = Dyer , first1 = Martin , author1-link = Martin Dyer , last2 = Frieze , first2 = Alan , author2-link = Alan M. Frieze , doi = 10.1137/0217060 , issue = 5 , journal =

SIAM Journal on Computing The ''SIAM Journal on Computing'' is a scientific journal focusing on the mathematical and formal aspects of computer science. It is published by the Society for Industrial and Applied Mathematics (SIAM). Although its official ISO abbreviation i ...

, mr = 961051 , pages = 967–974 , title = On the complexity of computing the volume of a polyhedron , volume = 17 , year = 1988 {{citation , last1 = Dyer , first1 = Martin , author1-link = Martin Dyer , last2 = Frieze , first2 = Alan , author2-link = Alan M. Frieze , last3 = Kannan , first3 = Ravi , author3-link = Ravindran Kannan , doi = 10.1145/102782.102783 , issue = 1 , journal =

Journal of the ACM The ''Journal of the ACM'' (''JACM'') is a peer-reviewed scientific journal covering computer science in general, especially theoretical aspects. It is an official journal of the Association for Computing Machinery. Its current editor-in-chief is ...

, mr = 1095916 , pages = 1–17 , title = A random polynomial-time algorithm for approximating the volume of convex bodies , volume = 38 , year = 1991, s2cid = 13268711 , doi-access = free {{citation , last = Elekes , first = G. , authorlink = György Elekes , doi = 10.1007/BF02187701 , issue = 4 , journal = Discrete and Computational Geometry , mr = 866364 , pages = 289–292 , title = A geometric inequality and the complexity of computing volume , volume = 1 , year = 1986, doi-access = free {{citation , last1 = Kannan , first1 = Ravi , author1-link = Ravindran Kannan , last2 = Lovász , first2 = László , author2-link = László Lovász , last3 = Simonovits , first3 = Miklós , author3-link = Miklós Simonovits , doi = 10.1002/(SICI)1098-2418(199708)11:1<1::AID-RSA1>3.0.CO;2-X , issue = 1 , journal = Random Structures & Algorithms , mr = 1608200 , pages = 1–50 , title = Random walks and an

O^*(n^5)

volume algorithm for convex bodies , volume = 11 , year = 1997 {{citation , last1 = Lovász , first1 = L. , author1-link = László Lovász , last2 = Simonovits , first2 = M. , author2-link = Miklós Simonovits , doi = 10.1002/rsa.3240040402 , issue = 4 , journal = Random Structures & Algorithms , mr = 1238906 , pages = 359–412 , title = Random walks in a convex body and an improved volume algorithm , volume = 4 , year = 1993 {{citation , last1 = Lovász , first1 = L. , author1-link = László Lovász , last2 = Vempala , first2 = Santosh , author2-link = Santosh Vempala , doi = 10.1016/j.jcss.2005.08.004 , issue = 2 , journal =

Journal of Computer and System Sciences The ''Journal of Computer and System Sciences'' (JCSS) is a peer-reviewed scientific journal in the field of computer science. ''JCSS'' is published by Elsevier, and it was started in 1967. Many influential scientific articles have been published ...

, mr = 2205290 , pages = 392–417 , title = Simulated annealing in convex bodies and an

O^*(n^4)

volume algorithm , volume = 72 , year = 2006, doi-access = free Computational geometry Approximation algorithms