In calculus, when estimating a area of a set in a 2-dimensional space, we use rectangles to approximate. To get sufficient precision, how many rectangles are needed if the shape of the set is close to a rectangle? I formalize the discrete version of the problem as follows.

Suppose we have a $N\times N$ grid (I assume it is a $N$ rows of squares, each row contains $N$ squares), and a set, say $S$, contains at least $r N^2$ squares, $r<1$. Now we wanna cover $S$ using rectangles approximately. (Pick several rows and several columns, all the crossing squares form a retangle) The requirements are

1. all rectangles are disjoint with each other.

2. The number of misplaced squares (i.e. the squares outside $S$ but covered and the squares in $S$ but not covered) $\leq\epsilon |S|$, where $\epsilon$ is considered to be a small positive constant. Question is how many rectangles are sufficient.

My guess is $poly(\frac{1}{r})$.

In calculus, when estimating a area of a set in a 2-dimensional space, we use rectangles to approximate. To get sufficient precision, how many rectangles are needed if the shape of the set is close to a rectangle? I formalize the discrete version of the problem as follows.

Suppose we have a $N\times N$ grid (I assume it is a $N$ rows of squares, each row contains $N$ squares), and a set, say $S$, contains at least $r N^2$ squares, $r<1$. Now we wanna cover $S$ using rectangles approximately. Here retangle is defined in this way. Pick several rows, maybe not contiguous, and several columns, maybe not contiguous either, all the squares in crossing form a square. For instance, all the black squares in chessboard consist of two disjoint rectangles.

The requirements are

1. all rectangles are disjoint with each other.

2. The number of misplaced squares (i.e. the squares outside $S$ but covered and the squares in $S$ but not covered) $\leq\epsilon |S|$, where $\epsilon$ is considered to be a small positive constant. Question is how many rectangles are sufficient.

My guess is $poly(\frac{1}{r})$.