In the analysis of algorithms, several authors have studied the computation of the

volume Volume is a measure of occupied 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). Th ...

of high-dimensional

convex bodies In mathematics, a convex body in n-dimensional Euclidean space \R^n is a compact convex set with non-empty interior. A convex body K is called symmetric if it is centrally symmetric with respect to the origin; that is to say, a point x lies in ...

, 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 infini ...

. 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. 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 far ...

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 Martin Edward Dyer (born 16 July 1946 in Ryde, Isle of Wight, England) is a professor in the School of Computing at the University of Leeds, Leeds, England. He graduated from the University of Leeds in 1967, obtained his MSc from Imperial College ...

, Alan M. Frieze and

Ravindran Kannan Ravindran Kannan ( ta, ரவீந்திரன் கண்ணன்; born 12 March 1953, Madras) is a Principal Researcher at Microsoft Research India, where he leads the algorithms research group. He is also the first adjunct faculty of ...

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. 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) methods comprise a class of algorithms for sampling from a probability distribution. By constructing a Markov chain that has the desired distribution as its equilibrium distribution, one can obtain ...

(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 is a random process that describes a path that consists of a succession of random steps on some mathematical space. An elementary example of a random walk is the random walk on the integer number line \mathbb Z ...

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 of ...

, 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 In computational geometry, Klee's measure problem is the problem of determining how efficiently the measure of a union of ( multidimensional) rectangular ranges can be computed. Here, a ''d''-dimensional rectangular range is defined to be a Cart ...

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 '' Discrete & Computational Geometry'' is a peer-reviewed mathematics journal published quarterly by Springer. Founded in 1986 by Jacob E. Goodman and Richard M. Pollack, the journal publishes articles on discrete geometry and computational geome ...

, mr = 911186 , pages = 319–326 , title = Computing the volume is difficult , volume = 2 , year = 1987, doi-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 is ...

, 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'' 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 Venkatesan ...

, 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 =

, 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 , 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