Simulated annealing in convex bodies and an O*(n4) volume algorithm

摘要

We present a new algorithm for computing the volume of a convex body in Rn. The main ingredients of the algorithm are (i) a “morphing” technique that can be viewed as a variant of simulated annealing and (ii) a new rounding algorithm to put a convex body in near-isotropic position. The complexity is O*(n4), improving on the previous best algorithm by a factor of n.