Polygon partition

A partition of a polygon is a set of primitive units (e.g. squares), which do not overlap and whose union equals the polygon. A polygon partition problem is a problem of finding a partition with a smallest number of units for a given polygon. This is an important class of problems in computational geometry. There are many different polygon partition problems, depending on the type of polygon being partitioned and on the types of units allowed in the partition. An example polygon partition problem is: given a rectilinear polygon, find a smallest set of non-overlapping squares whose union equals the polygon.

In a partition problem, the units must be disjoint and their union must exactly equal the target polygon. This is in contrast to a packing problem, in which the units must be disjoint and their union may be smaller than the target polygon, and to a covering problem, in which the units may overlap as long as their union must be equal to the target polygon.