Suppose I have a black and white image (composed of binary pixel values in a 2D cartesian array) that contains an irregular, nonconvex shape.  Let's further suppose that the shape is one connected region.  Instead of storing each individual pixel location (which may be too costly for very large images), I want to represent the exact same image as a set of 'space-filling' rectangles.  In doing so, each rectangle can be represented by its two antipodal corner points. Thus, there is no need to store information about each point inside the rectangle: we only need to store the matrix coordinates $(i,j)$ of the two opposite corner points.There are many ways that one can fill the space with rectangles.  So, my question is:How can I fill the space with the FEWEST number of rectangles? (smallest data compression)How can I find this optimal set of space-filling rectangles in polynomial time? (or is this problem NP-hard?)
How to fill a 2D set over a cartesian lattice with as few rectangles as possible?
optimization;geometry;data handling
I hadn't thought about it too closely, but I think the basic algorithm would work like this:Find the number of unique edges in either the $x$ or $y$ directions. Take the direction that has the smaller number of edges. Without loss of generality, we assume $x$ here.For each such edge, connecting $(x_{min},y_1)$ to $(x_{min},y_2)$, draw the largest possible rectangle, extending to terminate at the line $x = x_{max}$.Repeat this process for all edges on the other side (e.g., move rightwards) that have not yet been covered with a rectangle.This should cover the whole domain, but with the possibility of overlaps as one starts from either the left or the right. However, the number of unique edges in either the $x$ or $y$ direction acts as an upper bound on the number of rectangles. 