<p>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.</p>

<p>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&lt;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</p>

<p>1) all rectangles are disjoint with each other.</p>

<p>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. </p>

<p>My guess is $poly(\frac{1}{r})$.</p>

CC BY-SA 3.0
2011-11-11T11:53:51.150Z
Is the disjointness of rectangles crucial?  Allowing overlaps seems to broaden the applicability substantially, while not necessarily changing the answer.
András Salamon
CC BY-SA 3.0
2011-11-11T12:25:22.530Z
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
CC BY-SA 3.0
2011-11-11T12:59:42.503Z
Simultaneously cross-posted to MO: http://mathoverflow.net/questions/80665/how-to-cover-a-set-in-a-grid-with-as-few-rectangles-as-possible
András Salamon
CC BY-SA 3.0
2011-11-11T15:04:57.783Z
will the problem be easier when allowing overlap?  About the rectangle,  yes, the black squares are covered by two rectangles
pyao
CC BY-SA 3.0
2011-11-11T16:11:28.323Z
Voted to close to avoid duplicate effort.
Tsuyoshi Ito
CC BY-SA 3.0
2011-11-11T16:22:09.900Z
It appears that you have crossposted this question *simultaneously*. While we don't mind a question being **reposted**, our [site policy](http://meta.cstheory.stackexchange.com/questions/225/official-faq-for-theoretical-computer-science/231#231) 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
<co.combinatorics><approximation>
how to cover a set in a grid with as few rectangles as possible
pyao
# how to cover a set in a grid with as few rectangles as possible

(Asked by: username_0 on 2011-11-11)

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

**Tags:** co.combinatorics, approximation
> **Comments:**
> **username_1**: Is the disjointness of rectangles crucial?  Allowing overlaps seems to broaden the applicability substantially, while not necessarily changing the answer.  
> **username_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?  
> **username_1**: Simultaneously cross-posted to MO: http://mathoverflow.net/questions/80665/how-to-cover-a-set-in-a-grid-with-as-few-rectangles-as-possible  
> **username_0**: will the problem be easier when allowing overlap?  About the rectangle,  yes, the black squares are covered by two rectangles  
> **username_2**: Voted to close to avoid duplicate effort.  
> **username_3**: It appears that you have crossposted this question *simultaneously*. While we don't mind a question being **reposted**, our [site policy](http://meta.cstheory.stackexchange.com/questions/225/official-faq-for-theoretical-computer-science/231#231) 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.  

---

## 0 answers

