Decomposing rectilinear regions into rectangles
Ritu Chadha · VTechWorks (Virginia Tech) · 1987
This thesis discusses the problem of decomposing rectilinear regions, with or without holes, into a minimum number of rectangles. There are two different types of decomposition considered here : decomposing a figure into non-overlapping parts, called partitioning, and decomposing a figure into possibly overlapping parts, called covering. A method is outlined and proved for solving the above two problems, and algorithms for the solutions of these problems are presented. The partitioning problem can be solved in time O(n⁵ ²), where n is the number of vertices of the figure, whereas the covering problem is exponential in its time complexity.