An algorithm for estimating volumes and other integrals in n dimensions
share
The computational cost in evaluation of the volume of a body using numerical integration grows exponentially with dimension of the space n. Today's most generally applicable algorithms for estimating n-volumes and integrals are based on Markov Chain Monte Carlo (MCMC) methods; they are suited for convex domains. We present an alternate statistical method for estimating an n-dimensional integral that is suited even for non-convex domains and scales as O(n) in the samples required, given any distribution of extents of the arbitrary domain and the allowed tolerance in relative error. This results due to the possible decomposition of an arbitrary n-volume into an integral of statistically weighted volumes of n-spheres.
READ FULL TEXT