24
$\begingroup$

Suppose you have $n$ points picked uniformly at random on the surface of $\mathbb{S}^d,$ and let the volume of the convex hull of these points be $V_{n, d}.$ Clearly, $V_{n, d}$ converges to the volume of the unit ball in $\mathbb{R}^{d+1}$ as $n$ goes to infinity, but what is the distribution (or at least the expectation) of the difference? For $d=1,$ it is a simple computation that the $V_{n, 1} - \pi = O(1/n^3)\dots$

(there seem to be a number of questions and references about points in polygons, but I seem to be failing to find anything on spheres...)

$\endgroup$
  • 1
    $\begingroup$ Do simulations lead to a conjecture? $\endgroup$ – Eckhard Sep 21 '14 at 17:30
  • 4
    $\begingroup$ renyi.hu/~barany/cikkek/31.pdf This is slightly different problem (points are chosen not on the surface, but inside a body),though seems intimately connected. Maybe, it makes sense to ask Imre Bárány directly. $\endgroup$ – Fedor Petrov Sep 21 '14 at 18:29
  • 9
    $\begingroup$ arxiv.org/abs/1103.4978 and sciencedirect.com/science/article/pii/S0195669807000650 consider more generally a boundary of a convex body instead of $\mathbb{S}^d$ $\endgroup$ – Moritz Firsching Sep 21 '14 at 20:15
  • $\begingroup$ @MoritzFirsching Very cool, that certainly answers it! $\endgroup$ – Igor Rivin Sep 22 '14 at 0:10
  • $\begingroup$ @MoritzFirsching If you give your comment as an answer, I will be happy to accept it... $\endgroup$ – Igor Rivin Sep 22 '14 at 2:09
16
$\begingroup$

As mentioned in the comments, this question has been answered for random pointes on the boundary of convex bodies and even better for all intrinsic volumes. Let me offer some references:

A good refernce is:

Matthias Reitzner, Random points on the boundary of smooth convex bodies, Trans. Amer. Math. Soc. 354, 2243-2278, 2002

Abstract:

The convex hull of $n$ independent random points chosen on the boundary of a convex body $K \subset \mathbb{R}^d$ according to a given density function is a random polytope. The expectation of its $i$-th intrinsic volume for $i=1, \dots, d$ is investigated. In the case that the boundary of $K$ is sufficiently smooth, asymptotic expansions for these expected intrinsic volumes as $n \to \infty$ are derived.


By Ross M. Richardson, Van H. Vu and Lei Wu there are two papers, which are very simlilar:

Random inscribing polytopes, European Journal of Combinatorics. Volume 28, Issue 8, Pages 2057–2071, November 2007

and

An Inscribing Model for Random Polytopes, Discrete & Computational Geometry, Volume 39, Issue 1-3, pp 469-499, March 2008

With the following abstract:

For convex bodies $K$ with $\mathcal{C}^2$ boundary in $\mathbb{R}^d$ , we explore random polytopes with vertices chosen along the boundary of $K$. In particular, we determine asymptotic properties of the volume of these random polytopes. We provide results concerning the variance and higher moments of this functional, as well as an analogous central limit theorem.


Another more recent reference is

Károly J. Böröczky, Ferenc Fodor, Daniel Hug, Intrinsic volumes of random polytopes with vertices on the boundary of a convex body, Trans. Amer. Math. Soc. 365, 785-809, 2013, arxiv link

Let $K$ be a convex body in $\mathbb{R}^d$, let $j\in\{1, ..., d-1\}$, and let $\varrho$ be a positive and continuous probability density function with respect to the $(d-1)$-dimensional Hausdorff measure on the boundary $\partial K$ of $K$. Denote by $K_n$ the convex hull of $n$ points chosen randomly and independently from $\partial K$ according to the probability distribution determined by $\varrho$. For the case when $\partial K$ is a $C^2$ submanifold of $\mathbb{R}^d$ with everywhere positive Gauss curvature, M. Reitzner proved an asymptotic formula for the expectation of the difference of the $j$th intrinsic volumes of $K$ and $K_n$, as $n\to\infty$. In this article, we extend this result to the case when the only condition on $K$ is that a ball rolls freely in $K$.

$\endgroup$
  • 4
    $\begingroup$ Cool answer. And fantastic profile picture! $\endgroup$ – Vidit Nanda Sep 22 '14 at 10:26
5
$\begingroup$

Average area (over $100$ trials) of $n$ points uniformly distributed on a unit-radius circle:


          CircArea
One $n=6$ example:
         


$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.