PMC:1524773 / 35849-43401 JSONTXT

{"target":"https://pubannotation.org/docs/sourcedb/PMC/sourceid/1524773","sourcedb":"PMC","sourceid":"1524773","source_url":"https://www.ncbi.nlm.nih.gov/pmc/1524773","text":"4.3 Avoiding false maximal cliques when computing candidates for hypotenuse t\nIn the previous subsection, we have described the efficient computation of all maximal cliques having a specific triangle t as their lowest element. To provide truly output-sensitive algorithms we have to notice that some of those cliques, say M, might not be maximal overall, since there might be a triangle s(t') with hypotenuse t' such that M' = M ⋃ s(t') is also a clique. Clearly t' is lower than t. Note that M' will be found when computing the maximal cliques with lowest element t'.\nSo, when considering t we have to avoid those cliques, which are not truly maximal.\n\n4.3.1 The intersection staircase\nThe 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.\nThe 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.\nClearly, 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).\nFigure 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.\n\n4.3.2 Refinement of the staircase\nWe keep the intersection staircase as an ordered list of right upper corners of the corresponding rectangles r (t'). First we describe how rectangles from P(t) influence the intersection staircase.\nWe consider all the rectangles of P(t) and how they intersect the staircase. On this behalf, we sort the lower left corners ai of the rectangles pi according to the difference between y- and x-coordinates and process the rectangles in this ordering. Clearly, all those corners lie to the left of the left boundary of r (t). Assume that we have already processed the corners a1,..., ai-1 as well as the topmost j steps of the staircase with j ≥ 0. Let s(tj) be the actual step defined by rectangle r (tj) to be considered. We consider pi. If pi is below of the diagonal of r (tj), it can be neglected since it has been considered while processing r (tj). Otherwise, if the lower boundary intersects step s(tj), the upper part of s(tj) is cut off, and we proceed to Pi+1. If the lower boundary is even lower than the whole step, s(tj) is completely cut off, and we proceed to s(tj+1). In this case, we reconsider pi (see Fig. 8).\nFigure 8 The basic intersection staircase shown in grey must be refined since there are rectangles like Pi ∈ Pr(t) and r ∈ Rr(t) which have not been considered before in the runs for t' and which reduce the basic intersection staircase such that a lower staircase shown in darkgrey remains. Hence for the computation of the maximal cliques regarding t we have to reduce the area of the upper half only by the refined staircase. Clearly, since there are at most n points pi and steps s(tj), the whole process takes O(n log n).\nAnalogously, we can refine the intersection staircase by considering the rectangles in Q(t), which have not been considered in the staircase-defining rectangles r (t').\nFor rectangles in R (t), the refinement is slightly different, so we will consider this in more detail:\nThe intersection staircase now separates the area representing cliques that have not been computed before from those which either have been computed before or which have not been assigned yet. Hence we only move the intersection staircase downwards!\nThe intersection staircase consists of a list of points c1,...,ck which are not necessarily corners of rectangles, but at least they can uniquely be assigned to rectangles r (t') ∌ Pr(t) ⋃ Qr(t) ∈ Rr(t). Assume that these points are ordered with decreasing y-coordinates. We denote the corresponding diagonals t1,...,tk analogously.\nFirst we state an important observation:\nLemma 5 Only rectangles r (t') which are part of the intersection staircase have maximal diagonals. Hence the non-maximal r (t') that is not in P(t) ⋃ Q(t) ⋃ R (t) does not need to be considered.\nThe elements of Rr(t) are similarly ordered according to the difference between y- and x-coordinate of their left lower corner. The idea is that when comparing a rectangle r (t') from the staircase with an element s from Rr(t) then the staircase should not be changed if s intersects t'. Otherwise, the intersection of s must be cut off from the staircase.\nMore formally, we start with the topmost step of the staircase and let t' be the corresponding diagonal. Let smax be the first element in the ordered list from Rr(t). If the left lower corner is below t', then smax has been considered already in the computation of the maximal cliques regarding t'. Hence it can be disregarded and it does not change the staircase. We can delete smax from the list and let the next element be smax.\nIf the left lower corner of smax is above t', we compute the intersection of smax with the actual step of the staircase, and remove it either completely or only partially depending on the size of the intersection. In the first case, we proceed to the next lower step of the staircase while in the second case, we remove smax from the list and get a new smax.\nIn all cases, the operation can be done in O(1) time, and in total we have only O(n) operations. This concludes the description how we effectively restrict the area of r (t) to be considered for computation of just those maximal cliques which have not been computed before.\nHence we can summarize the whole section by\nTheorem 1 In time O(n2 log n + out) we can determine all maximal cliques in c-max-tolerance graphs.\nNote that the naive bound of O(n4) for out can be improved to O(n3) by writing down only the differences between subsequent maximal cliques. This is supported by the above methods to determine the maximal cliques in a plane sweep approach.","divisions":[{"label":"title","span":{"begin":0,"end":77}},{"label":"p","span":{"begin":78,"end":568}},{"label":"p","span":{"begin":569,"end":652}},{"label":"sec","span":{"begin":654,"end":2965}},{"label":"title","span":{"begin":654,"end":686}},{"label":"p","span":{"begin":687,"end":1472}},{"label":"p","span":{"begin":1473,"end":2029}},{"label":"p","span":{"begin":2030,"end":2605}},{"label":"figure","span":{"begin":2606,"end":2965}},{"label":"label","span":{"begin":2606,"end":2614}},{"label":"caption","span":{"begin":2616,"end":2965}},{"label":"p","span":{"begin":2616,"end":2965}},{"label":"title","span":{"begin":2967,"end":3000}},{"label":"p","span":{"begin":3001,"end":3198}},{"label":"p","span":{"begin":3199,"end":4126}},{"label":"figure","span":{"begin":4127,"end":4555}},{"label":"label","span":{"begin":4127,"end":4135}},{"label":"caption","span":{"begin":4137,"end":4555}},{"label":"p","span":{"begin":4137,"end":4555}},{"label":"p","span":{"begin":4556,"end":4653}},{"label":"p","span":{"begin":4654,"end":4822}},{"label":"p","span":{"begin":4823,"end":4926}},{"label":"p","span":{"begin":4927,"end":5176}},{"label":"p","span":{"begin":5177,"end":5509}},{"label":"p","span":{"begin":5510,"end":5550}},{"label":"p","span":{"begin":5551,"end":5746}},{"label":"p","span":{"begin":5747,"end":6103}},{"label":"p","span":{"begin":6104,"end":6535}},{"label":"p","span":{"begin":6536,"end":6894}},{"label":"p","span":{"begin":6895,"end":7168}},{"label":"p","span":{"begin":7169,"end":7212}},{"label":"p","span":{"begin":7213,"end":7312}}],"tracks":[]}