Polygon triangulation
In computational geometry, polygon triangulation is the decomposition of a polygonal area (simple polygon) P into a set of triangles, i.e., finding a set of triangles with pairwise non-intersecting interiors whose union is P.
Triangulations may be viewed as special cases of planar straight-line graphs. When there are no holes or added points, triangulations form maximal outerplanar graphs.
Over time a number of algorithms have been proposed to triangulate a polygon.
A convex polygon is trivial to triangulate in linear time, by adding diagonals from one vertex to all other vertices. The total number of ways to triangulate a convex n-gon by non-intersecting diagonals is the (n − 2)-th Catalan number, which equals , a solution found by Leonhard Euler.
A monotone polygon can be triangulated in linear time with either the algorithm of A. Fournier and D.Y. Montuno, or the algorithm of Godfried Toussaint.
...
Wikipedia