how to cover a set in a grid with as few rectangles as possible - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-18T13:34:55Z http://mathoverflow.net/feeds/question/80665 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/80665/how-to-cover-a-set-in-a-grid-with-as-few-rectangles-as-possible how to cover a set in a grid with as few rectangles as possible Penghui Yao 2011-11-11T08:33:30Z 2011-11-11T23:11:05Z <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. 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.</p> <p>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> http://mathoverflow.net/questions/80665/how-to-cover-a-set-in-a-grid-with-as-few-rectangles-as-possible/80676#80676 Answer by Joseph O'Rourke for how to cover a set in a grid with as few rectangles as possible Joseph O'Rourke 2011-11-11T11:18:10Z 2011-11-11T11:18:10Z <p>An <em>exact</em> 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," <a href="http://arxiv.org/abs/0908.3916" rel="nofollow">arXiv:0908.3916</a>. For primary references, see his answer to the earlier MO question, "<a href="http://mathoverflow.net/questions/28303/" rel="nofollow">split polygon into minimum amount of rectangles and triangles</a>."</p> <p><br />&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; <img src="http://cs.smith.edu/~orourke/MathOverflow/EppsteinRectangles.jpg" alt="Rectangle Partition"><br /></p> <p>Because there is a fast exact algorithm, perhaps there has not been study of approximation algorithms.</p> http://mathoverflow.net/questions/80665/how-to-cover-a-set-in-a-grid-with-as-few-rectangles-as-possible/80677#80677 Answer by Marc van Leeuwen for how to cover a set in a grid with as few rectangles as possible Marc van Leeuwen 2011-11-11T11:44:27Z 2011-11-11T11:44:27Z <p>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.</p> http://mathoverflow.net/questions/80665/how-to-cover-a-set-in-a-grid-with-as-few-rectangles-as-possible/80714#80714 Answer by Kevin P. Costello for how to cover a set in a grid with as few rectangles as possible Kevin P. Costello 2011-11-11T22:15:44Z 2011-11-11T23:11:05Z <p>In general, I don't think you can expect a set to be well approximated by such a small number of rectangles. </p> <p>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$. </p> <p>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&lt;1/2$ the probability of having error at most $\epsilon N^2$ is at most $c^{n^2}$ for some constant $c&lt;1$ depending only on $\epsilon$. </p> <p>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. </p> <p>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. </p>