Sylvester's Four-Point Problem

Sylvester's four-point problem asks for the probability that four points sampled independently and uniformly from a planar region of positive finite area have a convex hull which is a quadrilateral (Sylvester 1865). Depending on the method chosen to pick points from the infinite plane, a number of different solutions are possible, prompting Sylvester to conclude "This problem does not admit of a determinate solution" (Sylvester 1865, Pfiefer 1989).

For convex , the probability is given by

(1)

where is the expectation value of the area of a triangle formed by three points sampled independently and uniformly in , and is the area of (Efron 1965). Note that is simply the value computed for an appropriate region, e.g., disk triangle picking, triangle triangle picking, square triangle picking, etc., where can be computed exactly for polygon triangle picking using Alikoski's formula.

can range between

(2)

() depending on the shape of the region, as first proved by Blaschke (Blaschke 1923, Peyerimhoff 1997). The following table gives the probabilities for various simple plane regions (Kendall and Moran 1963; Pfiefer 1989; Croft et al. 1991, pp. 54-55; Peyerimhoff 1997).

The pentagon and hexagon rows refer to a regular pentagon and a regular hexagon, respectively.

		approx.
triangle		0.66667
square		0.69444
pentagon		0.70062
hexagon		0.70267
ellipse, disk		0.70448

For a positive integer , Sylvester's problem can be generalized to ask for the probability that the convex hull of points sampled independently and uniformly in the unit ball has vertices. The solution is given by

(3)

(Kingman 1969; Groemer 1973, pp. 526-527; Peyerimhoff 1997), which is the minimum over all convex bodies . Equality is attained exactly for ellipsoids. The first few values are

			(4)
			(5)
			(6)
			(7)
			(8)

(OEIS A051050 and A051051).

Another generalization asks for the probability that points sampled independently and uniformly in a fixed convex body are all vertices of their convex hull, where is a positive integer. For , this hull is a convex polygon with vertices. The solution is

(9)

for a triangle, which has first few values 1, 1, 1, 2/3, 11/36, 91/900, 17/675, ... (OEIS A004677 and A004824; Valtr 1995, p. 643; Valtr 1996), and

(10)

for a parallelogram, which has first few values 1, 1, 1, 25/36, 49/144, 49/400, 121/3600, ... (OEIS A004936 and A005017; Valtr 1995, p. 637; Peyerimhoff 1997).

Sylvester's four-point problem has an unexpected connection with the rectilinear crossing number of graphs (Finch 2003, pp. 532-533).