Clearly, the intersection staircase can be computed in time O(n log n). Unfortunately, this is not sufficient, since there might be rectangles r (t") ∈ Pr(t) ⋃ Qr(t) ⋃ Rr(t) which intersect r (t') but not the diagonal t' of r (t'), hence they have not been taken into account. Clearly, the intersection of r (t") with r (t) ⋂ r (t') has to be considered if it infers new cliques which have not been found when processing r (t'). Hence the intersection staircase which defines the forbidden area when processing r (t) has to be refined and its area will decrease (see Fig. 7).