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})$.