In geometry, a partition of a polygon is a set of primitive units (e.g., triangles, rectangles, etc.), which do not overlap and whose union equals the polygon. A polygon partition problem is a problem of finding a partition which is minimal in some sense, for example a partition with a smallest number of units or with units of smallest total side-length (sum of the perimeters).

Polygon partitioning 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.

The term "polygon decomposition" is often used as a general term that includes both polygon partitioning and polygon covering, which allows overlapping units.

Polygon decomposition is applied in several areas:

The most well-studied polygon partition problem is partitioning to a smallest number of triangles, also called triangulation. For a hole-free polygon with ${\displaystyle n}$ vertices, a triangulation can be calculated in time ${\displaystyle \Theta (n)}$. For a polygon with holes, there is a lower bound of ${\displaystyle \Omega (n\log n)}$.

A related problem is partitioning to triangles with a minimal total edge length, also called minimum-weight triangulation.

The same two variants of the problem were studied for the case in which the pieces should be pseudotriangles – polygons that like triangles have exactly three convex vertices. The variants are: partitioning to a smallest number of pseudotriangles, and partitioning to pseudotriangles with a minimal total edge length.

An important sub-family of polygon partition problems arises when the large polygon is a rectilinear polygon, and the goal is to partition it into rectangles. Such partitions are known as rectangular partitions. They have practical applications in a variety of fields, including VLSI design and image processing.