A Random Polynomial-Time Algorithm for Approximatingthe Volume of Convex BodiesMARTIN DYERlInll,ersitJ oj’Leeds, Leeds, EnglandANDALAN FRIEZE AND RAVI KANNANCurnegw-%lellon Uniwsity, Pittsburgh, PennsylvaniaAbstract. A randomized polynomial-time algorithm for approximating the volume of a convex body Kin n-dimensional Euclidean space is presented. The proof of correctness of the algorithm relies on recenttheory of rapidly mixing Markov chains and isoperimetric inequalities to show that a certain randomwalk can be used to sample nearly uniformly from withinK.Categories and Subject Descriptors: F.2.2 [Analysis of Algorithms and Problem Complexity]: Non-numencal Algorithms and Problems—geometricproblems and computations: G.3 [Probability andStatistics] —prubabihstic algorithms (inrluditlg Monte Carlo)General Terms AlgorithmsAdditional Key Words and Phrases: Convex sets, random walks, sampling, volume1. IntroductionIn this paper, we give an algorithm for approximating the volume of a convex bodyin Euclidean space. Our algorithm is a randomized polynomial-time-boundedalgorithm. In other words, suppose we are given a convex body K, determined bya membership oracle (see [9]) and a relative error bound c Then, our algorithmtakes time bounded by a polynomial in n, the dimension of the body K and 1/c.With probability at least 3/4,itfinds an c approximation to the volume of K.(Here, as usual, we count unit time per call to the oracle. Observe that we canmake the failure probability as small as we like by repeatedly running the algorithmand taking the median value as output [12, 13]. ) Our result should be contrastedwith results of Elekes [6], BarAny and Furedi [2], and Dyer and Frieze [5]. Inparticular, the first two of these references show that, with such an oracle. it is notpossible to approximate the volume of a convex set within even a polynomialfactor in deterministic polynomial time. In fact, Barany and Furedi showed thatthe best one could do was to get within a factor of the volume that is exponentialin n. Grotschel et al. [9] had already given such an approximation algorithm.Furthermore, Dyer and Frieze [5] show that if K is a polyhedron. given either by alist of its facets or its vertices then it is # P-hard to compute the volume of KThe work of R. Kannan was supported by National Science Foundation (NSF) grants ECS-84- 18392and CCR 88-05199.Authors’ addresses: M. Dyer, School of Computer Studies, University of Leeds. Leeds, U. K.: A. Frieze,Mathematics Department, Carnegie-Mellon Umversity, Pittsburgh, PA 15213-2890: R. Kannan. De-partment of Computer Science, Carnegie-Mellon University, Pittsburgh. PA 152.13-2890.Permission to copy without fee all or part of this material is granted provided that the copies are notmade or distributed for direct commercial advantage, the ACM copyright notice and the title of thepublication and its date appear, and notice 1sgiven that copying is by permission of the Association forComputing Machinery. To copy otherwise, or to republish, requires a fee and/or specific permission.@ 1991 ACM 0004-541 1/91/0100-0001 $01.50Journal of the Assomatmnfor Computing Machmer?. Vol 38. No 1, January 1991. PP 1-17~DYER ET AL.exactl]. B> comparing our results 11-ith these. l~e see that here is a case whererandomness gi~es a super-pol:-nomlal speed-up In computing power.Ii-e remark that one consequence of our algorithm is that the number of linearextensions of a partial order can be similarl: approximated (see, for example.[14, p. 61]).Our algorithm is based on a scheme for sampling nearl: uniformly from withink-. To do this, we place a grid conslstmg of cubes of side 0( l/n5’2) and do arandom walk over the cubes in the grid that intersect a slightl:- smoother enlarge-ment of A-. For this random \valk. it is not difficult to sho]~ that eventually it“settles down” to being nearl>- uniform. \Vhat is much more ddlleult to show isthat the time taken to settle down is polj-nomial, To do this. we use results on thetheory of rapidly mixing Markov chains. In particular. we emplo>- an extremelyuseful result of Sinclair and Jerrum [ 16]. \vhich relates the rapid mixing propertyto structural properties of the chain that are somewhat easier to establish. We notethat Jerrum and Sinclair [11] have used this result to rigorousl:- \ enfy Broder’salgorithm [4] for approximating dense permanents. These methods are likely toj-ield further interesting results. See Aldous [ 1] for an expositon- paper on othermethods for establishing the rapid mlxmg propert>-. The ke: step in the Sinclair–Jerrum approach is to establish an lsoperimetnc inequaht> for the graph underlyingthe random walk. To do this. we use a result from differential geometry. that is.the isoperimetric inequality of B6rard et al. [3] which generalizes the more classi-cal inequality of Levy-Gromov (see Mdman and Schechtmann [15]) on the vol-ume of the boundary of subsets of smooth Riemannian manifolds with positivecurvature.In the next few sections, we make these arguments more precise, In Section 2,we describe the random walk and the algorithm. In Section 3. u e show thatthe algorithm has the claimed properties under the assumption that the cmzdz~ct-ance [16] of our Markov chain is at least l/q(t?) \vhere. q(. ) is a polynomial. InSection 4. we verify this claim. The final section contains some technical lemmas.1.1 NOTATION AND VALUES USED THROLTGHOUT. )? z 3 is the dimension ofthe body whose volume is to be approximated. and O < c < 1 is the desired degreeof approximation.r=Ji(H+ 1)Random Algoritllnlfor Convex BodJ’ Volume3All logarithms are to the base e unless otherwise specified.B is the unit ball in R“ with the origin as center, and o,, denotes its surface area.By a convex bodj’, we mean a closed, bounded convex set of nonzero volume.For any convex set K and nonnegative real number, a, we denote by OK the“dilation” of K by a factor of a, that is, aK = {M: x E K}.If T C S c Rm, we denote the “boundary” of T with respect to S by d,YT. This isthe set of points .Y in the closure of T such that any ball in R’” with x as centerintersects S\ T. Usually, the context will make clear what S is, so we will denotedsTasd T.For any set Kin R’” and a nonnegative real number A, we denote by K(A) theset of points at distance at most A from K. If K is convex, it is easy to see that K( X)is too.All our convex bodies will be given a so-called “well-guaranteed membershiporacles, ” that is,