This web page contains the abstract of my paper:
"Covering Regions with Rectangles" with S. Chaiken, D.J. Kleitman and M. Saks, SIAM J. Alg. and Disc. Meth., 2(1981), p. 394-410.
Abstract: A board R is a finite set of unit squares lying in the plane whose corners have integer coordinates. A rectangle of R is a rectangular subset of R and an antirectangle is a set of squares of R no two of which are in a common rectangle. We prove a conjecture of Chvatal that if R is convex in the horizontal and vertical directions, then the minimum number of rectangles whose union is R equals the maximum cardinality of an antirectangle. Our proof uses two analogous minimax theorems about covering the corners and covering the edges of the board.
We quote examples that illustrate the necessity of the hypothesis, and give some conjectures and open questions. The method of proof can give a polynomial running time algorithm for finding a minimum cover.
IBM Research home page |
James B. Shearer's home page |
[ IBM home page | Order | Search | Contact IBM | Help | (C) | (TM) ]