A Polynomial Number of Random Points Does Not Determine the Volume of a Convex Body

作者：Eldan Ronen^*

来源：Discrete & Computational Geometry, 2011, 46(1): 29-47.

DOI：10.1007/s00454-011-9328-x

• Convex bodies
• Random point oracle
• Volume computing algorithms
• Sampling convex bodies
• Distribution of mass on convex bodies

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

• 出版日期2011-7