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?)