Expected hull-volume ratio for $n$ uniform random points of a convex body
edit · history · discussion · files · short url · probability theory elementary geometry volume
Numbers
$K$
$n$ 
$v_K(n)$
triangle
3:
1/12
triangle
4:
1/6
triangle
5:
43/180
triangle
6:
3/10
triangle
7:
197/560
triangle
8:
499/1260
triangle
9:
5471/12600
triangle
10:
589/1260
triangle
11:
82609/166320
triangle
12:
7243/13860
triangle
13:
1376527/2522520
triangle
14:
1530967/2702700
triangle
15:
1687123/2882880
triangle
16:
217033/360360
triangle
17:
68127937/110270160
triangle
18:
1290761/2042040
triangle
19:
500679401/775975200
triangle
20:
107119657/162954792
parallelogram
3:
11/144
parallelogram
4:
11/72
parallelogram
5:
79/360
parallelogram
6:
199/720
parallelogram
7:
104873/322560
parallelogram
8:
29609/80640
parallelogram
9:
976837/2419200
parallelogram
10:
13183/30240
parallelogram
11:
59323511/127733760
parallelogram
12:
10428379/21288960
parallelogram
13:
496609129/968647680
parallelogram
14:
632569037/1186099200
parallelogram
15:
11175414563/20242759680
parallelogram
16:
1440250403/2530344960
parallelogram
17:
150958502429/258095185920
parallelogram
18:
25781792423/43015864320
parallelogram
19:
20031109905799/32692056883200
parallelogram
20:
300414017749019/480573236183040
ellipse
3:
0.07388002973920462501116210859042640336776160653184644186658991908950123403496334253525676223743258993
comment: The mean area of a random triangle, divided by the ellipse area, is $35/(48\pi^2)$.
ellipse
4:
0.1477600594784092500223242171808528067355232130636928837331798381790024680699266850705135244748651799
comment: The exact ratio is $35/(24\pi^2)$.
ellipse
5:
0.2120720740367009709486849613374639233746999323520584921941332545067793397549657916837271922434750543
comment: The exact ratio is $175/(72\pi^2)-23023/(6912\pi^4)$ [3].
ellipse
6:
0.2668160734140797877902443410602597532852917643969432672494501680728318490900806623748977655432622133
ellipse
7:
0.3135100629428013275356635137704604110837541847447358575477954224206036805524335225126487218568057541
ellipse
8:
0.3536720479551212171736036368892860113865426689418249117378338610935385186191865974656035386666847736
ellipse
9:
0.3885521176152498248992593562388492087858341990054533770272685343889305137141493595698082450655225810
ellipse
10:
0.4191324449193522601143588060421551978495272634237184991828406993579242822077785281287314217559866969
ellipse
11:
0.4461777931382857965584438958654468041120846759335400571693385472151011280392997677916115047402801988
ellipse
12:
0.4702860222603372954401505975605495750653763942986285977886059307480652643388293869318040890096330653
ellipse
13:
0.4919286373545270654856250770886288222530167359181318464512567777049791158062765531437388731066904626
ellipse
14:
0.5114813788544791599040756712253586144681959902659592940810951901600477018470260258584862445607979711
ellipse
15:
0.5292468830509969103393976483518325065832828605370432878596812968479468131031190448058624256016993951
ellipse
16:
0.5454714410814824978768076925355457885394741668767949535184829254581896940186500130510020985571627931
ellipse
17:
0.5603574612577123605361138843575564165709363968877678330827796032847586930234600507540013783303159138
ellipse
18:
0.5740728161268532360459357861937091662840518424252966781682118360306600908645719332219079473427377619
ellipse
19:
0.5867579223453637906786611832714851833497369833436221264113666182693448973359855687524654301361210867
ellipse
20:
0.5985311582615740895341810847996170022953424688357440073800596950651758171544390182086056604485911777
Definition
For independent uniform points $X_1,\ldots,X_n$ in a convex body $K$, the expected hull-volume ratio is $v_K(n)=\mathbf E|\operatorname{conv}\{X_1,\ldots,X_n\}|/|K|$ [1]. The body $K$ is an argument of this expectation.
Parameters
$K$
—   affine class of the convex body (A compact convex subset of $\mathbb R^d$ with nonempty interior, considered up to invertible affine transformations.)
$n$
—   number of sampled points ($n\geq d+1$, where $d$ is the dimension of $K$.)
Formulas
(8)
$v_{AK+b}(n)=v_K(n)$ for every invertible real $d\times d$ matrix $A$ and every $b\in\mathbb R^d$.
(2)
If $N_m(K)$ denotes the number of vertices of the convex hull of $m$ independent uniform points in $K$, then $v_K(n)=1-\mathbf E[N_{n+1}(K)]/(n+1)$ [1]. Conditionally on the first $n$ points, an additional uniform point lies inside their hull with probability equal to its volume fraction.
(3)
For a triangle $T$, $v_T(n)=1-\dfrac{2H_n}{n+1}$, where $H_n=\sum_{k=1}^n1/k$ is the $n$th harmonic number [2] [4].
(4)
For a parallelogram $S$, $v_S(n)=1-\dfrac{8}{3(n+1)}\left[\sum_{k=1}^{n+1}\dfrac{1-2^{-k}}{k}-\dfrac{1}{(n+1)2^{n+1}}\right]$ [2] [4].
(5)
For a filled ellipse $D$, put $F(\theta)=(\theta-\sin\theta\cos\theta)/\pi$ for $0\leq\theta\leq\pi$. Then $v_D(n)=1-\dfrac{8n}{3\pi}\int_0^\pi \sin^4\theta\,F(\theta)^{n-1}\,d\theta$ [1]. For the unit disk, $F(\theta)$ is the area fraction of the cap cut off by the line at signed distance $-\cos\theta$ from the center.
(6)
For a planar convex body $K$, $v_K(3)=(1-p_K(4))/4$, where $p_K(4)$ is the probability that four independent uniform points are in convex position. Outside a null set, each nonconvex four-point configuration has exactly one point inside the triangle formed by the other three.
(7)
$0<v_K(n)\leq v_K(n+1)<1$ for $n\geq d+1$. Adding an independent point can only enlarge the convex hull.
Comments
(8)
The convex body $K$ is the body argument of the single quantity $v_K(n)$. The region labels represent affine classes. The triangle row applies to every nondegenerate triangle, the parallelogram row to every nondegenerate parallelogram, and the ellipse row to every filled nondegenerate ellipse. Uniformity is with respect to area throughout the interior. An invertible affine transformation multiplies the hull area and the body area by the same factor.
(9)
The notation $|\cdot|$ means $d$-dimensional Lebesgue volume for a body in $\mathbb R^d$. The stored quantity is a dimensionless ratio. To recover the expected area or volume for a particular body, multiply $v_K(n)$ by that body’s area or volume. No boundary points are fixed and the sampled points have no imposed cyclic order.
(10)
For $n\leq d$ the $d$-dimensional hull volume is zero. These trivial values are omitted. For planar bodies, the first nonzero case is the mean area of a random triangle, which is related to Sylvester’s four-point convex-position probability.
(11)
The triangle and parallelogram entries are exact rational numbers. The ellipse entries are decimal enclosures with 100 significant digits; three small cases also have their closed forms stated in entry comments [3].
Programs
(P1)
Sage
import numberdb.sage as numberdb
from sage.rings.rational_field import QQ

def triangle_ratio(n):
    return 1-QQ(2)/(n+1)*sum(QQ(1)/k for k in range(1,n+1))

def parallelogram_ratio(n):
    s=sum((1-QQ(1)/2**k)/k for k in range(1,n+2))
    return 1-QQ(8)/(3*(n+1))*(s-QQ(1)/((n+1)*2**(n+1)))

print(triangle_ratio(3), parallelogram_ratio(3))
(P2)
Sage
import numberdb.sage as numberdb
from sage.rings.complex_arb import ComplexBallField

def ellipse_ratio(n, digits=100):
    C=ComplexBallField(numberdb.bits(digits, losing=80))
    pi=C.pi()
    def integrand(u, analytic):
        s=(pi*u).sin()
        c=(pi*u).cos()
        return s**4*(u-s*c/pi)**(n-1)
    return (1-C(8*n)/3*C.integral(integrand,0,1)).real()

print(ellipse_ratio(3))
References
[1]
B. Efron, The convex hull of a random set of points, Biometrika 52 (1965), 331–343. (doi)
[2]
C. Buchta, Zufallspolygone in konvexen Vielecken, Journal für die reine und angewandte Mathematik 347 (1984), 212–220. (doi)
[3]
J.-F. Marckert, The probability that n random points in a disk are in convex position, Brazilian Journal of Probability and Statistics 31 (2017), 320–337. (arXiv) (doi)
Links
Similar tables
Convex-position probabilities for uniform random points —   The four-point probability determines the expected area fraction for a three-point hull.
Data properties
Entries are of type: real number
Table is complete: no (it holds every $n$ from $3$ through $20$ for the affine classes of triangles, parallelograms and filled ellipses, covering the classical random-triangle means and small finite-sample hulls in a common range; other convex bodies and higher dimensions are not included)
Sources of data: [2], [1]
How they were obtained:

The 36 triangle and parallelogram values use exact rational arithmetic. The 18 ellipse values use Arb’s certified complex integration of an entire trigonometric integrand, with 80 guard bits beyond 100 significant digits. The largest measured relative radius is less than $6.1\times10^{-122}$. Every ball is required to be finite, to lie between zero and one, and to have a relative radius below $10^{-110}$.

more

The polygon formulas are displayed by their author in [4]. An independent exact integration of the signed area contributed by possible hull edges reproduces every rational entry. Its controls are the known three- and four-point means. The integration is repeated after an invertible affine map with determinant $5$ and a translation.

A separate signed-area integral, given for rotationally symmetric distributions on printed page 15 of [5], is evaluated for every ellipse entry at 135 and 175 decimal digits. The known three-point ratio is tested first as a normalization control. The two quadratures agree to absolute tolerance $10^{-130}$ and agree with the Arb computation to $10^{-118}$. Three closed forms at $n=3,4,5$, including the five-point expression in [6], are also checked in 600-bit ball arithmetic. The numerical quadratures are agreement checks; the generator’s Arb enclosures supply the certified digits.

All 54 entries read back from the database were compared with the independent computations. The stored values satisfy all 51 adjacent monotonicity comparisons and the three-point relation to the convex-position probabilities for each of the three affine classes. The attached checks reproduce these comparisons when run with access to the draft.