A straight forward approach is to partition the Items according to how many bits are set in the area. Clearly, if a.bits > b.bits, then area a cannot be a subset of area b.

Going from that further, one might consider building a structure similar to a hypertree.

A B 0011 0001 0011 0011 1111 0111 0000 0000 <- just for demonstrating purposes to have width and height both a power of 2 

might be represented by (considering a 2x2 grouping)

X Y 04 03 22 12 

(where the numbers represent the numbers of set bits). X and Y are nodes which have A and B as children, respectively. X and Y might also have more children.

To check if B is a subset of some other item, you then visit the compacted nodes (X=0422) and check if each cell has more bits set than the compact representation for B. If yes, you can repeat the test for all children of X, using the complete area.

I hope my explanations are comprehensible. :) In the worst case, this will not be better than n^2, but in practice can hopefully significantly reduce the number of comparisons.

I just realise that this is probably a special case of Doc Brown's answer, where the hash function is simply "count". But maybe this explanations give you more insight.

A straight forward approach is to partition the Items according to how many bits are set in the area. Clearly, if a.bits > b.bits, then area a cannot be a subset of area b.

Going from that further, one might consider building a structure similar to a hypertree.

A B 0011 0001 0011 0011 1111 0111 0000 0000 <- just for demonstrating purposes to have width and height both a power of 2 

might be represented by (considering a 2x2 grouping)

X Y 04 03 22 12 

(where the numbers represent the numbers of set bits). X and Y are nodes which have A and B as children, respectively. X and Y might also have more children.

To check if B is a subset of some other item, you then visit the compacted nodes (X=0422) and check if each cell has more bits set than the compact representation for B. If yes, you can repeat the test for all children of X, using the complete area.

I hope my explanations are comprehensible. :) In the worst case, this will not be better than n^2, but in practice can hopefully significantly reduce the number of comparisons.

I just realise that this is probably a special case of Doc Brown's answer, where the hash function is simply "count". But maybe this explanations give you more insight.