	The most well-studied polygon partition problem is partitioning to a smallest number of triangles, also called triangulation. For a hole-free polygon with formula_1 vertices, a triangulation can be calculated in time formula_2. For a polygon with holes, there is a lower bound of formula_3.