In computational geometry, polygon triangulation is the decomposition of a polygonal area (simple polygon) P into a set of triangles, i.e., finding the set of triangles with pairwise non-intersecting interiors whose union is P.
In the strict sense, these triangles may have vertices only at the vertices of P. In a less strict sense, points can be added anywhere on or inside the polygon to serve as vertices of triangles. In addition, the cases of triangulation of a simple polygon and of a polygonal area with polygonal holes are treated separately.
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.