Sylvester's four-point problem asks for the probability that four points chosen at random in a planar region
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 points selected from an open, convex subset of the plane
having finite area, the probability is given by
()
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).
Sylvester's problem can be generalized to ask for the probability that the convex hull of randomly chosen points in the unit
ball
has
vertices. The solution is given by
(3)
(Kingman 1969, Groemer 1973, Peyerimhoff 1997), which is the maximum possible for any bounded convex domain . The first few values are
Another generalization asks the probability that randomly chosen points in a fixed bounded convex
domain are the vertices of a convex -gon. The solution is
(9)
for a triangular domain, which has first few values 1, 1, 1, 2/3, 11/36, 91/900, 17/675, ... (OEIS A004677 and A004824),
and
(10)
for a parallelogram domain, which has first few values 1, 1, 1, 25/36, 49/144, 121/3600, ... (OEIS A004936 and A005017;
Valtr 1996, Peyerimhoff 1997).
Sylvester's four-point problem has an unexpected connection with the rectilinear
crossing number of graphs (Finch 2003).
Alikoski, H. A. "Über das Sylvestersche Vierpunktproblem." Ann. Acad. Sci. Fenn.51, No. 7, 1-10, 1939.Blaschke,
W. "Über affine Geometrie XI: Lösung des 'Vierpunktproblems' von Sylvester
aus der Theorie der geometrischen Wahrscheinlichkeiten." Ber. Verh. Sachs.
Akad. Wiss. Leipzig Math.-Phys. Kl.69, 436-453, 1917.Blaschke,
W. §24-25 in Vorlesungen über Differentialgeometrie, II. Affine Differentialgeometrie.
Berlin: Springer-Verlag, 1923.Croft, H. T.; Falconer, K. J.;
and Guy, R. K. "Random Polygons and Polyhedra." §B5 in Unsolved
Problems in Geometry. New York: Springer-Verlag, pp. 54-57, 1991.Crofton,
M. W. "Probability." Encyclopedia Britannica, Vol. 19, 9th
ed. pp. 768-788, 1885.Efron, B. "The Convex Hull of a
Random Set of Points." Biometrika52, 331-343, 1965.Finch,
S. R. "Rectilinear Crossing Constant." §8.18 in Mathematical
Constants. Cambridge, England: Cambridge University Press, pp. 532-534,
2003.Groemer, H. "On Some Mean Values Associated with a Randomly
Selected Simlpex in a Convex Set." Pacific J. Math.45, 525-533,
1973.Kendall, M. G. and Moran, P. A. P. Geometrical
Probability. New York: Hafner, 1963.Kingman, J. F. C.
"Random Secants of a Convex Body." J. Appl. Prob.6, 660-672,
1969.Klee, V. "What is the Expected Volume of a Simplex Whose Vertices
are Chosen at Random from a Given Convex Body." Amer. Math. Monthly76,
286-288, 1969.Peyerimhoff, N. "Areas and Intersections in Convex
Domains." Amer. Math. Monthly104, 697-704, 1997.Pfiefer,
R. E. "The Historical Development of J. J. Sylvester's Four Point
Problem." Math. Mag.62, 309-317, 1989.Rottenberg,
R. R. "On Finite Sets of Points in ." Israel J. Math.10, 160-171, 1971.Santaló,
L. A. Integral
Geometry and Geometric Probability. Reading, MA: Addison-Wesley, 1976.Scheinerman,
E. and Wilf, H. S. "The Rectilinear Crossing Number of a Complete Graph
and Sylvester's 'Four Point' Problem of Geometric Probability." Amer. Math.
Monthly101, 939-943, 1994.Sloane, N. J. A. Sequences
A004677, A004824,
A004936, A005017,
A051050, and A051051
in "The On-Line Encyclopedia of Integer Sequences."Solomon,
H. "Crofton's Theorem and Sylvester's Problem in Two and Three Dimensions."
Ch. 5 in Geometric
Probability. Philadelphia, PA: SIAM, pp. 97-125, 1978.Sylvester,
J. J. "Question 1491." The Educational Times (London). April
1864.Sylvester, J. J. "On a Special Class of Questions on
the Theory of Probabilities." Birmingham British Assoc. Rept., pp. 8-9,
1865.Valtr, P. "Probability that Random Points are in a Convex Position." Discrete
Comput. Geom.13, 637-643, 1995.Valtr, P. "The Probability
that
Random Points in a Triangle are in Convex Position." Combinatorica16,
567-573, 1996.Weil, W. and Wieacker, J. "Stochastic Geometry."
Ch. 5.2 in Handbook
of Convex Geometry (Ed. P. M. Gruber and J. M. Wills).
Amsterdam, Netherlands: North-Holland, pp. 1391-1438, 1993.Wilf,
H. "On Crossing Numbers, and Some Unsolved Problems." In Combinatorics,
Geometry, and Probability: A Tribute to Paul Erdős. Papers from the Conference
in Honor of Erdős' 80th Birthday Held at Trinity College, Cambridge, March 1993
(Ed. B. Bollobás and A. Thomason). Cambridge, England: Cambridge
University Press, pp. 557-562, 1997.Woolhouse, W. S. B.
"Some Additional Observations on the Four-Point Problem." Mathematical
Questions, with Their Solutions, from the Educational Times, Vol. 7. London:
F. Hodgson and Son, p. 81, 1867.