A polynomial number of random points does not determine the volume of a convex body (Q542396)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A polynomial number of random points does not determine the volume of a convex body |
scientific article |
Statements
A polynomial number of random points does not determine the volume of a convex body (English)
0 references
10 June 2011
0 references
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\)''.
0 references
convex bodies
0 references
random point oracle
0 references
volume computing algorithms
0 references
sampling convex bodies
0 references
distribution of mass on convex bodies
0 references