Close approximations of minimum rectangular coverings

We consider the problem of covering arbitrary polygons with rectangles. The rectangles must lie entirely within the polygon. (This requires that the i nterior angles of the polygon are all greater than or equal to 90 degrees.) We want to cover the polygon with as few rectangles as possible. This prob lem has an application in fabricating masks for integrated circuits. In this paper we will describe the first polynomial algorithm, guaranteeing an O(log n) approximation factor, provided that the n vertices of the inpu t polygon are given as polynomially bounded integer coordinates. By the sam e technique we also obtain the first algorithm producing a covering which i s within a constant factor of the optimal in exponential time (compared to the doubly-exponential known before).