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.