Probability that $n$ uniform random points of a convex body are in convex position

edit · history · discussion · files · short url · probability theory elementary geometry

Numbers

$K$

$n$

$p_K(n)$

triangle

comment: Three independent uniform area points are noncollinear with probability $1$.

triangle

2/3

comment: This is Sylvester's four-point probability.

triangle

11/36

triangle

91/900

triangle

17/675

triangle

323/66150

parallelogram

comment: Three independent uniform area points are noncollinear with probability $1$.

parallelogram

25/36

comment: This is Sylvester's four-point probability.

parallelogram

49/144

parallelogram

49/400

parallelogram

121/3600

parallelogram

20449/2822400

ellipse

comment: Three independent uniform area points are noncollinear with probability $1$.

ellipse

0.7044798810431814999553515656382943865289535738726142325336403236419950638601466298589729510502696403

comment: This is Sylvester's four-point probability, $1-35/(12\pi^2)$ [3].

ellipse

0.3561883122726454106170159108548556277952202859367667208768592765057749605524623007641910719309445735

comment: The exact value is $1-305/(48\pi^2)$ [3].

ellipse

0.1343093863571099388567519390562815222062074839436436122362857629960799547838824432027786620320200015

comment: The exact value is $1-(146400\pi^2-473473)/(11520\pi^4)$ [3].

ellipse

0.03909056230070790319009578457274220307412526130314250142005362829091538567473484718778033253057964058

comment: The exact value is $1-(512400\pi^2-2900611)/(23040\pi^4)$ [3].

ellipse

0.009034262164855343163545962523547630210849646555099686962509365970595457222086937730075448400680513119

comment: The exact value is $1-(62664108221+1721664000\pi^4-18670881600\pi^2)/(48384000\pi^6)$ [3].

Definition

The convex-position probability $p_K(n)$ is the probability that $n$ independent points sampled uniformly by area in a planar convex body $K$ are all vertices of their convex hull [3].

Parameters

$K$

— affine class of the planar convex body (A compact convex subset of the plane with nonempty interior, considered up to invertible affine transformation.)

$n$

— number of sampled points ($n\geq 3$.)

Formulas

(9)

$p_{AK+b}(n)=p_K(n)$ for every invertible real $2\times2$ matrix $A$ and every $b\in\mathbb R^2$. An invertible affine map preserves vertices and sends normalized area measure to normalized area measure.

(2)

For a triangle $T$, $p_T(n)=\dfrac{2^n(3n-3)!}{((n-1)!)^3(2n)!}$ for $n\geq3$ [2].

(3)

For a parallelogram $S$, $p_S(n)=\left(\dfrac{\binom{2n-2}{n-1}}{n!}\right)^2$ for $n\geq3$ [1].

(4)

If $C_m(q)$ is the Carlitz-Riordan $q$-Catalan polynomial, then $p_S(n)=\left(C_{n-1}(1)/(n-1)!\right)^2$. The specialization $C_m(1)$ counts Dyck paths of semilength $m$.

(5)

$\dfrac{p_T(n+1)}{p_T(n)}=\dfrac{2(3n)(3n-1)(3n-2)}{n^3(2n+2)(2n+1)}$ for $n\geq3$, with $p_T(3)=1$.

(6)

$\dfrac{p_S(n+1)}{p_S(n)}=\left(\dfrac{2(2n-1)}{n(n+1)}\right)^2$ for $n\geq3$, with $p_S(3)=1$.

(7)

$p_K(4)=1-4\,\mathbf E[\operatorname{Area}(\operatorname{conv}\{X_1,X_2,X_3\})]/\operatorname{Area}(K)$. Outside a null set, a nonconvex configuration of four points has exactly one point inside the triangle formed by the other three.

(8)

$p_K(n+1)\leq p_K(n)$ for $n\geq3$, since every subset of a set in convex position is itself in convex position.

Comments

(9)

The parameter $K$ is the body argument of the probability $p_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 means normalized two-dimensional area measure, including the interior.

(10)

The points are sampled independently. There is no imposed cyclic order, no fixed boundary point, and no conditioning on the convex hull. Collinear triples and repeated points have probability zero.

(11)

The case $n=4$ is Sylvester's four-point problem [3]. At $n=3$ the probability is $1$ for every planar convex body with nonempty interior.

(12)

The triangle and parallelogram entries are exact rational numbers. The nontrivial ellipse entries are decimal enclosures of the exact expressions in their comments.

Programs

(P1)

Sage

# Exact probabilities for n uniform area points in a triangle or parallelogram.
import numberdb.sage as numberdb
from sage.rings.rational_field import QQ
from math import comb, factorial
n = 4
p_triangle = QQ(2**n * factorial(3*n-3)) / QQ(factorial(n-1)**3 * factorial(2*n))
p_parallelogram = (QQ(comb(2*n-2, n-1)) / QQ(factorial(n)))**2
print(p_triangle, p_parallelogram)

(P2)

Sage

# Sylvester's probability for four uniform area points in any ellipse.
import numberdb.sage as numberdb
from sage.rings.real_arb import RealBallField
R = RealBallField(413)
print(1 - R(35)/(12*R.pi()**2))

References

[1]

P. Valtr, Probability that n random points are in convex position, Discrete & Computational Geometry 13 (1995), 637–643. (doi)

[2]

P. Valtr, The probability that n random points in a triangle are in convex position, Combinatorica 16 (1996), 567–573. (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

[4]

Marckert: explicit disk formulas and the segment-integral recurrence (preprint)

[5]

Valtr: On the probability that n random points are in convex position, DIMACS seminar abstract

Similar tables

Carlitz-Riordan q-Catalan numbers — Their values at $q=1$ give the Catalan numbers in the parallelogram probability.

Data properties

Entries are of type: real number

How well the digits are known: proven

Table is complete: no (it holds every $n$ from $3$ through $8$ for the affine classes of triangles, parallelograms and ellipses; this common range includes the classical four-point problem and all five nontrivial disk probabilities explicitly displayed in the cited preprint, without gaps between the three classes)

Sources of data: [1], [2], [3]

How they were obtained:

Thirteen entries are exact Sage rationals. The five nontrivial ellipse probabilities use Arb ball arithmetic with 80 guard bits beyond 100 significant digits. Their maximum measured ball radius is less than $2\times10^{-123}$, and the least relative accuracy exceeds 120 decimal digits. Their exact expressions are transcribed from equation (7) of [4], which gives the complementary probabilities $1-p_D(n)$ for a disk $D$. The parallelogram formula also appears in the author's abstract [5].

The rational recurrence computations agree with independent factorial evaluations throughout the range. For parallelograms, direct enumeration of Dyck paths gives the same Catalan counts, also checked against the stored Carlitz-Riordan polynomials at $q=1$. Disk segment convolution integrals from Theorem 1 of the preprint are evaluated independently at 130 and 170 decimal digits for $3\leq n\leq7$, with the known value at $n=3$ serving as a normalization control. At $n=8$, a second high-precision evaluation rearranges the same published closed form; it is not an independent derivation.

A separate line-coordinate integral of the expected area of a random triangle verifies the disk four-point value. The change of variables is first checked against the known product of two disk areas. Uniform-point simulations use 500000 samples for each of the three regions and test all six sample sizes, together with sampler moments, known geometric controls and affine transformations. Every estimate differs from its predicted probability by less than two standard errors. The simulations and numerical quadratures are diagnostic checks. The exact arithmetic and Arb enclosures of the published formulas justify the stored precision. The attached checks also test the entries read back from the database.