Expected number of vertices of the convex hull of $n$ uniform random points
edit · history · discussion · files · long url · probability theory elementary geometry
Numbers
$K$
$n$ 
$e_K(n)$
triangle
4:
11/3
triangle
5:
25/6
triangle
6:
137/30
triangle
7:
49/10
triangle
8:
363/70
triangle
9:
761/140
triangle
10:
7129/1260
triangle
11:
7381/1260
triangle
12:
83711/13860
triangle
13:
86021/13860
triangle
14:
1145993/180180
triangle
15:
1171733/180180
triangle
16:
1195757/180180
triangle
17:
2436559/360360
triangle
18:
42142223/6126120
triangle
19:
14274301/2042040
triangle
20:
275295799/38798760
parallelogram
4:
133/36
parallelogram
5:
305/72
parallelogram
6:
281/60
parallelogram
7:
3647/720
parallelogram
8:
217687/40320
parallelogram
9:
51031/8960
parallelogram
10:
1442363/241920
parallelogram
11:
187627/30240
parallelogram
12:
68410249/10644480
parallelogram
13:
141187553/21288960
parallelogram
14:
472038551/69189120
parallelogram
15:
553530163/79073280
parallelogram
16:
9067345117/1265172480
parallelogram
17:
18531607469/2530344960
parallelogram
18:
107136683491/14338621440
parallelogram
19:
327447366043/43015864320
parallelogram
20:
12660946977401/1634602844160
ellipse
4:
3.704479881043181499955351565638294386528953573872614232533640323641995063860146629858972951050269640
comment: The exact value is $4-35/(12\pi^2)$, obtained from the disk case of Sylvester's four-point problem.
ellipse
5:
4.261199702607953749888378914095735966322383934681535581334100809104987659650366574647432377625674101
ellipse
6:
4.727567555779794174307890231975216459751800405887649046835200472959323961470205249897636846539149674
ellipse
7:
5.132287486101441485468289612578181727002957649221397129253848823490177056369435363375715641197164507
ellipse
8:
5.491919496457589379714691889836316711329966522042113139617636620635170555580531819898810225145553968
ellipse
9:
5.816951568403909045437567267996425897521115979523575794359495250158153332427320622809568151999837037
ellipse
10:
6.114478823847501751007406437611507912141658009945466229727314656110694862858506404301917549344774190
ellipse
11:
6.389543105887125138742053133536292823655200102339096508988752307062832895714436190583954360684146334
ellipse
12:
6.645866482340570441298673249614638350654983888797519313967937433418786463528402786500661943116637614
ellipse
13:
6.886281710615615159278042231712855524150106874117828228748122900275151563595217969886546842874770151
ellipse
14:
7.112999077036621083201248920759196488457765697146154149682405112130292378712128255987655776506333524
ellipse
15:
7.327779317182812601438864931619620782977060146010610588783572147599284472294609612122706331588030433
ellipse
16:
7.532049871184049434569637626370679894667474231407307394245099250432850990350095283106201190372809678
ellipse
17:
7.726985501614797536094269226895721594828939163094485790185790267210775201682949778132964324528232517
ellipse
18:
7.913565697361177510349950081563984501723144856020179004509967140874343525577719086427975190054313552
ellipse
19:
8.092616493589788515127220062319525840603014993919363114803975115417458273573133268783749000487982523
ellipse
20:
8.264841553092724186426776334570296333005260333127557471772667634613102053280288624950691397277578266
Definition
For independent points $X_1,\ldots,X_n$ uniformly distributed by volume throughout a convex body $K$, let $N_n(K)$ be the number of vertices of their convex hull. This table gives the single quantity $e_K(n)=\mathbf E[N_n(K)]$ as a function of the convex body $K$ and the sample size $n$ [1].
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\geq1$.)
Formulas
(8)
$e_{AK+b}(n)=e_K(n)$ for every invertible real $d\times d$ matrix $A$ and every $b\in\mathbb R^d$.
(2)
$e_K(n)=n\bigl(1-v_K(n-1)\bigr)$ for $n\geq2$, where $v_K(m)$ is the expected hull-volume ratio for $m$ independent uniform points in $K$ [1] [3]. A specified sample point is a vertex exactly when it lies outside the convex hull of the other points.
(3)
For a triangle $T$ and $n\geq2$, $e_T(n)=2H_{n-1}$, where $H_m=\sum_{k=1}^m1/k$ is the $m$th harmonic number [2] [4].
(4)
For a parallelogram $S$ and $n\geq2$, $e_S(n)=\dfrac83\left(\sum_{k=1}^n\dfrac{1-2^{-k}}{k}-\dfrac{1}{n2^n}\right)$ [2] [4].
(5)
For a filled ellipse $D$ and $n\geq2$, put $F(\theta)=(\theta-\sin\theta\cos\theta)/\pi$. Then $e_D(n)=\dfrac{8n(n-1)}{3\pi}\int_0^\pi\sin^4\theta\,F(\theta)^{n-2}\,d\theta$ [1]. For the unit disk, $F(\theta)$ is the area fraction to the left of the vertical line at coordinate $-\cos\theta$.
(6)
For a planar convex body $K$, $e_K(4)=3+p_K(4)$, where $p_K(4)$ is the probability that four independent uniform points are in convex position. The hull has four vertices in convex position and three otherwise, outside a null set.
(7)
For a planar convex body and $n\geq4$, $3<e_K(n)<n$.
Comments
(8)
The body $K$ is an argument of the single quantity $e_K(n)$. Each region label denotes an affine class: all nondegenerate triangles, all nondegenerate parallelograms, or all filled nondegenerate ellipses. An invertible affine map preserves vertices and carries normalized volume measure to normalized volume measure.
(9)
The points are independent, with no imposed cyclic order and no conditioning on their hull. They are sampled throughout the interior, rather than on the boundary. Coincident points and affine dependencies among at most $d+1$ points have probability zero.
(10)
For $1\leq n\leq d+1$, all sampled points are vertices with probability one, so $e_K(n)=n$. In the plane these universal cases are omitted; the first nontrivial case is $n=4$.
(11)
The triangle and parallelogram entries are exact rationals. The ellipse entries are decimal enclosures with 100 significant digits. The expectation is a real number although each realized hull has an integer number of vertices.
Programs
(P1)
Sage
import numberdb.sage as numberdb
from sage.rings.rational_field import QQ

def triangle_vertices(n):
    if n == 1:
        return QQ(1)
    return 2*sum(QQ(1)/k for k in range(1,n))

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

print(triangle_vertices(4), parallelogram_vertices(4))
(P2)
Sage
import numberdb.sage as numberdb
from sage.rings.complex_arb import ComplexBallField
from sage.rings.rational_field import QQ

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

print(ellipse_vertices(4))
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]
C. Buchta, The duality of the volumes and the numbers of vertices of random polytopes, Discrete & Computational Geometry 70 (2023), 951–959. (doi)
Links
Similar tables
Expected hull-volume ratios —   Efron's identity converts the expected volume fraction for $n-1$ points into the expected vertex count for $n$ points.
Convex-position probabilities —   The four-point probability is $e_K(4)-3$ in the plane.
Harmonic numbers —   For a triangle, the expected count is twice $H_{n-1}$.
Data properties
Entries are of type: real number
Table is complete: no (it holds every $n$ from $4$ through $20$ for the affine classes of triangles, parallelograms and filled ellipses, covering the first nontrivial four-point case 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 34 triangle and parallelogram values use exact rational arithmetic. The 17 ellipse values use Arb's certified integration of an entire trigonometric integrand, with 80 guard bits beyond 100 significant digits. The maximum measured absolute radius is less than $1.34\times10^{-121}$. Every enclosure is required to be finite and to have relative radius below $10^{-110}$.

more

Independent exact integration of hull-edge probabilities reproduces every rational entry. For triangles this integrates over the three pairs of boundary edges. For squares it separates the four adjacent and two opposite pairs. The controls are the known three-point expectation $3$ and the four-point expectations $11/3$ and $133/36$.

A separate signed-area integral from printed page 15 of [5], combined with Efron's identity, checks each ellipse value at 130 and 170 decimal digits. The mean area fraction $35/(48\pi^2)$ for three disk points is tested first as a normalization control. The two quadratures agree within $10^{-125}$, and they agree with the Arb values within $10^{-115}$. The expected-edge integral also passes its three-point control $3$ and the four-point closed form $4-35/(12\pi^2)$. Numerical quadrature supplies agreement checks; the Arb enclosures justify the stored digits.

The attached checks compare all 51 entries read back from the database with the independent computations, test all 51 Efron relations to the hull-volume ratios, test the three four-point relations to the convex-position probabilities, and check $3<e_K(n)<n$ for every stored entry.