A linear-time algorithm for triangulating simple polygons
Robert Endre Tarjan, Christopher J. Van Wyk · 1986
A simple polygon with n vertices is triangulated by adding to it n-3 line segments between its vertices that partition the interior of the polygon into triangles.We present an algorithm for triangulating a simple polygon in time proportional to its size.This result has a number of applications in computational geometry.