Minimum dissection of a rectilinear polygon with arbitrary holes into rectangles
The authors give a formula for a minimum number of dissecting rectangles for a given rectangular polygon with arbitrary (possibly, degenerate) holes. They also give a polynomial time algorithm for dissecting the polygon in a minimum number of rectangles. The holes can degenerate into points. This fact disproves an assertion about the \(NP\)-hardness of this problem.
scientific article; zbMATH DE number 78493
scientific article