I am interested in the following question:

Let a finite sequence of rectangles in $\mathbb{R}^2$ be given such that

  1. The edges of the rectangles are parallel to the coordinate axes, and

  2. The rectangles cover the unit square, $[0,1]^2$.

Is it possible to find, among these rectangles, a collection of mutually disjoint rectangles whose combined area is at least $1/4$?

As of yet, I'm not sure if a solution exists. My friend and I have spent a while thinking about this and have gotten nowhere.

Any help is greatly appreciated.

  • $\begingroup$ Where'd you come across this problem? This is very nifty looking. $\endgroup$ – Steven Stadnicki Nov 24 '18 at 2:52
  • 3
    $\begingroup$ This was asked before: math.stackexchange.com/questions/2381180/… $\endgroup$ – Alon Amit Nov 24 '18 at 3:03
  • 1
    $\begingroup$ @AlonAmit - Close, but not quite: in that question, the ratio is to the total area covered by all the rectangles (thus the chosen solution, which uses overlapping rectangles covering areas of unbounded size). In this question, the ratio is to the unit square, so the solution there does not apply here. $\endgroup$ – Paul Sinclair Nov 24 '18 at 15:23
  • 1
    $\begingroup$ @snulty Without loss of generality, we can assume that the rectangle is equal to the union, since we can just replace each rectangle by its intersection with the unit square. $\endgroup$ – Misha Lavrov Nov 28 '18 at 3:46
  • 1
    $\begingroup$ @ChristianBlatter: It doesn't really matter... assume they're closed (so "cover the unit square" is as easy as possible) and that rectangles just sharing edges are considered disjoint (so "mutually disjoint" is as easy as possible), and the answer is still "no" (for any constant $c>0$, not just $1/4$). $\endgroup$ – mjqxxxx Nov 28 '18 at 18:21

The question linked by @AlonAmit in the comments answers exactly this question, and shows that the answer (at least with the constant $1/4$) is no. For a concrete demonstration, start with a $6\times 6$ square broken into thirty-sixths: $$ \begin{matrix} 0&1&2&3&4&5\\ 6&7&8&9&a&b\\ c&d&e&f&g&h\\ i&j&k&l&m&n\\ o&p&q&r&s&t\\ u&v&w&x&y&z \end{matrix} $$ Now cover each corner $2\times2$ by four individual $(1+\varepsilon)\times (1+\varepsilon)$ rectangles, such that the four rectangles in the upper left ($0,1,6,7$) are mutually overlapping, as are those in each of the other corners. And cover the remaining shape in the center (a cross) by eight individual $(3+\varepsilon)\times(1+\varepsilon)$ rectangles ($28e$, $39f$, $cde$, $ijk$, $kqw$, $lrx$, $fgh$, and $lmn$), such that all eight include the center of the square. Any disjoint set of these rectangles includes at most four of the $(1+\varepsilon)\times(1+\varepsilon)$ rectangles and at most one of the $(3+\varepsilon)\times(1+\varepsilon)$ rectangles, and so has total area just over $7/36\approx 19.4\%$ of the full square.

  • $\begingroup$ Does a $(1+\epsilon)\times (1+\epsilon)$ rectangle have area $1+2\epsilon +\epsilon^2$? Which is a big square? $\endgroup$ – snulty Nov 28 '18 at 9:37
  • $\begingroup$ I would've thought theres arrangements where you cover 4 corners of the box, i.e. the four 2x2 squares, and the squares you've used are disjoint which would mean you've covered 16/36 of the area, since each letter represents 1/36 the area right? I must be misunderstanding something $\endgroup$ – snulty Nov 28 '18 at 15:00
  • $\begingroup$ @snulty: By $(1+\varepsilon)\times(1+\varepsilon)$, I mean covering a single small square plus a little extra. There's no disjoint set of the rectangles I listed that cover a corner $2\times 2$, because each corner $2\times 2$ is covered by four mutually overlapping rectangles, of which you can only include one. $\endgroup$ – mjqxxxx Nov 28 '18 at 15:25
  • $\begingroup$ @DavidC.Ullrich: I changed it to say $6\times 6$ from the outset. $\endgroup$ – mjqxxxx Nov 28 '18 at 15:28
  • 5
    $\begingroup$ @mjqxxxx: I find this kind of answers very helpful, so I created an SVG image (nominal-animal.net/answers/unit-square-36.svg) you can use if you want to illustrate the covering. (Consider it public domain, or CC0-1.0 licensed.) The rectangles have rounded corners to make it easier to perceive the overlappings. The small squares areas are $\frac{1+\epsilon}{36} \approx 0.0278$ of the unit square, and the larger rectangles $\frac{3+\epsilon}{36} \approx 0.0834$. The largest disjoint sets contain four squares and one rectangle, for a maximum area of approx $0.1945$. $\endgroup$ – Nominal Animal Nov 29 '18 at 3:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.