PMC:1524773 / 31649-35847 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":"The algorithm\nWe perform a left-to-right sweep. As the underlying data structure we keep the list L of all polygons which are currently intersected by the sweepline as well as a distinct list LM of all locally maximal polygons. We start our sweep at the left side of r (t) initializing list L by the polygons defined by all rectangles of Pr(t) in increasing order of their lower boundaries. LM is initialized with the topmost polygon representing the intersection of all rectangles in Pr(t). Two basic events occur while sweeping from left to right:\n1. A rectangle from Pr(t) ends\n2. A rectangle from Qr(t) or Rr(t) is added.\n1. Let s be the rectangle from Pr(t) with the right lower corner c that ends. Since s intersects all polygons from c up to the upper boundary or r (t), the removal of s decreases the cover-variables by one for all polygons above c, the two polygons adjacent to c have to join, and the maximal polygons above c have to be output. The join-operation can be done by updating list L after locating the two polygons by binary search for c. The output operation can be performed easily by scanning list LM from the top until the y-coordinate of c has been reached.\nNote that there will not arise any new local maxima, and all previous maxima remain. One important speciality is that the maxima we just output should not be output even they still represent maxima. We call them false maxima, we remove them from the list LM and insert them in a list LF ordered by their y-coordinates. Note that false maxima have to be reinserted into list LM again as soon as they are covered by a new rectangle from either Qr(t) or Rr(t). This might happen as described in the next case:\n2. A rectangle s from Qr(t) ⋃ Rr(t) starts to be intersected by the sweepline. We discuss the case that s ∈ Qr(t), the other case is symmetrical.\nLet c be the left upper corner of rectangle s. s adds a new intersection to all polygons below c, the polygon containing c is split into two and the cover-variables of all of them increase by one. Note that a new locally maximal polygon might arise below c. All false maxima below c become 'true' maxima again. They are deleted from LF and inserted again into LM. The operation can be performed by locating the polygon to be split by binary search in L, scanning the list LF until the y-coordinate of c is reached, and inserting all false maxima back into LM.\nAnalysis: At each event we have to perform a binary search for corner c. A direct implementation includes the insertion and deletion of maxima and false maxima into the corresponding lists in time O(log n). Finally it leads to a runtime of O(n log n + C(t) log n + out), where C(t) denotes the number of maximal cliques with lowest hypotenuse t.\nNext we will show how to improve the efficiency of the algorithm to O(n log n + out): Instead of two separated lists LM and LF we keep only one doubly linked list LD of interleaved blocks containing false maximals and 'true' maximals ordered by y-coordinates. A block denotes a maximal sequence of maxima of one or the other kind. We keep also the blocks internally connected.\nEach block is created by a certain event and it will be removed eventually. We count only the number of block creations, which naturally links the number of block removals, and show that only O(n + C(t)) blocks will be created.\nOne possible event is the creation/removal of a polygon adjacent to corner c of a single maximum in the list LD. Possibly one new block is created by splitting an old block into two. After having located the position of the block, corresponding to the y-coordinate of c, by binary search, this can be done in constant time. Clearly there are at most O(n) such events.\nAll other events consist of browsing through the lists of blocks starting from the upper or lower boundary of rectangle r (t), output the contents and join adjacent blocks until reaching the polygon with y-coordinate of corner c. Hence in these events, each operation creates one or two new blocks, but might remove k blocks in time O(k).\nIn total, we are using only time O(n log n) time.\nLemma 4 Determining the maximal cliques with lowest parameter t takes time O(n log n + out).","divisions":[{"label":"title","span":{"begin":0,"end":13}},{"label":"p","span":{"begin":14,"end":549}},{"label":"p","span":{"begin":550,"end":580}},{"label":"p","span":{"begin":581,"end":625}},{"label":"p","span":{"begin":626,"end":1184}},{"label":"p","span":{"begin":1185,"end":1691}},{"label":"p","span":{"begin":1692,"end":1837}},{"label":"p","span":{"begin":1838,"end":2397}},{"label":"p","span":{"begin":2398,"end":2743}},{"label":"p","span":{"begin":2744,"end":3120}},{"label":"p","span":{"begin":3121,"end":3348}},{"label":"p","span":{"begin":3349,"end":3716}},{"label":"p","span":{"begin":3717,"end":4055}},{"label":"p","span":{"begin":4056,"end":4105}}],"tracks":[]}