Computing Optimal Shortcuts for Networks

Computing Optimal Shortcuts for Networks Delia Garijo Departamento de Matemática Aplicada I, Universidad de Sevilla, Spain [email protected] Alberto Márquez Departamento de Matemática Aplicada I, Universidad de Sevilla, Spain [email protected] Natalia Rodríguez Departamento de Computación, Universidad de Buenos Aires, Argentina nro[email protected] Rodrigo I. Silveira Departament de Matemàtiques, Universitat Politècnica de Catalunya, Spain [email protected] Abstract We study augmenting a plane Euclidean network with a segment, called shortcut, to minimize the largest distance between any two points along the edges of the resulting network. Questions of this type have received considerable attention recently, mostly for discrete variants of the problem. We study a fully continuous setting, where all points on the network and the inserted segment must be taken into account. We present the first results on the computation of optimal shortcuts for general networks in this model, together with several results for networks that are paths, restricted to two types of shortcuts: shortcuts with a fixed orientation and simple shortcuts. 2012 ACM Subject Classification Theory of computation →Computational geometry Keywords and phrases graph augmentation, shortcut, diameter, geometric graph Digital Object Identifier 10.4230/LIPIcs.ISAAC.2018.15 Related Version A full version of the paper is available at [12], https://arxiv.org/abs/1807. 10093. Funding D. G. and R. S. were supported by project MTM2015-63791-R. R. S. was also supported by Gen. Cat. 2017SGR1640 and MINECO through the Ramón y Cajal program. A. M. was supported by project BFU2016-74975-P. 1 Introduction A fundamental task in network analysis, especially in the context of geographic data (for instance, for networks that model roads, rivers, or train tracks), is analyzing how an existing network can be improved. This can arise in many different contexts: in relation to facility location analysis, for instance, to guarantee a certain maximum travel time from any point on the network to the nearest hospital, or in road network design problems, to decide where to add road segments to reduce network congestion [16]. Networks like the ones above are naturally modeled as a geometric network: an undirected graph whose vertices are points in R2 and whose edges are straight-line segments connecting pairs of points. Moreover, in many applications, it is reasonable to assign lengths to the edges equal to the Euclidean distance between their endpoints. These are called Euclidean ©Delia Garijo, Alberto Márquez, Natalia Rodríguez, and Rodrigo I. Silveira; licensed under Creative Commons License CC-BY 29th International Symposium on Algorithms and Computation (ISAAC 2018). Editors: Wen-Lian Hsu, Der-Tsai Lee, and Chung-Shou Liao; Article No. 15; pp. 15:1–15:12 Leibniz International Proceedings in Informatics Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Dagstuhl Publishing, Germany 15:2 Computing Optimal Shortcuts for Networks p q r ¯r Figure 1 Left: Example of network with diameter 4 (each edge has unit length); in the highway model, no single segment insertion can improve the diameter. Right: in the planar model, segment pq is a shortcut, since its insertion reduces the diameter to d ( r, ¯r )=3 . 5. However, pq is not a shortcut in the highway model as its insertion increases the diameter to 5. networks. When, in addition, there are no crossings between edges, the Euclidean network is said to be plane. Many problems in geographic analysis, for instance, those involving transportation networks, can be accurately modeled with a plane Euclidean network. In the following, we shall simply write network, it being understood as plane and Euclidean. One of the most fundamental ways to improve a network is by adding edges. This increases the connectivity of the network and potentially can decrease travel times and congestion. The most studied criteria to measure network improvement, in the geometric setting, are related to distances. Particularly important is the maximum distance, or diameter of the network, which provides an upper bound on the distance between any two network points. Another important distance-related criterion in this context is the dilation, which captures the maximum detour between two points on the network. In this work, we focus on the problem of adding edges to a network in order to improve its diameter. This can be seen as a variant of the Diameter-Optimal- k -Augmentation problem, which consists in inserting k additional segments into a graph, while minimizing the largest distance in the resulting network (see the survey [14] for more on augmentation problems over plane geometric graphs). More precisely, we study a continuous version of the problem for k = 1: we consider the addition of one segment, called shortcut, whose endpoints can be any two points (not necessarily vertices) on the network. A segment will be considered a shortcut only if its insertion improves the diameter of the resulting network. Note that the resulting network includes the points on the shortcut inserted. Our goal is to find an optimal shortcut: one minimizing the diameter of the resulting network, over all possible shortcuts. Two major variants of the problem arise, depending on how the shortcut is inserted into the network. In the first variant, which we call highway model, the crossings between the shortcut and the network edges do not form new network vertices: a path can only enter and leave the shortcut through its endpoints. In contrast, in the planar model, every crossing creates a new vertex, which can be used by paths in the network. Figure 1 illustrates some of the differences between the two models. In this work, we focus on the planar model. This model is more general, and is applicable to a wider range of situations, like the addition of segments to road or pedestrian networks. From a theoretical point of view, the difference between the highway and planar model is important. The latter results in more complex problems, since the fact that a shortcut can be used only in part, implies that the structural information on how the distances in the network change after adding a segment is more difficult to maintain. Moreover, as we show in this work, many intuitive properties of shortcuts do not hold in the planar model anymore. D. Garijo, A. Márquez, N. Rodríguez, and R. I. Silveira 15:3 Related work. There has been a considerable amount of work devoted to the graph version of the Optimalk -Augmentation problem. Due to space constraints, we only discuss the geometric version of the problem (i.e., where the graph is embedded in the plane), and where the continuous diameter is used (i.e., the distances are taken over all pairs of points in the network, as opposed to considering only pairs of vertices). Most attention to the problem studied here has been on the highway model, for certain classes of graphs. For paths, De Carufel et al. [6] gave an algorithm to find an optimal shortcut in linear time, and also optimal pairs of shortcuts (i.e., k = 2) for convex cycles. Trees have been studied in a recent follow-up work [7], which presents an algorithm to find an optimal shortcut for a tree of size n in O ( nlog n )time. For circles, very recently Bae et al. [1] have analyzed how to add up to seven shortcuts in an optimal way. For the planar model much less is known. Yang [15] designed three different approximation algorithms to compute an optimal shortcut for certain types of paths. Cáceres et al. [5] were the first to consider general networks, for which they show that one can find a shortcut in polynomial time if one exists (note that there are networks whose diameter cannot be improved by adding only one segment, e.g., a cycle), but they do not look for an optimal one. Our results. We present the first study of optimal shortcuts in the planar model for general networks, and several improved results for paths. An important contribution of our work is to highlight many important differences between the highway and planar models, the latter resulting in considerably harder problems. In Section 2, we give a polynomial time algorithm to compute an optimal shortcut if one exists. Moreover, we present a discretization of the problem that immediately leads to an approximation algorithm for general networks, generalizing an existing result for paths [15]. Section 3 focuses on paths: we first show that the diameter of a path network after adding a shortcut can be computed in Θ( n )time. Then we improve the method of Section 2 for shortcuts of any fixed direction. Finally, we study simple shortcuts, a variant that has been studied before, which has applications in settings where the added edge cannot intersect the existing network. Due to space limitations, most proofs are not included here; they can be found in [12]. 1.1 Preliminaries We will use N = ( V ( N ) , E ( N )) to denote a network with n vertices, and N` for its locus, the set of all points of the Euclidean plane that are on N . Thus, N` is treated indistinctly as a network or as a closed point set. When N` is a path, we use P` instead of N` . Further, we write a∈ N`for a point aon N`, and V(N)⊂ N`. Apath P connecting two points a, b on N` is a sequence au1. . . ukb such that u1u2 , . . . , uk−1uk∈E ( N ), a is a point on an edge ( 6 = u1u2 ) incident to u1 , and b is a point on an edge ( 6 = uk−1uk ) incident to uk . We use |P| to denote the length of P , i.e., the sum of the lengths of all edges uiui+1 plus the lengths of the segments au1 and buk . The length of a shortest path from a to b is the distance between a and b on N` . This distance is written as dN` ( a, b ) or d ( a, b )when the network is clear, and whenever ab /∈E ( N` ), it is larger than |ab| , the Euclidean distance between the points. The eccentricity of a point a∈ N` is ecc( a ) = maxb∈N`d ( a, b ), and the diameter of N` is diam ( N` ) = maxa∈N`ecc ( a ) . Two points a, b ∈ N` are diametral whenever d ( a, b ) = diam ( N` ), and a shortest path connecting aand bis then called diametral path. The diameter of N` , diam ( N` ), can be computed in polynomial time [5,8]. Furthermore, the diametral pairs of N` are either (i) two vertices, (ii) two points on distinct non-pendant ISAAC 2018 15:4 Computing Optimal Shortcuts for Networks edges 1 , or (iii) a pendant vertex and a point on a non-pendant edge [5, Lemma 6]. Thus, with some abuse of notation, in Section 2, we will say that a diametral pair α, β ∈V ( N ) ∪E ( N ) may be (i) vertex-vertex, (ii) edge-edge, or (iii) vertex-edge. Ashortcut for N` is a segment s with endpoints on N` such that diam ( N`∪s ) <diam ( N` ) . We say that shortcut s is simple if its two endpoints are the only intersection points with N` , and s is maximal if it is the intersection of a line and ( N`∪s ), i.e., s = ( N`∪s ) ∩` , for some line ` . A shortcut is optimal if it minimizes diam ( N`∪s )among all shortcuts s for N` . 2 General networks The main result in [5] states that one can always determine in polynomial time whether a network N` has a shortcut (and compute one, in case of existence). In this section, we first prove the analogous result for optimal shortcuts. Our proof uses some ideas in [5] but captures the property of being optimal with a much shorter argument based on some functions defined in Lemma 1 below. Let α, β ∈V ( N ) ∪E ( N ), and let e = uv and e0 = u0v0 be two edges of N . When α is an edge, we use ecc ( u, α )to indicate the maximum distance from u to the points on α (analogous for β and the remaining endpoints of e and e0 ); if α is a vertex, ecc ( u, α ) = d ( u, α ). In general, ecc(α, β) = maxt∈α,z∈βd(t, z). ILemma 1. Let y = ax + b be a line intersecting edges e = uv and e0 = u0v0 on points p and q , respectively, and let α, β ∈V ( N ) ∪E ( N ). For each pair ( w, z )with w∈ {u, v} and z∈ {u0, v0}, function fw,z α,β (a, b) = ecc(w, α) + |wp|+|pq|+|qz|+ ecc(z, β)is linear in b. The following theorem is the optimality version of Theorem 8 in [5]. ITheorem 2. It is possible to determine in polynomial time whether a network N` admits an optimal shortcut, and compute one in case of existence. It should be noted that the approach that leads to the preceding result, albeit polynomial, has a very high running time. A direct implementation involves O ( n4 )functions fw,z α,β ( a, b ) that must be computed, and this has to be done for O ( n4 )different cases. Moreover, each evaluation of fw,z α,β ( a, b )takes O ( n2 )time. All in all, its running time would add up to O ( n10 ). 2.1 Discretizing the set of possible shortcuts: approximation In light of the high running time of the previous approach, it becomes interesting to look for faster approximation algorithms. Moreover, given the continuous nature of the problem, it is natural to wonder to what extent the problem can be discretized. In other words, how good can shortcuts be if we restrict them to some discrete collection of segments? The most natural choice for such a collection is probably the segments defined by pairs of vertices u, v of N` , but this choice can lead to poor results, as the example in Figure 2(left) shows. In some cases, one can do better by considering the maximal extensions of the segments uv (i.e., the largest segment through uv with endpoints on N` ), as Yang [15] did to obtain an additive approximation for paths. Unfortunately, as Figure 2(right) shows, maximal extensions do not work anymore as soon as N` is a tree. However, in this section, we show that if one considers all extensions of segments defined by two vertices of N` , then it is possible to guarantee an approximation factor for general networks. 1An edge uv ∈E(N)is pendant if either uor vis a pendant vertex (i.e., has degree 1). D. Garijo, A. Márquez, N. Rodríguez, and R. I. Silveira 15:5 a b c e d a b Figure 2 Left: the optimal shortcut is the dashed purple segment, which contains the blue segment. That blue segment (and any other segment between two vertices) gives a larger diameter as points a and b are diametral for both segments. Right: the original diameter is given by the orange path. The best shortcut connecting two vertices is bc . Contrary to intuition, extending bc to bd worsens the diameter, which becomes given by points aand e(pink path). p q u v v0 C1 C2 s0 a b ≤ρ ≤ρ s u0 p q u v v0 C1 C2 s0 s u0 Figure 3 Left: approximating a shortcut swith a segment s0∈ S2. Right: using s0instead sto go from ato bcauses a detour of at most 4ρ(purple path). Let S be the infinite set of segments with endpoints in N` , and let S2⊂ S be the subset of segments of S that contain two vertices of N` . The following proposition states that set S2is an approximation of S. IProposition 3. Let ρ be largest edge length in N` . Then, mins∈S diam ( N`∪s ) ≤ mins∈S2diam(N`∪s)≤mins∈S diam(N`∪s)+4ρ. Proof. The first inequality is straightforward. For the second, it suffices to prove that given s=pq ∈ S \ S2there exists s0∈ S2such that diam(N`∪s0)≤diam(N`∪s)+4ρ. Segment s may cross several faces of N` , refer to Figure 3. Consider the first and the last ones, say F1 and F2 , together with the vertices of N` that are adjacent to p and q in those faces: u, v in F1 and u0, v0 in F2 . Let V1 be the vertices of N` in the quadrilateral upqu0 (including u and u0 ), and let C1 be its convex hull. Analogously, we have V2 and C2 for the quadrilateral vpqv0 . Note that both convex hulls may have one point in common. Extending one of the common internal tangents of C1 and C2 gives rise to a segment s0 with endpoints on two of the edges of F1 and F2 containing points p and q . Observe that s0 intersects all the edges of N` that are crossed by s . Thus, this construction allows us to show that, for any two points a, b ∈ N` , the length of the shortest path between a and b that uses s0 is at most 4 ρ plus the corresponding length but using s . To do this, we first use the triangle inequality to compare the lengths of the used portions of segments s and s0 , which gives a difference of 2 ρ , and then we add the two distances indicated in Figure 3(right). A similar argument is used for a∈s0and b∈ N`.J The collection S2 is finite but quite large, it has size O ( n4 ), which gives a time complexity of O ( n6 )to compute the optimal among the segments in S2 (there are O ( n2 )possible extensions per each pair of vertices, and for each of them one needs to compute the diameter from scratch in O(n2)time [13]). ISAAC 2018 15:6 Computing Optimal Shortcuts for Networks u v d(u, u0) |u0v0| d(v, v0) v u s t p1 Figure 4 Left: function Φ st uv . Right: if the distance from p1 to st decreases when adding s0 = uv , then, after adding s1=up1it will become even smaller. We would like to find a small subset of S2 that preserves the property in Proposition 3. Ideally, we would like to consider not all the extensions of a segment with endpoints in V ( N` )(that is exactly S2 ), but only the best extension for each segment. Unfortunately, this appears rather difficult: already for a tree with a single vertex of degree larger than two, it may happen that an extension of a segment gives a worse diameter than the segment itself, see Figure 2(right). However, we show next that we can speed-up the computation of the diameter for each extension in S2, saving a nearly-linear factor in the total running time. Given a segment s0 = p0q0 , let r be the ray starting at p0 and containing s0 , and let P = p0, p1, . . . , pk be the sorted list of intersection points of r with edges of N` (note that q0 = pj for some j ). Segments si = p0pi are called extensions of s0 to the right; the extensions to the left are defined similarly. Next we show how to speed-up the re-computation of the diameter of N`∪si as we insert s0, s1,...sk , in that order. To that end, we split the re-computation of distances into two parts: distances from points on si to points on N` , and distances (in N`∪si)between two points on N`. ILemma 4. Let u and v be vertices of N` . It is possible to compute the eccentricities of all the extensions to the right of segment uv in O(n2)time. Proof. As a preprocessing step, we store the distances from each vertex to all the other edges and the point at each edge attaining that maximum distance. This allows us to construct the functions Φ st uv : [0 , 1] →R+ that encode the information of the maximum distance from each point on an edge uv to an edge st (see [13, Theorem 2] for their analytic expression). Their shape is as follows – see also Figure 4(left): let u0 and v0 be the farthest points to, respectively, u and v in edge st . Function Φ st uv increases uniformly from 0and from 1until the distance between both lines equals the distance between u0 and v0 , at that moment it stabilizes horizontally. Thus, knowing the farthest points u0 and v0 to u and v in the segment st (and the distance between them), it is possible to build Φst uv in constant time. The main idea of the proof of this lemma is that it is possible to update each map Φ st uv for each extension of a segment again in constant time. Observe that Φ st uv encloses the information of the largest distance from any point of uv to the segment st. In a first step, we insert segment s0 = uv . As u and v are in N` , they belong to some edges g and g0 , and we use the information of Φ st g and Φ st g0 to find the largest distance from u and v to st (in N` ). With that information, we compute Φ st uv in constant time. Thus, the maximum eccentricity of the edge s0=uv can be computed in linear time. Observe that building the map Φ st uv it is possible to detect if ecc ( v, st )changes when adding s0 , so, we update the values of the distances from vp0 to all the other edges, and the point on each edge giving that maximum distance (again, in linear time). D. Garijo, A. Márquez, N. Rodríguez, and R. I. Silveira 15:7 s0 s1 s2 s3 s4 s5 s6 s7 N(0) E(0) Figure 5 For each segment extension, we consider two values: E ( i )– maximum eccentricity on si – (blue points), and N ( i )– maximum eccentricity in N`∪si for points in N` – (red squares). For each si , the diameter of N`∪si is given by the maximum of these two values. Only the blue points with green arrows must be tested (they are the maximal blue points). Of course, the addition of s0 can change the eccentricity of p1 with respect to some other edge (and the same with any of the other pi ’s), but we will see that we do not need to update that information at this moment. Indeed, if the distance from p1 to st changes when adding s0 , it can only decrease. Then, the addition of s1 is going to make it even smaller – see Figure 4(right). Thus, in step i , we only need to update the information of the new vertex pi, since by adding si, the value of pi+1 is going to be updated. J ILemma 5. Let u and v be vertices of N` . It is possible to find the extension s of segment uv that minimizes diam(N`∪s)in O(n3log n)time. Proof. The value of diam ( N`∪s )can be computed by calculating the eccentricity of segment s and comparing with the eccentricities in N`∪s of all the points in N` . Thus, for each extension s0 of uv to the left, we compute the eccentricities E ( i )of all its extensions si to the right using Lemma 4, in O ( n2 )time. Let N ( i )be the maximum distance in N`∪si between pairs of points in N`. Our goal is to compute minimax{E(i), N(i)}. Since N(i)is a decreasing function as i grows, we do not need to compute N ( i )for all values of i , but only for those i for which E ( i )is maximal: there is no j > i with E ( j ) < E ( i )(see Figure 5). Therefore, we can look for that minimum by binary search, computing N ( i )only for O ( log n ) values of i . Using [10], we can update the distances between vertices in quadratic time and then compute N ( i )also in quadratic time (the distance between pairs edge–edge and vertex-edge can be computed in constant time knowing the distance between vertices), giving a total time of O(n3log n).J We thus obtain the main result in this section. ITheorem 6. Let ρ be the length of a longest edge of a network N` . Then, it is possible to find a segment s0such that diam(N`∪s0)≤mins∈S diam(N`∪s)+4ρin O(n5log n)time. This result immediately gives a simple approximation algorithm: subdivide each edge in N` by adding dummy vertices such that the largest resulting edge length is ε . Then the previous theorem implies the following result, which is a generalization to general networks of the result for paths presented in [15, Theorem 8.1]. ICorollary 7. Let ρ be the length of a longest edge of a network N` . Then, for any 0 <ε< ρ/ 2it is possible to find a segment s0 such that diam ( N`∪s0 ) ≤mins∈S diam ( N`∪s ) + 4 ε in O((nρ/ε)5log(nρ)) time. ISAAC 2018 15:8 Computing Optimal Shortcuts for Networks o p q pi qj Figure 6 Schematic construction showing that the insertion of a shortcut pq can create Θ( n2 ) diametral pairs. The distance between the top of one spike on the left of o and one on its right, like piand qj, can be made to be |pq|, and equal to the diameter of P`∪pq. 3 Path networks In the remaining, we focus on networks that are paths. To illustrate the complexity of this seemingly simple setting, we begin by observing that the insertion of a shortcut to a path can create a quadratic number of diametral pairs; as illustrated in the construction in Figure 6. It consists of Θ( n )spikes placed symmetrically with respect to the midpoint of the shortcut, denoted with o . After inserting pq , each spike forms a face with a cycle of length roughly twice its height. The spikes are spaced by one unit each, while their heights are set such that the distance from o to the top of the spike is always the same, namely |pq|/ 2. In this way, for any two spike tops pi and qj on the left and right of o , respectively, the distance between piand pjon P`∪pq is always equal to |pq|, which is also the diameter of P`∪pq. 3.1 Diameter after inserting a shortcut The diameter of P` can be immediately computed in linear time, however, the addition of a shortcut scan create a linear number of new faces, thus in principle it is not clear whether diam( P`∪ s) can be computed in linear time, i.e., without computing the diameter between each pair of faces. The main result in this section is that this is still possible. Path networks have the nice property that the maximal extension of an optimal shortcut is also optimal [15]. Thus, we can assume that s = pq is maximal and horizontal. The insertion of s splits P` into polygonal chains, which bound the different faces created. Our goal is to compute the pair of chains that have maximum distance in P`∪s. We number the polygonal chains from 0to m in the order of their left endpoints from left to right along s (using right endpoints to disambiguate). Except for possibly the first and last, all chains have both endpoints on s . For the i th chain Ci , we denote its left and right endpoints by pl i and pr i , respectively. If the first vertex of P` is not on s , we consider the path from its first vertex to the first intersection of P` with s as a degenerate loop chain with equal left and right endpoints on s(analogous for the last vertex of P`). Refer to Figure 7. Let |Ci| be the length of Ci , let Li = |ppl i| and Ri = |pr iq| , and let si denote the segment pl ipr i . Note that Ci∪si forms a cycle. We use Di for the distance on P`∪s from pl i to its furthest point ¯pl ion Ci∪si(i.e., Diis the semiperimeter of Ci∪si). We make some basic observations about the diameter between two chains, depending on their relative position. They reveal a key property of the problem: the linear ordering between chains induced by sdefines uniquely how the diameter between two chains is achieved. IObservation 8 (Disjoint chains) . Let Ci, Cj be two chains of P`∪s with si∩sj = ∅ and si to the left of sj . The diameter of Ci∪pl ipr j∪Cj is Di + |pr ipl j| + Dj = Di + Ri−Rj−|sj| + Dj . D. Garijo, A. Márquez, N. Rodríguez, and R. I. Silveira 15:9 p q C1 C2 C3 C4 C6 C5 C7 C8 p q C0 pl 3 pr 3 C3 s3 R3 L3 ¯pl 3 ¯pr 3 D3 P` C9 C3 Figure 7 Left: chains created by s ; C0 and C8 are degenerate chains. Right: detail for chain C3 , showing the cycle formed by C3∪s3. Thick lines are used here to denote distances. IObservation 9 (Nested chains) . Let Ci, Cj be two chains of P`∪s with sj⊂si . The diameter of Ci∪si∪Cj is 1 2 ( |Ci| + |pl ipl j| + |pr ipr j| + |Cj| ) = 1 2 ( |Ci| + Lj−Li + Rj−Ri + |Cj| ). IObservation 10 (Overlapping chains) . Let Ci, Cj be two chains of P`∪s with si∩sj6 = ∅ , pl i/∈sj and pr j/∈si . The diameter of Ci∪pl ipr j∪Cj is 1 2 ( |Ci| + |pl ipl j| + |pr ipr j| + |Cj| ) = 1 2(|Ci|+Lj−Li+Ri−Rj+|Cj|). Note that, while in the case of disjoint chains the diameter is achieved by a unique pair of points, that is not the case of nested and overlapping chains, for which an infinite number of diametral pairs of points may exist. Also, observe that expressions in Obs. 9 and Obs. 10 are the same except for adding up either Rj−Ri or Ri−Rj . This difference only exists to differentiate between the two possible orders of the right endpoints of the two chains. The algorithm for computing diam( P`∪ s) in linear time starts by going along P` and computing all intersections with s in the order of P` . Then we apply a linear-time algorithm for Jordan sorting [11] to obtain the intersections in the order along s , say, from left to right. Within the same running time we can compute Ck and sk . Next, we sweep the endpoints of the chains along s to compute, for each chain Ck , its furthest chain from the ones seen so far. To that end, certain information is computed and stored: 1. The furthest chain from Ck to the left, given by arg max0≤i<k αi , where αi = Di + Ri . Similarly, we store the furthest chain to the right. 2. The furthest chain nested inside Ck . This is given by arg maxj∈Nkβj , where βj = |Cj|+Lj+Rjand Nkis the set of indices of all chains nested inside Ck. 3. The furthest chain with one endpoint in Ck , and one outside: given by arg maxj∈Or kγj , where γj = |Cj| + Lj−Rj and Or k is the set of indices of all overlapping chains with their left endpoint inside Ck and their right endpoint outside. Similarly, we store those with their left endpoints outside and the right one inside of sk. The computation of the information in (1) is straightforward when sweeping along s , say, from left to right. We just maintain the largest value of αi seen so far as we sweep. The case of nested or overlapping chains, which is explained next, is more complicated because one needs the maximum restricted to those chains that are contained or overlap with Ck . For that reason, what we will do is to store βj and γj values for all chain endpoints. Suppose that Ci starts to the left of Cj (the other case is analogous). We use a data structure for range minimum queries [2,3]. This allows to preprocess an array A in linear time in order to find the maximum value in any subarray A [ a, b ]in O (1) time. In our context, we need two such data structures. We use arrays An and Ao to store the maximum β and γ values defined above for the chains that are nested and overlapping, respectively. Each array has one position for each endpoint of a chain, thus 2 m in total. The positions are as they appear sorted along s , from left to right. Refer to Figure 8. For a chain Cj , the position corresponding to its left endpoint has a value equal to βj in the array An , and value γj in array Ao . The values corresponding to the right endpoints of the chains are not used, i.e., they have value −∞ , in both arrays. At each array position, we also store pointers to the corresponding chains. ISAAC 2018