PMC:1524773 / 12266-13752 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 lemma states that an edge between two intervals is drawn if and only if their corresponding semi-squares intersect. The formal proof is given in [9] but we want to motivate it here: an edge between two intervals A and B is drawn if they tolerate each other. It follows, that A can tolerate B if B does not start right of ⌊|A| (1 - c)⌋; otherwise |A ⋂ B \u003cc · |A|. Note that the y-coordinate of a semi-square corresponding to an interval is equal to ⌊|A| (1 - c)⌋ and that the semi-square ends at xA + ⌊|A| (1 - c)⌋. On the other hand, any overlap with A cannot be longer than |A|, and this only in the case where B fully overlaps A. If B starts at xA + 1, their overlap can be of length at most |A| - 1, etc. The semi-square illustrates exactly this: The y-coordinate of the hypotenuse of any semi-square at position x gives a bound on the length of an overlap the corresponding interval can have with any other interval starting at x. Thus, two semi-squares will intersect if and only if the corresponding intervals tolerate each other: Let A be the longer interval, i.e., it determines the minimal length of the intersection, denoted by the y-coordinate of the basis of its corresponding semi-square. This semi-square can only be intersected by those semi-squares whose basis are below that of A and have a hypotenuse that is not lower than the basis of A at least at some point within the interval of A. Fig. 3 shows a set of intervals and their corresponding set of semi-squares.","tracks":[]}