Skip to main content
edited tags
Link
Gerry Myerson
  • 39.9k
  • 10
  • 186
  • 247
edited tags
Link
Gerry Myerson
  • 39.9k
  • 10
  • 186
  • 247
Source Link
ltdtl
  • 21
  • 2

Placing Axis-parallel rectangles on 2-D plane

Can we place $n$ axis-parallel rectangles on 2D plane (e.g. four sides of each rectangle must be parallel to either x-axis or y-axis) such that for every pair of rectangles, there is a region that is contained in the intersection of the two rectangles but NOT contained in any other $n-2$ rectangles.

For $n = 1, 2, 3,$ and $4,$ it is a rather trivial task - you can draw some rectangles to find such arrangements. (for $n=1,2,3,4$, here's the arrangements: http://www.freeimagehosting.net/image.php?5260dfe888.png ). However, this does not seem to work for $n=5$ or higher.

Can you prove or disprove that you can place $n>=5$ axis-parallel rectangles to have the above property?