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

  • $\begingroup$ Is the disjointness of rectangles crucial? Allowing overlaps seems to broaden the applicability substantially, while not necessarily changing the answer. $\endgroup$ Nov 11, 2011 at 11:53
  • 1
    $\begingroup$ Your definition of rectangle is also not completely clear. Are you saying that the black squares on a chessboard can be covered by two rectangles? $\endgroup$ Nov 11, 2011 at 12:25
  • 2
    $\begingroup$ Simultaneously cross-posted to MO: mathoverflow.net/questions/80665/… $\endgroup$ Nov 11, 2011 at 12:59
  • $\begingroup$ will the problem be easier when allowing overlap? About the rectangle, yes, the black squares are covered by two rectangles $\endgroup$
    – pyao
    Nov 11, 2011 at 15:04
  • 1
    $\begingroup$ It appears that you have crossposted this question simultaneously. While we don't mind a question being reposted, our site policy is to permit a repost only after sufficient time has passed and you did not obtain the desired answer elsewhere, because simultaneous crossposting duplicates effort and fractures discussion. You may flag this question for closing now, and then reflag it for opening if necessary after adding relevant information from discussion on the other sites. $\endgroup$ Nov 11, 2011 at 16:22


Browse other questions tagged or ask your own question.