Covering Regions by Rectangles
Authors:
- Seth ChaikenSCSeth Chaiken
- Daniel J. KleitmanDKDaniel J. Kleitman
- Michael SaksMSMichael Saks
- James ShearerJSJames Shearer
- 1 December 1981
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Algebraic Discrete Methods
- Vol. 2 (4) , 394-410
Abstract
A board$\mathcal{B}$ is a finite set of unit squares lying in the plane whose corners have integer coordinates. A rectangle of $\mathcal{B}$ is a rectangular subset of $\mathcal{B}$ and an antirectangle is a set of squares in $\mathcal{B}$ no two of which are in a common rectangle. We prove a conjecture of Chvátal that $\mathcal{B}$ if is convex in the horizontal and vertical directions, then the minimum number of rectangles whose union is $\mathcal{B}$ 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 hypotheses, and give some conjectures and open questions. The method of proof can give a polynomial running time algorithm for finding a minimum cover.