4.3.1 The intersection staircase
The first idea is to compute for rectangle r (t) the intersection of r (t) with all r (t') where t' does not belong to P(t) ⋃ Q(t) ⋃ R (t). Clearly, polygons in r (t') ⋂ r (t) might represent cliques which are maximal in r (t') but are false maximal in r (t) since t' has not been considered there. To neglect the area where such rectangles r (t') intersect r (t) seems to be a good first step, although it will turn out that this is not sufficient. The union of those intersections is determined by a set of maximal rectangles, which form a kind of a staircase pattern above the diagonal of r (t) which we call the intersection staircase. The intersection staircase will be represented by a list of the right upper endpoints with decreasing y-coordinates and increasing x-coordinates.
The computation of the intersection staircase can be done using a list of the rectangles r (t') decreasingly ordered according to the y-coordinate of their upper boundaries. For each rectangle r (t') we check if it intersects the diagonal of r (t) and does not belong to P(t) ⋃ Q(t) ⋃ R (t). If the right boundary of the last element of the actual intersection staircase is also intersected by the upper boundary of r (t') or if the last element of the intersection staircase ends above r (t'), r (t') is appended to the list of the intersection staircase.
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).
Figure 7  The grey area denotes the basic intersection staircase, which describes the maximal cliques which potentially must not be considered since they have been considered already during the computation of the maximal cliques for hypotenuses like t' lower than t. In the example, we have three diagonals t' lower than t whose rectangles r (t') intersect t.