Triangulating a Simple Polygon in Linear Time

Abstract:

We give a deterministic algorithm for triangulating a simple polygon in linear time. The basic strategy is to build a coarse approximation of a triangulation in a bottom-up phase and then use the information computed along the way to refine the triangulation in a top-down phase. The main tools used are (i)
the polygon-cutting theorem, which provides us with a balancing scheme, and (ii) the planar separator theorem, whose role is essential in the discovery of new diagonals. Only elementary data structures are required by the algorithm. In particular, no dynamic search trees, finger trees, or point location
structures are needed. We mention a few applications of our algorithm.