The following easily stated problem has arisen in my research. However, it's outside my field, and I'm unfamiliar with the literature. I would greatly appreciate any references.

Let $K\subset \mathbb{R}^d$ be a convex polytope, and let $f=f(v)$ be a probability mass function on $K$'s vertices. Assume I draw $n$ vertices $v_1,\dots,v_n$ randomly according to $f$, and let $K_n$ be the convex hull of $\{v_1,\dots,v_n\}$. Note $K_n$ is a random convex polytope that is a subset of $K$.

I would like to estimate or bound the expectation of the volume difference $$ \mathbb{E}\left[\frac{\text{vol}(K \backslash K_n)}{\text{vol}(K)}\right], $$ or estimate the probability $$ \text{Prob}\left[\,\frac{\text{vol}(K \backslash K_n)}{\text{vol}(K)}\;\geq\; t\,\right]. $$ Assume, of course, that $f(v)>0$ for all vertices.

I found a survey, Random Polytopes, Convex Bodies, and Approximation, by Bárány that seems closely related, but the problem set up is slightly different. I suspect this problem has been studied before.

  • $\begingroup$ The article you cite appears to be a comprehensive survey of random polytope approximations of convex bodies. It seems fairly comprehensive covering both the case of smooth and non-smooth boundaries including the convex polyhedron $K$. $\endgroup$ Aug 31 '16 at 22:17
  • $\begingroup$ Yes, it is comprehensive for its problem. However, the sampling scheme they study is different. They are sampling points uniformly from the interior of the polytope and constructing the convex hull. Then they study the approximation as the number of samples goes to infinity. If the sampling is, instead, from the polytope's vertices, then the analysis is different. $\endgroup$ Aug 31 '16 at 22:30
  • $\begingroup$ Still seems like a good find. You probably want to mention in your post that it is a survey and not just a set of notes. Also, the smooth case seems to be discussed here projecteuclid.org/download/pdf_1/euclid.aoap/1075828053 $\endgroup$ Aug 31 '16 at 22:38

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.