COVERING CONVEX RECTILINEAR POLYGONS IN LINEAR TIME
W. T. LIOU, Chuan Yi Tang, R.C.T. Lee · International Journal of Computational Geometry & Applications · 1991
In this paper, we discuss the problem of covering a convex rectilinear polygon with the minimum number of rectangles. The rectangles can overlap with each other. We show that this problem can be solved in linear time, which improves the previous O(n2) result proposed by Franzblau and Kleitman3. However, Franzblau and Kleitman's algorithm works for a larger class of polygons (vertically convex).