# filling an occluded plane with the smallest number of rectangles

I’ve got a specific problem which I’ll try to describe as clearly as possible.

I have a defined rectangular region on a cartesian plane, and within that region there are other given rectangular sub-regions that are described in terms of their 4 vertices, ie {(x1, y1), (x1, y2), (x2, y1), (x2, y2)}, so that these regions form ‘occlusions’ on the plane. These regions don’t overlap, but they can form more complex polygons when different-sized rectangles adjacent to each other appear joined.

here’s an illustration:

I am interested in the space between these shapes, and how to define the space in the same way the occlusions are defined, that is as a set of rectangles. In particular I want the definition optimised so that the space is described using the smallest possible number of rectangles. For example, an incomplete rendering might look like this:

Can anyone suggest a way forward with this? How can I have the original set of vertices (describing the black rectangles) generate the ‘complementary’ set of vertices (red rectangles) such that the number of red rectangles is minimal?

I suspect it’s a variation of a ‘packing problem’, but I have a feeling it might be fairly simple…

#### Solutions Collecting From Web of "filling an occluded plane with the smallest number of rectangles"

This problem has been studied in the 1980’s. You can find it named the problem of finding
a minimum rectangle partition of an orthogonal polygon with holes. In the older literature, sometimes “orthogonal” is replaced with “rectilinear.” If you wrap your black rectangles with the minimum bounding box, then you have converted it to an orthogonal polygon with holes.

I believe the first result was by Lipsky in 1979, but I am not finding that
paper. Here is a somewhat later paper:

“Partitioning rectilinear figures into rectangles.” 1988. (ACM link)

Although many problems superficially analogous to this are NP-hard,
this rectangle-partition problem can be solved in
$O(n^{5/2})$ time for a polygon of $n$ vertices in total.
The algorithms depend on finding a maximum independent set of the
intersection graph of certain chords in the polygon.

(Added 8Jul14): In response to Rahul’s queries, I point out in the comments that for
a simple orthogonal polygon (without holes), the minimum rectangle
partition can be found in $O(n \log \log n)$ time.