Complexities of Efficient Solutions of Rectilinear Polygon Cover Problems

The rectilinear polygon cover problem is one in which a certain class of features of a rectilinear polygon of n vertices has to be covered with the minimum number of rectangles included in the polygon. In particular, we consider covering the entire interior, the boundary, and the set of corners of the polygon. These problems have important applications in storing images and in the manufacture of integrated circuits. Unfortunately, most of these problems are known to be NP-complete. Hence it is necessary to develop efficient heuristics for these problems or to show that the design of efficient heuristics is impossible. In this paper we show: (a) The corner cover problem is NP-complete. (b) The boundary and the corner cover problem can be approximated within a ratio of 4 of the optimum in O(n logn) and O(n1.5) time, respectively. (c) No polynomial-time approximation scheme exists for the interior and the boundary cover problems, unless P = NP.