A randomized algorithm for triangulating a simple polygon

decomposition of a simple polygon. The expected running time of the
algorithm is linear in the size of the polygon. From the trapezoidal
decomposition, a triangulation of the polygon can be obtained in linear
time, using a well-known procedure. Our algorithm is simpler than
Chazelle's (1991) celebrated optimal deterministic algorithm.

Joint work with Nancy M. Amato and Michael T. Goodrich