Covering Rectilinear Polygons by Rectangles

Covering Rectilinear Polygons by Rectangles is a category of problems, the general definition of the problem: A board B is a finite set of unit squares lying in the plane whose corners have integer coordinates. A rectangle of B is a rectangular subset of B. A rectangle cover of B is a collection of rectangles whose union equals B.The rectangles of a cover may overlap, but each of them must be wholly contained in the board.

This problem obviously is NP-Complete, I am still thinking of the proof. The first idea come up is that it is finding maximal cliques on the graph G(B), G(B) is a graph whose nodes represent squares in B. Two square u, v are adjacent in G if Rec(u, v) in B. The other similar NP-complete problem to rectangle covering, is set cover problem.

There are some specialized problems. For example, the given board B must be convex and no hole inside the board.

Since the problem is NP-complete problem, most of the attention is focus on the approximability of the problem. Erdos asked if Theta / Alpha [1] is bounded, but it still cannot be proved yet.

This problem is quite interesting and applicable, one of its application is an operation used by microelectronics industry. A layer of an integrated circuit is to be printed on a photographic plate. The printing is done by flashing rectangles onto the plate and as few rectangles as possible.

[1] Theta is the rectangle of B; Alpha is anti-rectangle of B, ie. a set of squares in B that no two of which are contained in any rectangle.