Chadha, Ritu2019-07-032019-07-031987http://hdl.handle.net/10919/90962This 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.ix, 116 leavesapplication/pdfen-USIn CopyrightLD5655.V855 1987.C523Decomposition (Mathematics)Thesis