DIMACS Focus on Discrete Probability Seminar

Title:

On the Probability that n Random Points are in Convex Position

Pavel Valtr
DIMACS

Place:

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

Time:

3:30 PM
Thursday, October 24, 1996
Abstract:

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.

dimacs-www@dimacs.rutgers.edu