Intersection of n rectangles - Maximum number of regions where exactly k rectangles intersect

Question

Imagine n axis-aligned rectangles (specified by its position (x,y), width and height). The rectangles are aligned in a way so that the i-th rectangle necessarily intersects with the (i+1)-th. For example let n = 3, then 1 necessarily intersects with 2 and 2 with 3. It is important to mention that this is not transitive; 3 can intersect with 1 but there is no guarantee (see figure for two valid alignment examples).

What I'm now looking for is the maximum possible number of regions where exactly k = 2,...,n rectangles intersect with each other (these regions are shown in the figure). In other words, I'm looking for a worst-case alignment of n rectangles so that the number of regions where exactly k rectangles intersect reaches its maximum. Theoretical, the maximum possible number of regions where exaclty k rectangles intersect is n over k (the binomial coefficient). However, this formula is geometrical only valid for n < 4 as it is not possible to align (and to draw) rectangles for n >= 4 so that in the worst-case n over k regions exist where exactly k rectangles intersect.

The first sub-image of the figure shows the worst-case alignment for n = 3. There are 3 over 2 = 3 regions where exactly two rectangles intersect and 3 over 3 = 1 region where exactly three rectangles intersect. The second sub-image also shows a valid alignment for three rectangles however this is not a worst-case alignment as, for example, there is no region where exactly three rectangles intersect.

Answer 1

Build a matrix where the cell Aij is 1 if rectangles i and j intersect or 0 if they don't. This matrix is symmetric.

Now notice that many 1's close to the diagonal mean more intersections between contiguous-aligned rectangles.

The "worst" case, where k, the number of rectangles that intersect each other, is maximum, is represented in the matrix by k contiguous 1's, with no 0 in between. You can consider the elements after the diagonal. This way the property "rectangle i intersects rectangle j" is fulfilled.

The problem is how to swap rows and columns to achieve this result. It may be a matrix bandwidth reduction problem. See, for example, this and this.

You can also generate your own algorithm for your special case. Be aware of it can be a NP problem, and that several solutions may exist.

Answer 2

A WRONG answer; not removed only because of the approach that may or may not be useful.

The geometric data -- which rectangles intersect -- can be abstracted away: all that matters is the following property:

Property P: If rectangles i and j intersect that implies that i intersects with i+1,...,j-1 as well.

If your representation of the problem encodes P it doesn't matter anymore that you started with the rectangles.

Now, how do we keep record which rectangles intersect? One way would be a graph with nodes being the rectangles and edges intersections, but that isn't very useful because the above property P is not evident in a graph. A better way would be to setup the following matrix:

Represent i-th rectangle with the i-th row of a matrix A that has 0s until the entry A(i,i), 1s from A(i,i) to A(i,i+m), where i+m is the index of the furthest rectangle that intersects with rectangle i. That is, A has n rows, one per the original rectangle, it consists of 0s and 1s, and A(i,j) for j>i is 1 if and only if rectangles i and j intersect. For j

Now, what does it mean that we have an area of exactly k intersecting rectangle? I claim that the above matrix represents that by a column that has exactly k 1s. Why? Suppose that your area is an intersection of rectangles i+1,...,i+k. Take a look at the matrix entry A(i+k,i+k). The column above it has 1s in rows from 1+1 to i+k and 0s otherwise.

The above matrix looks superficially similar to young's skew-tableau, thus the comment. But yes, similarity is superficial because it doesn't originate from a partition.

Now it remains to maximize the number of columns in A that has exactly k 1s. I think the best one would be a matrix with exactly k 1s in each row, which would give the answer to the original problem n. The answer is obviously wrong, so I'm missing something here. Aaaaah!