PMC:1524773 / 9838-15742
Annnotations
{"target":"https://pubannotation.org/docs/sourcedb/PMC/sourceid/1524773","sourcedb":"PMC","sourceid":"1524773","source_url":"https://www.ncbi.nlm.nih.gov/pmc/1524773","text":"2 Mathematical background\nIn this section we will define the formal basis and repeat some earlier derived results that are essential for the understanding of the rest of the article.\nLet S denote a set of n intervals Ii = [xi, yi], 1 ≤ i ≤ n, xi, yi ∈ ℕ, xi \u003cyi, where xi denotes the coordinate of the left endpoint and yi denotes the coordinate of the right endpoint. The length |Ii| of an interval is defined as yi - xi. Let Ii = [xi, yi] and Ij = [xj, yj] be two intervals. Their overlap length |Ii ⋂ Ij| is given by:\n|Ii ⋂ Ij| = min{yi, yj} - max{xi, xj}.\nA c-max-tolerance graph G = (V, E) is associated with a tolerance parameter 0 ≤ c ≤ 1 and it is then given by V = {v1, ...,vn} representing the set of intervals and\nE = {{vi, vj}||Ii ⋂ Ij| ≥ c · max{|Ii|, |Ij|}} (1)\nfor 1 ≤ i,j ≤ n. Pairs of intervals satisfying this condition are said to tolerate each other. More generally, interval Ii tolerates interval Ij if |Ii ⋂ Ij| \u003e c · |Ii|.\nIn a general max-tolerance graph each interval Ii is associated with a tolerance 0 ≤ ti ≤ |Ii| and here, two intervals are said to tolerate each other, if |Ii ⋂ Ij| ≥ max{ti, tj}.\nGiven a graph G = (V, E), a clique is a subset C ⊆ V of pairwise-connected vertices. A clique C is called a maximal clique if there is no other clique C' ⊃ C. A clique is a maximum clique if its cardinality is of largest possible size.\nThe following lemma has been derived for general max-tolerance graphs and applies also to c-max-tolerance graphs [9]:\nLemma 1 The number of maximal cliques in (c-)max-tolerance graphs is O(n3).\nThis result has been derived by a fundamental equivalence, for which we will need the following definitions: Let S = {[x1, y1], [x2, y2],..., [xn, yn]} be a set of intervals and let 0 \u003cc ≤ 1.0 denote the same relative tolerance for all intervals. Let T(S) denote a set of triangles Δi = {Ai, Bi, Ci}, Ai, Bi, Ci ∈ (ℕ × ℕ) with the following coordinates:\nAi = (xi, |Ii| - ⌊|Ii| * (1 - c)⌋) (2)\nBi = (xi + ⌊|Ii| * (1 - c)⌋, |Ii| - ⌊|Ii| * (1 - c)⌋) (3)\nCi = (xi, |Ii|) (4)\nThus, these triangles look like squares of length ⌊|Ii| * (1 - c)⌋, located at (xi, ⌊|Ii| * (1 - c)⌋), cut in half by the diagonal from their upper left to their lower right corner. Therefore, we will call these triangles semi-squares. The next lemma states the following equivalence:\nLemma 2 The c-max-tolerance graph of (S,c) is equivalent to the intersection graph of T(S).\nThe 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.\nFigure 3 A set of intervals A-E together with its corresponding semi-square representation. This example for c = 0.5 also shows that not all candidate cliques are maximal with respect to the set of active semi-squares: When D is born, there are two maximal cliques in the y-structure: {A, B} and {B, C}. D is intersecting with A and B. Thus, there will be one candidate clique {A, B, D}, built from clique {A, B}, and {A, D}, built from {B, C}. The latter candidate clique is thus not maximal with respect to all active cliques and should not be inserted into Q. The semi-squares can be ordered according to three different criteria: either by their left sides xi, or their y-coordinate of their basis at |Ii| - ⌊|Ii| * (1 - c)⌋ or by their hypotenuse. Hypotenuses can be easily ordered according to their height at a given x-position by noting that the slope is -1 for all of them. Thus, for every x-coordinate with x between xi and xi + ⌊|Ii| * (1 - c)⌋, the following equation is valid:\nconst = yi - (x - xi) (5)\nwhere yi is the endpoint of the corresponding interval Ii. Thus, for a given x-position the height of the hypotenuse of each active semi-square is determined by yi + xi - x (s. Fig. 2).\nSince x is the same for all active semi-squares we can order the semi-squares by yi + xi. An important observation is that the order by the y-coordinate of the basis of the semi-squares or by their hypotenuse is not the same in general.\nA very general tool in geometric algorithms is that of a sweep-line [12]: Here, so called events are ordered and then processed in this order, thus, we process the events in a sweep, where the invariant is that all events up until a certain point in the ordered list are already processed and that the events after this point still have to be processed. In geometrical problems such as finding the intersection points of a set of lines, an event is typically something as the begin or birth of a geometric structure and the end or death of it.","divisions":[{"label":"title","span":{"begin":0,"end":25}},{"label":"p","span":{"begin":26,"end":182}},{"label":"p","span":{"begin":183,"end":520}},{"label":"p","span":{"begin":521,"end":559}},{"label":"p","span":{"begin":560,"end":724}},{"label":"p","span":{"begin":725,"end":781}},{"label":"p","span":{"begin":782,"end":951}},{"label":"p","span":{"begin":952,"end":1131}},{"label":"p","span":{"begin":1132,"end":1367}},{"label":"p","span":{"begin":1368,"end":1485}},{"label":"p","span":{"begin":1486,"end":1561}},{"label":"p","span":{"begin":1562,"end":1915}},{"label":"p","span":{"begin":1916,"end":1960}},{"label":"p","span":{"begin":1961,"end":2024}},{"label":"p","span":{"begin":2025,"end":2050}},{"label":"p","span":{"begin":2051,"end":2335}},{"label":"p","span":{"begin":2336,"end":2427}},{"label":"p","span":{"begin":2428,"end":3914}},{"label":"figure","span":{"begin":3915,"end":4478}},{"label":"label","span":{"begin":3915,"end":3923}},{"label":"caption","span":{"begin":3925,"end":4478}},{"label":"p","span":{"begin":3925,"end":4478}},{"label":"p","span":{"begin":4479,"end":4905}},{"label":"p","span":{"begin":4906,"end":4937}},{"label":"p","span":{"begin":4938,"end":5123}},{"label":"p","span":{"begin":5124,"end":5360}}],"tracks":[]}