Saturday, March 21, 2009

Trolled from the arXiv... volume estimation...

Just posted on math.PR, math.MG:
A Polynomial Number of Random Points does not Determine the Volume of a Convex Body
Ronen Eldan

We show that there is no algorithm which, provided a polynomial number of random points uniformly distributed over a convex body in R^n, can approximate the volume of the body up to a constant factor with high probability.

Specifically, you can't estimate the volume of a convex body merely by sampling. You need to generate new points that are "near" the old ones, and use a membership oracle as well.


Disqus for The Geomblog