Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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

share|improve this question
    
Is the disjointness of rectangles crucial? Allowing overlaps seems to broaden the applicability substantially, while not necessarily changing the answer. –  András Salamon Nov 11 '11 at 11:53
1  
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? –  András Salamon Nov 11 '11 at 12:25
2  
Simultaneously cross-posted to MO: mathoverflow.net/questions/80665/… –  András Salamon Nov 11 '11 at 12:59
    
will the problem be easier when allowing overlap? About the rectangle, yes, the black squares are covered by two rectangles –  pyao Nov 11 '11 at 15:04
1  
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. –  Suresh Venkat Nov 11 '11 at 16:22
show 1 more comment

closed as off topic by Tsuyoshi Ito, Suresh Venkat Nov 11 '11 at 16:22

Questions on Theoretical Computer Science Stack Exchange are expected to relate to research-level theoretical computer science within the scope defined by the community. Consider editing the question or leaving comments for improvement if you believe the question can be reworded to fit within the scope. Read more about reopening questions here.If this question can be reworded to fit the rules in the help center, please edit the question.