Polygon partitioning is an important class of problems in computational geometry.
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.
In this case, the most important component shape to consider is the rectangle.
In VLSI design, it is necessary to decompose masks into the simpler shapes available in lithographic pattern generators, and similar mask decomposition problems also arise in DNA microarray design.
Closely related matrix decomposition problems have been applied to radiation therapy planning, and rectangular partitions have also been used to design robot self-assembly sequences.
[2] The problem of minimizing the number of component rectangles is polynomial: several polynomial-time algorithms are known.
The problem of partitioning a rectilinear polygon to a smallest number of squares (in contrast to arbitrary rectangles) is NP-hard.
[4][5] The run-time complexity of this problem crucially depends on whether the raw polygon is allowed to have holes.
If the raw polygon is hole-free, then an optimal partition can be found in time
In the special case of a "histogram polygon", the complexity improves to
[4] The algorithm uses dynamic programming and relies on the following fact: if the polygon is hole-free, then it has a minimum-length partition in which each maximal line-segment contains a vertex of the boundary.
The reason is that, in any minimum-length partition, every maximal line-segment can be "pushed" until it hits one of the vertices of the boundary, without changing the total length.
candidates for a line segment in an optimal partition, and they can be checked efficiently using dynamic programming.
[4][6] For the case in which all holes are single points, several constant-factor approximations have been developed: In this setting, the large polygon already contains some pairwise-disjoint rectangles.
The following results are known:[12] In VLSI artwork processing systems, it is often required to partition a polygonal region into the minimum number of trapezoids, with two horizontal sides.
[14] If the polygon does contain holes, the problem is NP-complete, but a 3-approximation can be found in time
There are linear-time algorithms for quadrangulations of hole-free polygons with Steiner points, but they are not guaranteed to find a smallest partition.
[19] The original polygon already contains some pairwise-disjoint convex figures, and the goal is to partition it into convex polygons that such that each original figure is contained in one of the pieces, and subject to this, the number of "blanks" (pieces that do not contain an original figure) is as small as possible.
[12] The fair polygon partitioning problem[20] is to partition a (convex) polygon into (convex) pieces with an equal perimeter and equal area (this is a special case of fair cake-cutting).