How to cover a set in a grid with as few rectangles as possible?

Question

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

Answer 1

In general, I don't think you can expect a set to be well approximated by such a small number of rectangles.

Let $S$ be a random set formed by including every square with probability $1/2$. Then with high probability $S$ has $r \geq 0.5-\epsilon$ for any $\epsilon$.

Now consider any (fixed) arbitrary set $T$. The error of $T$ from $S$ can be thought of as the sum of $N^2$ Bernoulli trials, each with probability $1/2$. It follows from the Chernoff bound that for any fixed $\epsilon<1/2$ the probability of having error at most $\epsilon N^2$ is at most $c^{n^2}$ for some constant $c<1$ depending only on $\epsilon$.

On the other hand, there are only $4^N$ rectangles (choose whether or not to include each row and column), so at most $4^{Nk}$ unions of $k$ rectangles. Taking the union bound over all such unions, we see that with high probability $S$ is not approximated by any union of $o(N)$ rectangles.

In general, I have a feeling (though I'm not familiar enough with this area to say for certain) that a better way to explain this all is in terms of information theory/entropy -- Specifying that a set has density $r$ still leaves you with approximately $N^2 H(r)$ (where $H$ is the entropy function) bits of entropy. On the other hand, the union of $k$ rectangles has less than $2kN$ such bits. You can't compress the former into the latter if $k$ is much less than $NH(r)$ without incurring a fair amount of error.

Answer 2

An exact partition into the minimum number of rectangles can be found in $O(n^{3/2} \log n)$ time, if the set $S$ forms a region with $n$ corners. See David Eppstein's survey, "Graph-Theoretic Solutions to Computational Geometry Problems," arXiv:0908.3916. For primary references, see his answer to the earlier MO question, "split polygon into minimum amount of rectangles and triangles."

---

        

---

Because there is a fast exact algorithm, perhaps there has not been study of approximation algorithms.

Answer 3

The question is not clear to me, nor is your guess. Take $r=\frac12$, $\epsilon=\frac14$ and $S$ the checkerboard subset of the square. I can't see how you could do with less than a rectangle for every element of $S$, that's $\frac12N^2$ and not bounded independently of $N$ at all. If you guess it to be interpreted as $O(P(\frac1r))$ as $r\to0$ for some polynomial function $P$ then this seems a strange guess indeed: your introduction seems to indicate you are more interested in the limit $r\to1$. My guess would be that as long as $\frac{1-r}r>\epsilon$ there is no bound independent of $N$, and otherwise 1 rectangle (the whole square) suffices.