Sylvester's four point problem

Sylvester's four point problem in geometric probability asks for the probability that four randomly chosen points in the Euclidean plane form a convex quadrilateral. Together with Buffon's needle problem, it has been called "one of the prime paradigms in geometric probability theory".^[1]

The answer depends on the probability distribution from which the points are drawn, and finding a distribution for which this probability is small is closely connected to the crossing number of complete graphs.^[2] The problem was posed in 1864 by J. J. Sylvester, who asserted (with fallacious reasoning) that if the points are drawn from the entire plane then the probability is ${\displaystyle {\tfrac {3}{4}}}$ but that if they are drawn from a bounded convex set then the probability is bounded below ${\displaystyle {\tfrac {3}{4}}}$.^[3] (Sylvester originally posed the problem in a complementary form, asking for the probability that four points do not form a convex quadrilateral, and giving answers ${\displaystyle {\tfrac {1}{4}}}$ and bounded above ${\displaystyle {\tfrac {1}{4}}}$.)^[1][3]

Among continuous uniform distributions over bounded convex sets the probability of a convex quadrilateral is maximized by any circle or ellipse (probability approximately 0.704) and minimized by any triangle (approximately 0.667). For uniform distributions over bounded open sets the minimum probability that can be achieved is unknown, but has upper and lower bounds that are both near 0.380.

Sylvester, and Arthur Cayley, presumed that three of the points could be taken as forming the largest-area triangle of the four triangles determined by the points. This assumption limits the fourth point to a larger similar triangle, the anticomplementary triangle of the first three points, with four times the area. The four points form a convex quadrilateral if the fourth point does not also lie within the triangle of the first three points. The fraction of area of the anticomplementary triangle in which a convex quadrilateral is formed is ${\displaystyle {\tfrac {3}{4}}}$. However, it is fallacious to use this reasoning to justify Sylvester's claim that the probability of obtaining a convex quadrilateral is ${\displaystyle {\tfrac {3}{4}}}$: there is no uniform distribution on the entire plane from which one can draw four points and apply this sort of area argument.^[3]

For four points chosen uniformly at random within a unit disk, the probability that they are in convex position is^[3] $${\displaystyle 1-{\frac {35}{12\pi ^{2}}}\approx 0.7045.}$$ This was calculated soon after Sylvester posed his problem by Wesley S. B. Woolhouse; Woolhouse then assumed (again, fallaciously) that the solution for the entire plane could be taken as a limit of disks with arbitrarily large radii, all having the same probability. The same probability applies to an ellipse. For points chosen uniformly at random from within a triangle, square, or regular hexagon (or their affine transformations, including the rectangles and parallelograms), the probabilities are respectively ${\displaystyle {\tfrac {2}{3}}\approx 0.6667}$, ${\displaystyle {\tfrac {11}{36}}\approx 0.6944}$, and ${\displaystyle {\tfrac {289}{972}}\approx 0.7027}$.^[3]

Among uniform distributions over convex shapes, the maximum probability of obtaining a convex quadrilateral is given by choosing random points in a disk, while the minimum probability is obtained by choosing points in a triangle.^[3] For points drawn from a two-dimensional Gaussian distribution, the probability of obtaining four points in convex position is^[1][4][5] $${\displaystyle {\frac {6}{\pi }}\arcsin {\frac {1}{3}}\approx 0.6490.}$$

Instead of considering a uniform distribution over a convex set, one can more generally consider the problem for uniform distributions over open sets of finite Lebesgue measure. For this problem, it is unknown which open set (or limiting sequence of open sets) provides the smallest probability of four points being in convex position.^[2] Maximizing this probability is not interesting: an open set obtained by thickening a convex curve gives probability close to one.

The problem of minimizing the probability of a convex quadrilateral is connected to the rectilinear crossing number of complete graphs, as follows. A complete graph is an undirected graph in which every pair of vertices form the endpoints of an edge. The rectilinear crossing number of a graph is the minimum number of crossings that can be obtained in a graph drawing with the vertices drawn as points in the plane, the edges drawn as straight line segments, and two edges having an intersection only at a shared endpoint of the edges or at point where only those two edges cross. If there exists an open set for which the probability of forming a convex quadrilateral is ${\displaystyle \kappa }$, then drawing ${\displaystyle n}$ random points from this set and using these as the vertices as a drawing produces an expected number of crossings equal to ${\displaystyle \kappa {\tbinom {n}{4}}}$: each four-tuple of vertices produces either a single crossing (when it is in convex position) or no crossings (otherwise), and by linearity of expectation the expected number of crossings equals the sum of the probabilities of each four-tuple having a crossing.^[2]

In the other direction if a complete graph on ${\displaystyle n}$ vertices can be drawn with ${\displaystyle \kappa {\tbinom {n}{4}}}$ crossings, then there exists an open set whose probability of four points forming a convex quadrilateral is ${\displaystyle \kappa +O({\tfrac {1}{n}})}$, constructed from the drawing by replacing each vertex with a small disk. For four-tuples of points drawn from four distinct disks, the probability of forming a convex quadrilateral is exactly ${\displaystyle \kappa }$, and the probability of drawing two of the points from the same disk is ${\displaystyle O({\tfrac {1}{n}})}$. It follows from these conversions between the two problems that the limiting constant factor for the rectilinear crossing number of the complete graph (the limit of ${\displaystyle \kappa }$ as ${\displaystyle n}$ goes to infinity) and the limiting probability for Sylvester's four point problem (the infimum of probabilities ${\displaystyle \kappa }$ over arbitrary open sets of bounded Lebesgue measure) are equal.^[2] More generally the same equivalence holds for Sylvester's four point problem for Borel measures on open subsets of the plane.

Through subsequent research and computational searches the limiting value of ${\displaystyle \kappa }$ (equivalently for both Sylvester's problem and the rectilinear crossing number) is known to have the upper and lower bounds^[6][7][8][9] $${\displaystyle 0.37968\leq \kappa \leq 0.38045.}$$

The problem has been generalized to ask about the probability that ${\displaystyle n}$ random points in ${\displaystyle d}$-dimensional space, drawn uniformly at random from a convex body, lie in convex position,^{[3][10][11][12][13]} as well as to higher-dimensional Gaussian distributions.^[5]