TOPICS
Search

Sylvester's Four-Point Problem


SylvestersFourPoints

Sylvester's four-point problem asks for the probability q(R) that four points chosen at random in a planar region R 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

 P(R)=1-(4A^__R)/(A(R)),
(1)

where A^__R is the expected area of a triangle over region R and A(R) is the area of region R (Efron 1965). Note that A^__R is simply the value computed for an appropriate region, e.g., disk triangle picking, triangle triangle picking, square triangle picking, etc., where A_R can be computed exactly for polygon triangle picking using Alikoski's formula.

P(R) can range between

 2/3<=q(R)<=1-(35)/(12pi^2)
(2)

(0.66666<=q(R)<=0.70448) 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).

RP(R)approx.
triangle2/30.66667
square(25)/(36)0.69444
pentagon2/(45)(18-sqrt(5))0.70062
hexagon(683)/(972)0.70267
ellipse, disk1-(35)/(12pi^2)0.70448

Sylvester's problem can be generalized to ask for the probability that the convex hull of n+2 randomly chosen points in the unit ball B^n has n+1 vertices. The solution is given by

 P_n=((n+2)(n+1; 1/2(n+1))^(n+1))/(2^n((n+1)^2; 1/2(n+1)^2))
(3)

(Kingman 1969, Groemer 1973, Peyerimhoff 1997), which is the maximum possible for any bounded convex domain K in R^n. The first few values are

P_1=1
(4)
P_2=(35)/(12pi^2)
(5)
P_3=9/(143)
(6)
P_4=(676039)/(648000pi^4)
(7)
P_5=(20000)/(12964479)
(8)

(OEIS A051050 and A051051).

Another generalization asks the probability that n randomly chosen points in a fixed bounded convex domain K subset R^2 are the vertices of a convex n-gon. The solution is

 P_n=(2^n(3n-3)!)/([(n-1)!]^3(2n)!)
(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

 P_n=[1/(n!)(2n-2; n-1)]^2
(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).


See also

Disk Triangle Picking, Hexagon Triangle Picking, Polygon Triangle Picking, Rectilinear Crossing Number, Square Triangle Picking, Triangle Triangle Picking

Explore with Wolfram|Alpha

References

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." Biometrika 52, 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. Monthly 76, 286-288, 1969.Peyerimhoff, N. "Areas and Intersections in Convex Domains." Amer. Math. Monthly 104, 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 P^3." 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. Monthly 101, 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 n Random Points are in a Convex Position." Discrete Comput. Geom. 13, 637-643, 1995.Valtr, P. "The Probability that n Random Points in a Triangle are in Convex Position." Combinatorica 16, 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.

Referenced on Wolfram|Alpha

Sylvester's Four-Point Problem

Cite this as:

Weisstein, Eric W. "Sylvester's Four-Point Problem." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/SylvestersFour-PointProblem.html

Subject classifications