A fast Las Vegas algorithm for triangulating a simple polygon
Kenneth L. Clarkson, Robert Endre Tarjan, Christopher J. Van Wyk · 1988
We present an algorithm that triangulates a simple polygon on n vertices in Ο(n log* n) expected time. The algorithm uses random sampling on the input, and its running time does not depend on any assumptions about a probability distribution from which the polygon is drawn.