DIMACS Focus on Discrete Probability Seminar


On the Probability that n Random Points are in Convex Position


Pavel Valtr


CoRE 305B, CoRE Building,
Busch Campus, Rutgers University.


3:30 PM
Thursday, October 24, 1996

A finite set of points in the plane is called convex if its points are vertices of a convex polygon. We show that n random points chosen independently and uniformly from a parallelogram are in convex position with probability $$\left( {{2n-2\choose n-1}\over n!} \right)^2.$$ Surprisingly, this expression can be easily expressed by the Catalan numbers. We also find a closed fomulae for the above probability when parallelogram is replaced by a triangle. The proofs are combinatorial, and they give a theoretical background for a fast algorithm which finds a random n-point convex set.

Document last modified on September 23, 1996