Polygon partition

The problem of minimizing the number of component rectangles is polynomial: several polynomial-time algorithms are known. See [1]^: 10–13 and [2]^: 3–5 for surveys.

The problem of partitioning a rectilinear polygon to a smallest number of squares (in contrast to arbitrary rectangles) is NP-hard.[3]

In some applications, it is more important to minimize the total length of the cuts (e.g. to minimize the cost of performing the partition, or to minimize the amount of dust). This problem is called minimum edge-length rectangular partitioning. It was first studied by Lingas, Pinter, Rivest and Shamir in 1982.[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 ${\displaystyle O(n^{4})}$, where n is the number of vertices of the polygon. In the special case of a "histogram polygon", the complexity improves to ${\displaystyle O(n^{3})}$.[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. Therefore, there are only ${\displaystyle O(n^{2})}$ candidates for a line segment in an optimal partition, and they can be checked efficiently using dynamic programming.[5]^{: 166–167}

If the raw polygon might have holes, even if they are degenerate holes (i.e., single points), the problem is NP-hard. This can be proved by reduction from Planar SAT.[4][6] For the case in which all holes are single points, several constant-factor approximations have been developed:

• A (3+sqrt(3)) approximation in time ${\displaystyle O(n^{2})}$;[6]
• A (3+sqrt(3)) approximation in time ${\displaystyle O(n\log {n})}$;[7]
• A 4 approximation in time ${\displaystyle O(n\log {n})}$ (more generally, in d dimensions, it is a ${\displaystyle 2d}$ approximation in time ${\displaystyle O(dn\log {n})}$),[8]
• A 3 approximation in time ${\displaystyle O(n^{4})}$;
• A 1.75 approximation in time ${\displaystyle O(n^{5})}$ (more generally, in d dimensions, it is a ${\displaystyle 2d-4+4/d}$ approximation in time ${\displaystyle O(dn^{2d+1})}$);[9] the latter approximation uses a restricted variant of the problem called guillotine partitioning, in which the cuts must be guillotine cuts (edge-to-edge cuts).
• Several polynomial-time approximation schemes using sophisticated guillotine cuts.[10][11][5]

In this setting, the large polygon already contains some pairwise-disjoint rectangles. The goal is to find a partition of the polygon into rectangles such that each original rectangle is contained in one of the pieces, and subject to this, the number of "blanks" (pieces that do not contain an original rectangle) is as small as possible. The following results are known:[12]

• If the large polygon is a rectangle, then in any maximal arrangement of n rectangles, all the holes are rectangles, and their number is at most ${\displaystyle n-\lceil 2{\sqrt {n}}-1\rceil }$, and this is tight.
• If the large polygon is a rectilinear polygon with T reflex vertices, then in any maximal arrangement of n rectangles, the holes can be partitioned into at most ${\displaystyle T+n-\lceil 2{\sqrt {n}}-1\rceil }$ rectangles, and this is tight.

The optimal convex partitioning problem is to partition a non-convex polygon into as few as possible convex polygons, using only the initial polygon's vertices. There are exact and approximate algorithms for this problem.[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. If the large polygon is convex, then in any maximal arrangement of n convex figures, all the holes are convex, and their number is at most ${\displaystyle 2n-5}$, and this is tight.[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). Any convex polygon can be easily cut into any number n of convex pieces with an area of exactly 1/n. However, ensuring that the pieces have both equal area and equal perimeter is more challenging. There are algorithms for solving this problem when the number of pieces is a power of 2.[21]

A generalization of this problem is when the area and perimeter measures are replaced with a measure on the body and on the boundary of the polygon, respectively. This problem was studied for 2 and 3 pieces.[22]

There is a further generalization to handle any number of measures.