I have a 𝑛×𝑚 rectangular grid of cells, and a set 𝑅 of rectangles within this grid. Each rectangle is a subset of the cells. (Alternatively, you can think of them as axis-aligned rectangles where each of the four corners has integer coordinates.) Some of these rectangles overlap and some of these rectangles are adjacent. I want to merge adjacent rectangles to bigger rectangles if possible and remove overlaps.
So my output set should have bigger non overlapping rectangles instead of small adjacent or overlapping rectangles. The number of rectangles in the output set should be minimized. The output set need not be a subset of input set. Is there any approximate or exact algorithm for this problem?