There are $n$ squares of $m$ different colors. Squares of the same color are interior disjoint, but squares of different colors may intersect.

For every square, define its "greed" as the maximum number of squares of a single color that it intersects. For example, in the figure below, the top-left red square has a greed of 1 because it intersects 1 green square; the bottom-right red square has a greed of 4 becaues it intersects 4 green squres (in addition to 1 blue square); the other two red squares have a greed of 2.

enter image description here

MY QUESTION IS: What is the minimum greed that a single square can have, in the worst case?

4 is an upper bound, because the smallest of all squares has a greed of at most 4. This is because, when a square intersects a larger square, at least one corner of the smaller square must be covered. Since a square has 4 corners, it can intersect at most 4 larger squares that are disjoint, i.e., at most 4 squares per color.

2 is a lower bound, as shown by the construction below, where all squares have a greed of 2:

enter image description here

So, the question is whether there is always a square with a greed of at most 2? Or at most 3?

  • 2
    $\begingroup$ Why could a large red square not intersect, say, 15 blue squares, all lined up along its right-hand edge, but not intersecting each other? Perhaps you need to be clearer for us on what the constraints on the squares might be. $\endgroup$ – John Hughes Jan 16 '14 at 20:43
  • $\begingroup$ Or, what if all squares have distinct interiors? $\endgroup$ – Eddie E. Jan 16 '14 at 20:43
  • 1
    $\begingroup$ @John If I understand the problem correctly, then the question is on $$\sup_{\text{instance }I}\quad\min_{\text{square } s \in I}\quad\mathrm{greed}(s).$$ $\endgroup$ – dtldarek Jan 16 '14 at 20:44
  • 1
    $\begingroup$ @HagenvonEitzen yes. In other words: Is there an arrangement of squraes where each square intersects at least 3/4 squares of at least one other color? $\endgroup$ – Erel Segal-Halevi Jan 16 '14 at 20:59
  • 1
    $\begingroup$ @Listing The question stipulates that they must be squares, i.e. side lengths are equal. $\endgroup$ – Eddie E. Jan 16 '14 at 22:10

Partial solution: Here is an example for lowerbound of $\mathbf{3}$:


and my hypothesis is that this is it (assuming finite number of squares and colors).

I hope this helps $\ddot\smile$


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.