Simulated annealing in convex bodies and an O*(n/sup 4/) volume algorithm

摘要

We present a new algorithm for computing the volume of a convex body in R/sup n/. The main ingredient of the algorithm is a "morphing" technique that can be viewed as a variant of simulated annealing. Its complexity is O*(n/sup 4/), improving on the previous best algorithm by a factor of n.