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.

A report for PC tree

The beta version of the PC tree report is finished. The topic is "PC tree and its application". This report first discuss the use of PC tree for testing consecutive-ones property of a 0-1 matrix. Then discuss its further application on interval graph recognition and planarity testing.

However, I start writing terribly when describing the application. If you don't understand what they are talking about, please feel free to ask me, I will fix it asap, but not today XD

PC tree and its application