A polynomial number of random points does not determine the volume of a convex body

DOI10.1007/S00454-011-9328-XMaRDI QIDQ542396zbMATH OpenOpenAlexFDO

Authors Ronen Eldan

Publication date 10 June 2011

Published in Discrete \& Computational Geometry (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0903.2634

zbMATH Keywords

convex bodiesdistribution of mass on convex bodiesrandom point oraclesampling convex bodiesvolume computing algorithms

Mathematics Subject Classification ID

Random convex sets and integral geometry (aspects of convex geometry) (52A22)

Abstract: 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.

Review text

The author gives a negative answer to the question of existence of a volume computing algorithm using a random point oracle in case of high-dimensional convex body. It is shown that a polynomial number of points does not contain enough information to estimate the volume, regardless of the number of calculations. The main result from this paper is in the following Theorem: ``There do not exist constants \(C,p,k>0\) such that for any dimension \(n\), there exists an algorithm with complexity \(O(n^{k})\) which is correct in estimating the volume of convex bodies in \(\mathbb{R}^{n}\) up to \(C\) with probability \(p\).

Recommendations

• scientific article; zbMATH DE number 18983
• Random walks in a convex body and an improved volume algorithm
• scientific article; zbMATH DE number 65730
• Approximating the volume of convex bodies
• scientific article; zbMATH DE number 1149839

Cites work

• A random polynomial-time algorithm for approximating the volume of convex bodies
• Computing the volume is difficult
• scientific article; zbMATH DE number 1149839 (Why is no real title available?)
• Power-law estimates for the central limit theorem for convex sets
• Random walks in a convex body and an improved volume algorithm

Cited in

(4)

• How to compute the volume in high dimension?
• scientific article; zbMATH DE number 18983 (Why is no real title available?)
• Testing convexity of figures under the uniform distribution
• scientific article; zbMATH DE number 7758320 (Why is no real title available?)

This page was built for publication: A polynomial number of random points does not determine the volume of a convex body

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q542396)