# How to fill a 2D set over a cartesian lattice with as few rectangles as possible?

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:

1. How can I fill the space with the FEWEST number of rectangles? (smallest data compression)
2. How can I find this optimal set of space-filling rectangles in polynomial time? (or is this problem NP-hard?)
• Why use rectangles? Why not simply store points along the boundary of the shape? – Joe Jan 12 '12 at 19:52
• I think you need to specify more about your problem. For example, a circle cannot be filled with a finite number of rectangles. – Dan Jan 12 '12 at 20:01
• A binary image consists of finite points, thus any shape can be filled with finite rectangles. Also, there are some shapes such that there are more boundary points than space-filling rectangles... – Paul Jan 13 '12 at 5:55
• @Paul, I have revised the title and text to make explicit your unstated assumptions. It's an interesting question! You might also try asking it on mathoverflow or CS (cstheory.stackexchange.com) – David Ketcheson Jan 13 '12 at 7:29
• There is a related (but different!) question here: cstheory.stackexchange.com/questions/9240/… – David Ketcheson Jan 13 '12 at 8:16

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.

Actually, I found the answer here . Thanks for the help though...

• Thanks for the reference. Apparently, I should have used the "cuts" as the nodes of the graph and the corners as the edges. Then it would have been more obvious that the graph is bipartite (x-"cuts" and "y-cuts"). (And of course, then the intersections between the "cuts" are also taken care of.) – Thomas Klimpel Jan 15 '12 at 23:17

The boundary of the domain has exactly two types of corners: convex 90 degree corners and concave 90 degree corners. For filling the domain with non-overlapping rectangles, only the concave corners are important. (I don't know how to upload pictures, sorry.) At each concave corner, we must have a "cut" in x- or y-direction. Each "cut" adds one rectangle, unless the "cut" happens to end in another concave corner.

EDIT Fixed the proposed solution based on the references given in the other answer.

Therefore, we define a bipartite graph with the axis-parallel "cuts" between concave corners as nodes. Two nodes are connected by an edge, if the corresponding "cuts" intersect each other, or have a common corner. A maximum independent set in this graph (a set of nodes with no edges between them) would translate into a solution of the original problem. Such a set can be derived from a maximum matching of the bipartite graph. (This is probably related to the Dulmage-Mendelsohn decomposition.)