# DIMACS Focus on Discrete Probability Seminar

## Title:

On the Probability that n Random Points are in Convex Position

## Speaker:

- 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.

Document last modified on September 23, 1996