Computing optimal shortcuts for networks
Delia Garijo Alberto Márquez Natalia Rodríguez Rodrigo I. Silveira



Transiting Exoplanet Monitoring Project (TEMP). I. Refined System Parameters and Transit Timing Variations of HAT-P-29b
    Gregory Laughlin
    
=======================================================================================================================



footnote1  Departamento de Matemática Aplicada I, Universidad de Sevilla, Avda. Reina Mercedes s/n, 41012, Sevilla, Spain. Emails: {dgarijo, almar}@us.es
footnote1 Departamento de Computación, Universidad de Buenos Aires, Pabellón I, Ciudad Universitaria, C1428EGA, Buenos Aires, Argentina. Email: nrodriguez@dc.uba.ar
footnote1 Corresponding author. Departament de Matemàtiques, Universitat Politècnica de Catalunya, Jordi Girona 1-3, 08034, Barcelona, 
Spain. Email: rodrigo.silveira@upc.edu




We study augmenting a plane Euclidean network with a segment, called a shortcut, to minimize the largest distance between any two points along the edges of the resulting network. Problems of this type have received considerable attention recently, mostly for discrete variants of the problem.
We consider a fully continuous setting, where the problem of computing distances and placing a shortcut is much harder as all points on the network, instead of only the vertices, must be taken into account. We present the first results on the computation of optimal shortcuts for general networks in this model: a polynomial time algorithm and a discretization of the problem that leads to an approximation algorithm. We also improve the general method for networks that are paths, restricted to two types of shortcuts: those with a fixed orientation and simple shortcuts.












§ 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 example, 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 <cit.>.

In fact, due to the many and varied applications of this type of network optimization problem, there is a vast amount of work in areas like operational research and  transportation science, which deals with different aspects of the so-called Network Design Problem: deciding how to add or modify network connections (e.g., roadway segments) in order to improve aspects such as travel time, capacity or connectivity (see, for instance <cit.>).

One of the simplest approaches to model networks like the ones above is as a geometric network: an undirected graph whose vertices are points in ℝ^2 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 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 certain transportation networks, can be reasonably  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 paper, we focus on the problem of adding segments to a network in order to improve its diameter.
This can be seen as a variant of the Diameter-Optimal-k-Augmentation problem for edge-weighted geometric graphs, which consists in inserting k additional edges into an edge-weighted geometric graph, while minimizing the largest distance in the resulting graph.
While in most augmentation problems the additional edges are inserted between two existing vertices of the graph, we consider a continuous version,  for k=1: the endpoints of our inserted segment, called shortcut, can be any two points (not necessarily vertices) on the network.  In addition, our goal is to find an optimal shortcut: one minimizing the diameter of the resulting network, over all possible shortcuts. 
We point out here that a segment will be considered a shortcut only if its insertion improves the diameter of the resulting network. 
The fact that all points on the network must be taken into account turn the computation of distances and the placement of a shortcut into a much harder problem.
For instance, since the resulting network also includes the points on the shortcut inserted, we can run into the somewhat counterintuitive situation that the insertion of a segment  worsens the diameter of the resulting network.


In the continuous setting, 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 <ref> illustrates the difference between the two models.





We deal in this paper with optimal shortcuts in 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.

Related work

The motivation of this work lies on the well-studied Road Network Design Problem, which has been subject of much attention in many areas, including operational research, transport geography, and engineering, and has been recognized as one of the most difficult and challenging problems in transport <cit.>.
We refer to <cit.> for relevant surveys on this general problem, for their urban and road variants.
The network design problem is extremely complex, involving plenty of different aspects such as travel demand, road capacity, traffic flow, and congestion.
In this work we focus on a much simplified geometric scenario, with the goal of exploring some of the algorithmic aspects of this complex problem. 
For that reason, our problem is mostly related graph augmentation problems, and in particular to those where the graph is geometric.

There has been a considerable amount of work devoted to the non-geometric version of the Optimal-k-Augmentation problem, see for instance <cit.>. However, there are very few results on augmentation problems over plane geometric graphs. Farshi et al. <cit.> considered plane Euclidean networks in ℝ^d and designed approximation algorithms to minimize the dilation when inserting one edge. The analogous problem for networks embedded in a metric space is studied in <cit.>. See the survey <cit.> for more on augmentation problems over plane geometric graphs.

In the geometric and continuous setting, most known results on the problem studied in this paper consider the highway model and certain classes of graphs. For paths, De Carufel et al. <cit.> 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 <cit.>, 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. <cit.> have analyzed how to add up to seven shortcuts in an optimal way.

For the planar model much lees is known. Yang <cit.> designed three different approximation algorithms to compute an optimal shortcut for certain types of paths. Cáceres et al. <cit.> were the first to deal with general networks, for which they show that one can find a shortcut in polynomial time if one exists, but they do not compute an optimal one. Note that there are networks whose diameter cannot be improved by adding only one segment (e.g., a cycle).


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 <ref>, we give a polynomial time algorithm to compute an optimal shortcut, if one exists, for a general network.
Moreover, we present a discretization of the problem that immediately leads to an approximation algorithm, generalizing an existing result for paths <cit.>.
Section <ref> 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 general method of Section <ref> for shortcuts of any fixed direction.
Finally, we study simple shortcuts, a variant that has been considered before <cit.>, which has applications in settings where the added edge cannot intersect the existing network. We show that an optimal simple shortcut can be found, if one exists, in O(n^2) time.





 §.§ Preliminaries



We will use 𝒩=(V(𝒩), E(𝒩)) to denote a network with n vertices, and   for its locus, the set of all points of the Euclidean plane that are on 𝒩. Thus,
 is treated indistinctly as a network or as a closed point set. When  is a path, we use  instead of . Further, we write a∈ for a point a on , and V(𝒩)⊂.

A path P between two points a,b on  is a sequence au_1… u_kb where u_1u_2,…,u_k-1u_k∈ E(𝒩), a is a point on an edge (≠ u_1u_2) incident to u_1, and b is a point on an edge (≠ u_k-1u_k) incident to u_k. We use |P| to denote the length of P, i.e., the sum of the lengths of all edges u_iu_i+1 plus the lengths of the segments au_1 and bu_k.
The length of a shortest path from a to b is the distance between a and b on N_ℓ. This distance is written as d_N_ℓ(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∈ is ecc(a)=max_b ∈ d(a,b), and the diameter of , also called generalized or continuous diameter of 𝒩 <cit.>, is diam() = max_a∈ ecc(a). Two points a,b ∈ are diametral whenever d(a,b)= diam(), and a shortest path connecting a and b is then called diametral path.

The diameter of , diam(), can be computed in quadratic time <cit.>.
Furthermore, the diametral pairs of  are either (i) two vertices, (ii) two points on distinct non-pendant edges[An edge uv∈ E(𝒩) is pendant if either u or v is a pendant vertex (i.e., has degree 1).], or (iii) a pendant vertex and a point on a non-pendant edge <cit.>. Thus, with some abuse of notation, in Section <ref>, we will say that a diametral pair α,β∈ V(𝒩)∪ E(𝒩) may be (i) vertex-vertex, (ii) edge-edge, or (iii) vertex-edge.

A shortcut for  is a segment s with endpoints on  such that its insertion improves the diameter of the resulting network, that is, diam(∪ s)< diam().
We say that shortcut s is simple if its two endpoints are the only intersection points with , and s is maximal if it is the intersection of a line and (∪ s), i.e., s=(∪ s) ∩ℓ, for some line ℓ; see Figure <ref>(b) for an example of a non-simple and maximal shortcut. A shortcut is optimal if it minimizes diam(∪ s) among all shortcuts s for .




§ GENERAL NETWORKS


The main result in <cit.> states that one can always determine in polynomial time whether a network  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 <cit.> but captures the property of being optimal with a much shorter argument based on some functions defined in Lemma <ref> below.

Let α,β∈ V(𝒩)∪ E(𝒩), and let e=uv and e'=u'v' be two edges of 𝒩. 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 e'); if α is a vertex, ecc(u,α)=d(u,α). In general, ecc(α,β)= max_t∈α, z∈β d(t,z).



Let y=ax+b be a line intersecting edges e=uv and e'=u'v' on points p and q, respectively, and let α,β∈ V(𝒩)∪ E(𝒩). For each pair (w,z) with w∈{u,v} and z∈{u',v'}, function f_α,β^w,z(a,b)= ecc(w,α)+|wp|+|pq|+|qz|+ ecc(z,β) is linear in b.



 The only term in the expression of f_α,β^w,z(a,b) that is not linear is |pq| (the values ecc(w,α) and ecc(z,β) are fixed, and |wp| and |qz| are linear). Thus, it suffices to prove that there is a linear change when line y=ax+b is moved parallel to itself (changing slightly b), which is a straightforward consequence of the Side Splitter Theorem.


The following theorem is the optimality version of Theorem 8 in <cit.>.



It is possible to determine in polynomial time whether a network 𝒩_ℓ admits an optimal shortcut, and compute one in case of existence.





As explained in <cit.>, the search space can be split into a polynomial number of regions; we include a description here for the sake of completeness.

Two lines are equivalent if the half-planes to the right (resp., to the left) that they define contain the same vertices of .
There are O(n^2) classes of equivalent lines as one can associate four lines to every pair of vertices u,v, say,
lines m_u^+v^+ and m_u^-v^- parallel to segment uv and leaving u and v in the same half-plane, and lines m_u^+v^-, m_u^-v^+ leaving u,v in different half-planes. These lines must be placed sufficiently close to u and v as Figure <ref>(a) shows. Thus, every class of equivalent lines has a representative in the set {m_u^+v^+, m_u^-v^-, m_u^+v^-, m_u^-v^+  |   u,v∈ V(𝒩)}, whose cardinality is O(n^2).

Given a line m that crosses two fixed edges e,e' ∈ E(𝒩), let  P_e,e'(m) be the set of  lines  equivalent to m. This set can be seen as the set of segments determined by the corresponding intersections of the lines in P_e,e'(m) with edges e and e'; thus, the region of the plane that P_e,e'(m) defines has the shape of an hourglass <cit.>, see Figure <ref>(b). By the argument above, there are  O(n^2) regions P_e,e'(m) per each pair of edges e,e'∈ E(𝒩), which gives a total of O(n^4) regions.




 Consider a line r ≡ y=ax+b in a region P_e,e'(m) and the set I={e=e_0, e_1, …, e_k, e_k+1=e'} of edges that it intersects in between e and e'; let e_i=u_iv_i and p_i=r∩ e_i. For a fixed diametral pair α, β∈ V(𝒩)∪ E(𝒩), a function of the type f_α,β^w,z(a,b) (see Lemma <ref>) with w∈{u_i,v_i} and z∈{u_j,v_j}, 0≤ i≠ j≤ k+1, describes ecc(α,β) when using a path that passes through vertices w, z and contains segment p_ip_j.

Geometrically, functions f_α,β^w,z(a,b) can be viewed as lines in the (b, f_α,β^w,z(a,b))-plane. By Lemma <ref>, they are linear in b and so, in order to compute them in an hourglass-shaped region P_e,e'(m), it suffices to obtain their evaluation only in those values of (a,b) corresponding to the lines that form the boundary of the region, which is defined by O(n) vertices.
 Note that for fixed α,β, w,z, all functions f_α,β^w,z(a,b) have an important part in common, as illustrated in Figure <ref>. Thus, the common values of the distances from α to z and from w to β only need to be computed once, which can be done in quadratic time. Each function will be different only in the portion of the path from w to z that depends on the segment defined by (a,b), and this distance can be computed in constant time. This results in O(n^6) running time for computing the O(n^4) functions f_α,β^w,z(a,b) in a region P_e,e'(m).




An optimal shortcut for  in 𝒫_e,e'(m) is given by the minimum of the upper envelope of the set of lines f_α,β^w,z(a,b). Note that shortcuts must satisfy that ecc(t)< diam() for every t∈ s, since, by definition, any shortcut improves the diameter of , and so all segments p_ip_j must be included in the set of O(n^2) diametral pairs α, β∈ V(𝒩)∪ E(𝒩). Applying the same argument to the O(n^4) regions 𝒫_e,e'(m), the result follows.
 


The importance of the preceding approach relies in the fact that the problem is polynomial.
However, its running time is very high as it involves O(n^4) functions f_α,β^w,z(a,b) that must be computed, and this has to be done for each of the O(n^4) regions 𝒫_e,e'(m).
Moreover, each evaluation of f_α,β^w,z(a,b) takes O(n^2) time.
All in all, its running time amounts to O(n^10).





 §.§ 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 of , but this choice can lead to poor results, as the example in   <ref>(a) shows.
In some cases, one can do better by considering the maximal extensions of such segments: the maximal extension of a segment s is the longest segment containing s that has both endpoints on edges of .
Yang <cit.> showed that for paths, it is enough to consider only maximal extensions, a fact that allowed him to obtain an additive approximation for this class of graphs.
Unfortunately, as  <ref>(b) illustrates, maximal extensions do not work anymore as soon as  is a tree: an extension of a segment can lead to a worse diameter than the segment itself.
However, in this section, we show that if one
considers all extensions of segments defined by two vertices of , then it is possible to guarantee
an approximation factor for general networks.




Let 𝒮 be the infinite set of segments with endpoints in , and let 𝒮_2 ⊂𝒮 be the subset of segments of 𝒮 that contain two vertices of . The following proposition states that set 𝒮_2 is an approximation of 𝒮.


 
Let ρ be the largest edge length in . Then, 
    min_s ∈𝒮 diam(∪ s) ≤min_s ∈𝒮_2 diam(∪ s) ≤min_s ∈𝒮 diam(∪ s)+4ρ.




The first inequality is straightforward. For the second, it suffices to prove that given s=pq ∈𝒮 there exists s' ∈𝒮_2 such that diam(∪ s') ≤ diam(∪ s)+4ρ.

Segment s may cross several faces of , refer to  <ref>(a).

Consider the first and the last ones, say ℱ_1 and ℱ_2, together with the vertices of  that are adjacent to p and q in those faces: u,v in ℱ_1 and u',v' in ℱ_2. Let V_1 be the vertices of  in the quadrilateral upqu' (including u and u'), and let C_1 be its convex hull. Analogously, we have V_2 and C_2 for the quadrilateral vpqv'. Note that both convex hulls may have one point in common. Extend one of the common internal tangents of C_1 and C_2 giving rise to a segment s' with endpoints on two of the edges of ℱ_1 and ℱ_2 containing points p and q. Observe that s' intersects all the edges of  that are crossed by s. This construction allows us to show that, for any two points a,b∈, the length of the shortest path between a and b that uses s' 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 s', which gives a difference of 2ρ, and then we add the two distances indicated in  <ref>(b). A similar argument is used for a∈ s' and b∈.




The collection 𝒮_2 is finite but quite large, it has size O(n^4), which gives a time complexity of O(n^6) to compute the optimal among the segments in 𝒮_2. Indeed, there are O(n^2) possible extensions per each pair of vertices, and for each of them one needs to compute the diameter from scratch in O(n^2) time <cit.>. 

We would like to find a small subset of 𝒮_2 that preserves the property in Proposition <ref>. Ideally, we would like to consider not all the extensions of a segment with endpoints in V() (that is exactly  𝒮_2), but only the best extension for each segment. 
Unfortunately, this appears rather difficult, as extensions of a segment do not seem to behave monotonically: 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  <ref>(b).
However, we show next that we can speed-up the computation of the diameter for each extension in 𝒮_2, saving a nearly-linear factor in the total running time.

Given a segment s'=p'q', let r be the ray starting at p' and containing s', and let 𝒫=p_0, p_1, … , p_k be the sorted list of intersection points of r with edges of . Segments s_i=p'p_i are called extensions of s' 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 ∪ s_i as we insert s_0,s_1, … s_k, in that order.
To that end, we split the re-computation of distances into two parts:  distances from points on s_i to points on ,
and distances (in ∪ s_i) between two points on .




 
Let u and v be vertices of . It is possible to compute the eccentricities of all the extensions to the right  of segment uv in O(n^2) time.



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 Φ_uv^st:[0,1] →ℝ^+ that encode the information of the maximum distance from each point on an edge uv to an edge st (see <cit.>). Their
shape is as follows (see  <ref>(a)).

Let u' and v' be the farthest points to, respectively, u and v in edge st.
Function Φ_uv^st increases uniformly from 0 and from 1 until the distance between both lines equals the distance between u' and v', at that moment it stabilizes horizontally. 

Therefore, knowing the farthest points u' and v' to u and v in the segment st (and the distance between them), it is possible to build Φ_uv^st in constant time. The main idea of the proof is that it is also possible to update each map Φ_uv^st for each extension of a segment in constant time. Observe that Φ_uv^st encloses the information of the largest distance from any point of uv to the segment st.

In a first step, we consider the addition of the segment s_0=uv. As u and v are on the network , they belong to some edges g and g', and we use the information of Φ_g^st and Φ_g'^st to find the largest distance from u and v to st (in the network ). With that information, we compute Φ_uv^st in constant time.
Thus, the maximum eccentricity of the edge s_0=uv can be computed in linear time.

 Note that, by building the map Φ_uv^st, it is possible to detect whether vertex v changes its eccentricity with respect to st. Thus, we update the values of the distances from vp_0 to all the other edges, and the point on each edge giving that maximum distance (again, in linear time).

The addition of s_0 may change the eccentricity of p_1 with respect to some other edge (and the same with any of the other p_i's), but we do not need to update that information at this moment.
Indeed, if the distance from p_1 to st changes when adding s_0, it can only decrease.
Hence, the addition of s_1 will make that distance even smaller; see  <ref>(b). Thus, in step i, we only need to update the information of the new vertex p_i, since by adding s_i, the value of p_i+1 will be updated.


 
Let u and v be vertices of . It is possible to find the extension s of segment uv that minimizes diam(∪ s) in O(n^3 log n) time.


The value of diam(∪ s) can be computed by calculating the eccentricity of segment s and comparing with the eccentricities in ∪ s of all the points in .
Thus, for each extension s' of uv to the left, we compute the eccentricities E(i) of all its extensions s_i to the right using Lemma <ref>, in O(n^2) time.
Let N(i) be the maximum distance in ∪ s_i between pairs of points in .
Our goal is to compute min_i max{ 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: such that there is no j>i with E(j)<E(i) (see  <ref>).
Therefore, we can look for  that minimum by binary search, computing N(i) only for O(log n) values of i.
Using <cit.>, 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(n^3 log n).





We thus obtain the main result in this section.

 
Let ρ be the largest edge length in a network . Then, it is possible to find a segment s' such that diam(∪ s') ≤min_s ∈𝒮 diam(∪ s)+4ρ in O(n^5 log n) time.


This result immediately gives a simple approximation algorithm: subdivide each edge in 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 <cit.>.


Let ρ be the largest edge length in a network . Then, for any 0 < ε < ρ/2 it is possible to find a segment s' such that diam(∪ s') ≤min_s ∈𝒮 diam(∪ s)+4 ε in O((n ρ/ε)^5 log (n ρ)) time.





§ 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 into a path can create a quadratic number of diametral pairs;
as illustrated in the construction in  <ref>. 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 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 p_i and q_j on the left and right of o, respectively, the distance between p_i and p_j on ∪ pq is always equal to |pq|, which is also the diameter of ∪ pq.





 §.§ Diameter after inserting a shortcut


The diameter of  can be immediately computed in linear time, however, the addition of a shortcut s can create a linear number of new faces, thus in principle it is not clear whether ( ∪ 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 <cit.>.
Thus, we can assume that s=pq is maximal and horizontal.
The insertion of s splits into polygonal chains, which bound the different faces created.
Our goal is to compute the pair of chains that have maximum distance in  ∪ s.

We number the chains from 0 to m in the order of their left endpoints from left to right along s (using right endpoints do disambiguate).
Except for possibly the first and last, all chains have both endpoints on s.
For the ith chain C_i, we denote its left and right endpoints by p_i^l and p_i^r, respectively.
If the first vertex of  is not on s, we consider the path from its first vertex to the first intersection of  with s as a degenerate loop chain with equal left and right endpoints on s (analogous for the last vertex of ).

Refer to  <ref>.

Let |C_i| be the length of C_i, let L_i=|pp^l_i| and R_i=|p^r_iq|, and
let s_i denote the segment p_i^lp_i^r.
Note that C_i ∪ s_i forms a cycle.
We use D_i for the distance on ∪ s from p_i^l to its furthest point p̅_i^l on C_i ∪ s_i (i.e., D_i is the semiperimeter of C_i ∪ s_i); see  <ref>(b).




We make some basic observations about the diameter between two chains, depending on their relative position, as shown in Figure <ref>.
They reveal the key property of the problem: the linear ordering between chains induced by s defines uniquely how the diameter between two chains is achieved.




[Disjoint chains]

Let C_i,C_j be two chains of (∪ s) with s_i ∩ s_j = ∅ and s_i to the left of s_j.
The diameter of C_i ∪ p_i^l p_j^r ∪ C_j is D_i+|p_i^r p_j^l|+D_j = D_i+R_i-R_j-|s_j|+D_j.



Chain C_i is completely to the left of C_j (see Figure <ref>(a)), thus any path from a point in C_i to one in C_j must include segment p_i^r p_j^l.
Since the furthest point in C_i from p^r_i is p̅^r_i, and the same for p^l_j and p̅^l_j, the result follows by definition of D_i and D_j, and by observing that |p_i^r p_j^l| = R_i-R_j-|s_j|.



[Nested chains]

Let C_i,C_j be two chains of (∪ s) with s_j ⊂ s_i.
The diameter of C_i ∪ s_i ∪ C_j is 1/2(|C_i|+|p^l_i p^l_j|+|p^r_i p^r_j|+|C_j|) = 1/2(|C_i|+L_j-L_i+R_j-R_i+|C_j|).




In this case the endpoints of the chain C_j are nested inside those of C_i (see Figure <ref>(b)), hence the two chains behave effectively like a cycle, because no diametral pair can have a point on segment s_j, since |C_j|>|s_j|.
The cycle is formed by chains C_i, C_j, and the two subsegments of s_i ∖ s_j.
The diameter of any cycle is half of its perimeter, which in this case amounts to 1/2(|C_i|+|s_i|-|s_j|+|C_j|).
The second equality follows from the fact that |p^l_i p^l_j|+|p^r_i p^r_j| = L_j-L_i+R_j-R_i.



[Overlapping chains]

Let C_i,C_j be two chains of (∪ s) with s_i ∩ s_j ≠∅, p_i^l ∉ s_j and p_j^r ∉ s_i.
The diameter of C_i ∪ p_i^l p_j^r ∪ C_j is
 1/2(|C_i|+|p^l_i p^l_j|+|p^r_i p^r_j|+|C_j|)  = 1/2(|C_i|+L_j-L_i+R_i-R_j+|C_j|).



As in the previous case, the two chains behave effectively like a cycle (see Figure <ref>(c)), in this case formed by C_i, C_j and the segments p^l_i p^l_j and p^r_i p^r_j.
The second equality follows from the fact that |p^l_i p^l_j| = L_j-L_i and |p^r_i p^r_j| = R_i-R_j.


Note that, while in the case of Figure <ref>(a) the diameter is achieved by a unique pair of points, that is not the case in situations (b) and (c), for which an infinite number of diametral pairs of points may exist (as in any cycle). Also, note that expressions for the diameter in Observations <ref> and <ref> are the same except for adding up either R_j-R_i or R_i-R_j.
This difference only exists to differentiate between the two possible orders of the right endpoints of the two chains.


The algorithm for computing ( ∪ s) in linear time starts by going along  and computing all intersections with s in the order of . Then we apply a linear-time algorithm for Jordan sorting <cit.> to obtain the intersections in the order along s, say, from left to right. Within the same running time we can compute the values C_k and s_k.
Next, we sweep the endpoints of the chains along s to compute, for each chain C_k, its furthest chain from the ones seen so far.
To that end, certain information is computed and stored:


  * The furthest chain from C_k to the left, given by _0≤ i < kα_i, where α_i=D_i+R_i.
Similarly, we store the furthest chain to the right.

  * The furthest chain nested inside C_k. This is given by _j ∈ N_kβ_j, where β_j=|C_j|+L_j+R_j and N_k is the set of indices of all chains nested inside C_k.

  * The furthest chain with one endpoint in C_k, and one outside: given by
_j ∈ O^r_kγ_j, where γ_j=|C_j|+L_j-R_j and O^r_k is the set of indices of all overlapping chains with their left endpoint inside C_k and their right endpoint outside.
Similarly, we store those with their left endpoints outside and the right one inside of s_k.


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 C_k.

Suppose that C_i starts to the left of C_j (the other case is analogous). We use a data structure for range minimum queries <cit.>.
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 A_n and A_o 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 2m in total.
The positions are as they appear sorted along s, from left to right.
Refer to  <ref>.

For a chain C_j, the position corresponding to its left endpoint has a value equal to β_j in the array A_n, and value γ_j in array A_o.
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.





To find the nested or overlapping chain furthest from C_i we would like to perform one maximum range query in A_n and one in A_o, in both cases with a subarray corresponding to the interval between the endpoints of C_i.
The goal is to use these queries to obtain the furthest chain of each type: nested and overlapping.
However, there is an issue.
In the way A_n and A_o are defined, the result of a range query cannot distinguish between nested or overlapping chains, it necessarily searches in both sets (i.e., N_i ∪ O^r_i).
Fortunately, the geometry of the problem guarantees that we can still use the result obtained, as we show next.
The following lemma shows that if the furthest face is associated to a β_i value, then it must be nested, and similarly, if it is associated to a γ_i value, it must be overlapping.



Let C_k be a chain with distance to C_i equal to

    d^* =max{max_j ∈ (N_i ∪ O^r_i) |C_i|-L_i-R_i+β_j , max_j ∈ (N_i ∪ O^r_i) |C_i|-L_i+R_i+ γ_j }.
 Then it holds that:


  (i) if d^* = |C_i|-L_i-R_i+β_k, then k∈ N_i;

  (ii) if d^* =  |C_i|-L_i+R_i+ γ_k, then k∈ O^r_i.




We prove (i); an analogous argument proves (ii). Suppose that d^* = |C_i|-L_i-R_i+β_k, but k∈ O^r_i, i.e., C_k is overlapping.
Further, to the right of C_i we have R_i > R_k and thus R_k-R_i < 0 < R_i-R_k. Hence, using this and the definitions of d^* and β_k, we have

    d^*= |C_i|-L_i-R_i+(|C_k|+L_k+R_k) < |C_i|-L_i+R_i+|C_k|+L_k-R_k = |C_i|-L_i+R_i + γ_k.

In other words, the value associated to γ_k gives a larger distance than the one associated to β_k, contradicting the optimality of d^*.


Therefore, when processing a chain C_k, we perform one maximum range query in A_n and one in A_o, and keep the maximum of those two values.
Lemma <ref> guarantees that the associated chain is the furthest one that is either nested or overlapping.
Proceeding in an analogous way for the chains that are overlapping with one endpoint to the left of C_k, the furthest face from C_k of any of the three types (disjoint, nested, overlapping) can be found in O(1) time, and the maximum distance between two chains can thus be found in linear time.


For every path  with n vertices and a shortcut s, it is possible to compute the diameter of ( ∪ s) in Θ(n) time.


It is worth noting that the ideas used in this section do not extend to networks that are trees.
As soon as  is a tree, the insertion of s creates chains that can have several ways to connect in ∪ s, making it impossible to know, a priori, the expression of their distance as we did for paths in Observations <ref>–<ref>.




 §.§ Optimal horizontal shortcuts


The observations in Section <ref> also give us a way to compute an optimal horizontal shortcut for a path considerably faster than using the general method in Section <ref>. After a suitable rotation, this allows to find an optimal shortcut of any fixed orientation.

Assume as in Section <ref> that shortcuts are horizontal and maximal, so they can be treated as horizontal lines. Now,
consider the vertices in  sorted increasingly by y-coordinate, and let y_a,y_b, with y_a < y_b, be the y-coordinates of two consecutive vertices in that order. Observations <ref>–<ref> are stated in terms of chains, but they also apply to faces.
Indeed, they imply that the distance between any two faces f_i and f_j is a linear function d_ij(y) for y_a ≤ y ≤ y_b. Thus, each face is associated with k-1 lines in 2D where k is the total number of faces, leading to a set L of Θ(k^2) lines (note that k=O(n)). 

The optimal shortcut over all y ∈ [y_a,y_b] is given by the minimum of the upper envelope of L, which can be computed in O(k^2 log k) time <cit.>. If this is done with each of the n-1 horizontal strips formed by consecutive vertices of , the optimal horizontal shortcut is obtained in total O(n^3 log n) time. 

 The preceding method can be improved if, instead of computing from scratch the upper envelope of L at each horizontal strip, we maintain the upper envelope between consecutive strips and only add or remove the lines that change when going from one strip to the next one. The changes between two consecutive strips are of three types:


  (i) one of the two line segments bounding a face within the strip changes;

  (ii) a face ends;

  (iii) a new face appears.

In the worst case, n-1 lines are removed from L and another n-1 lines are added to L.
Maintaining the upper envelope of N lines is equivalent to maintaining the convex hull of N points in 2D, which can be done in amortized  O(log N) time per insert/delete operation with a data structure of size O(N) <cit.>. Since N = O(n^2), we obtain the following theorem.


For every path  with n vertices, it is possible to find an optimal horizontal shortcut in O(n^2 log n) time, using O(n^2) space.




 §.§ Optimal simple shortcuts


In this section we consider optimal simple shortcuts, i.e., we restrict the possible shortcuts to those whose interior does not intersect .
We show that an optimal simple shortcut can be computed much faster if it exists. Note that one must distinguish between an optimal simple shortcut and a simple optimal shortcut. The first is a shortcut that is optimal in the set of simple shortcuts; this is different of being optimal in the set of all shortcuts and, in addition, being simple.

Interestingly, it is known that optimal simple shortcuts may not exist, even for paths <cit.> (e.g., when the only optimal shortcut goes through a vertex, see Figure <ref>(a)). It is not clear, however, what the conditions for a network  to have an optimal shortcut are, even restricted to simple shortcuts. The following proposition is a first approach to this question.





Let 𝒩 be a network whose locus  admits a simple shortcut, and let 𝒩 be the network resulting from adding to 𝒩 all edges of the convex hull of V(𝒩). If all faces of 𝒩 are convex, then  has an optimal simple shortcut.



Suppose on the contrary that there is no optimal simple shortcut for . Then, there is a sequence {s_n} of simple shortcuts such that d_n+1<d_n where d_n= diam(∪ s_n). Let s_n=p_nq_n.
We may assume, without loss of generality, that {s_n} is contained in a face ℱ of 𝒩 as there is a finite number of faces, at least one of which contains a subsequence of {s_n}. The same argument on the number of edges of a face lets us assume that for every n, points p_n and q_n are, respectively, on edge e and edge e' of .

Since e is a compact set, sequence {p_n} has a convergent subsequence {p_n'}. The corresponding sequence {q_n'} is not necessarily convergent, but edge e' is also a compact set which implies that {q_n'} contains a convergent subsequence {q_m}. Let {s_m}={p_mq_m}, lim p_m=p, lim q_m=q, and s=pq; we will write, with some abuse of notation, lim s_m=s . Next, we prove that d_s= diam(∪ s)<d_n for every n.

Fixed n, consider two segments s_m_0,s_m_1⊂{s_m} with n<m_0<m_1, and take ε>0 such that d_m_0-d_m_1>ε; such segments do exist as lim s_m=s. Let ℛ be the set of points in face ℱ whose distance to p or q is smaller than ε/8. Any segment s_m' with endpoints p'∈ e∩ℛ and q'∈ e'∩ℛ verifies that |d_s-d_m'|<ε/2. Indeed, 
    |d_s-d_m'|<|p-p'|+|q-q'|+||pq|-|p'q'||<ε/8+ε/8+2ε/8=ε/2.

Since lim s_m=s, there exists m_2 such that s_m ∈ℛ for all m≥ m_2. Let m_3= max{m_1,m_2}.
 If d_s<d_m_3 then d_s<d_m_3+ε <d_m_0<d_n. Otherwise, 
    d_s<d_m_3+ε/2<d_m_0-ε/2<d_m_0<d_n.



Thus, for every sequence {s_n} of simple shortcuts such that d_n+1<d_n there is a shortcut s satisfying that d_s<d_n for all n. Further, s is simple (all faces of 𝒩 are convex) and there is no optimal simple shortcut. This implies that s must be an edge of 𝒩 which contradicts the fact that, by definition, edges are not shortcuts. Note that there can be sequences for which the corresponding segment s is an edge of CH(V(𝒩)∖ E(𝒩) (here CH(V(𝒩) denotes the convex hull of V(𝒩)), but there is a finite number of such edges and so one would obtain an optimal simple shortcut among all those segments s.


Figure <ref>(b) shows that the converse of Proposition <ref> is not true.

We now turn our attention to the computation of an optimal simple shortcut, if it exists.

Let s=pq be a simple shortcut for a path  with endpoints u,v. Suppose that point p is closer to u than q along ; let x=d(u,p) and y=d(v,q). There is only one bounded face in ∪ s whose boundary is a cycle C(p,q). Let p and q be the farthest points from, respectively, p and q on C(p,q), and let z=(d_(p,q)-|pq|)/2. Note that d(p,q)=|pq| and z=d(p,q)=d(p,q).
See  <ref>.



There are three candidates for diametral path in ∪ s (see <cit.>):


  * The path from u to v via s is diametral if and only if z= min{x,y,z},
 
  * the path from u to p via s is diametral if and only if y= min{x,y,z},

  * the path from v to q via s is diametral if and only if x= min{x,y,z}.


Thus, diam(∪ s)∈{x+y+|pq|, x+z+|pq|, y+z+|pq|}.

For the highway model, it was proved in <cit.> that  has an optimal shortcut satisfying x=y, which allows to compute it in linear time.
In the planar model the situation is more complicated but, in a similar fashion, we can prove the following lemma, which will lead to Theorem <ref>.

 
Let pq be an optimal simple shortcut for . The following statements hold.


  * If neither p nor q are vertices of  then x=y=z.

  * If p or q are vertices of  then the two smallest values among x,y,z are equal.




First note that increasing (resp., decreasing) the value of either x or y leads to a decrease (increase) in the value of z.

Suppose that neither p nor q are vertices of  and assume on the contrary that x is smaller (respectively, greater) than y and z. Then point p can be slightly moved away from u (respectively, q away from v) in order to obtain a shortcut s' such that diam(∪ s')< diam(∪ pq). Thus, shortcut pq would not be optimal, which is a contradiction. The same argument applies for y. Finally, if the smallest value is z then we can slightly move p closer to u and q closer to v while decreasing the diameter of the augmented network, again a contradiction.

Suppose now that p is a vertex of , i.e., q is the only possible point to be moved in order to argue as above and reach a contradiction. If x<y<z we can decrease y by moving point q closer to v obtaining a “better” shortcut, a contradiction. If x<z<y it suffices to increase y in order to decrease z to reach a contradiction. The remaining cases are analogous.



 
 It is possible to decide whether a path  with n vertices has an optimal simple shortcut and compute one (in case of existence) in O(n^2) time.



We first determine all candidate segments pq for an  optimal simple shortcut and also other relevant segments to decide the existence of such a shortcut. Two cases are distinguished depending on whether p and q are vertices.

Case 1. p,q∉ V(): we add O(n) extra vertices on each half of , such that the i-th edges from each endpoint have the same length. Let 𝒫_ℓ^1 and 𝒫_ℓ^2 be the two resulting sub-paths where every edge e_1∈𝒫_ℓ^1 has an associated edge e_2∈𝒫_ℓ^2 of the same length, and vice-versa.


This partition of  allows us to compute the points p∈ e_1 ∈𝒫_ℓ^1 and q ∈ e_2 ∈𝒫_ℓ^2 where x=y (and |e_1|=|e_2|).
Among these points and according to Lemma <ref>, we want those satisfying that z=x (=y).
Now, assume we have p ∈ e_1 and q ∈ e_2 such that x=y=z. Consider advancing a distance λ along e_1 and e_2, from p and q to p' and q'.
Since d_P_ℓ(p,q)=||-2x and z=(d_P_ℓ(p,q)-|pq|)/2, we only need to compute the variation of |pq| with respect to the variation λ of x (and y).  <ref>(a) shows the construction where α denotes the angle formed by the prolongations of e_1 and e_2, and a and b are, respectively, the distances from p and q to the intersection point of those prolongations. By the law of cosines we have

    |p'q'|=√((a∓λ)^2+(b∓λ)^2 - 2(a∓λ)(b∓λ)cosα).

Note that the variation of x might be in the direction of the intersection point o of the prolongations of e_1 and e_2 or in the opposite direction and, in general, it does not lead to a parallel segment to pq (see  <ref>(b)); in fact, segments pq and p'q' are parallel only if the triangle formed by p, q, and the intersection point o is isosceles.

Therefore, by solving O(n) quadratic equations, we obtain O(n) candidate segments pq with p,q∉ V().





Case 2.  p or q are vertices of : according to Lemma <ref> our candidate segments must satisfy that the two smallest values among x,y,z are equal. Clearly, there are O(n^2) segments to consider with both endpoints being vertices; it remains to obtain those candidate segments with exactly one endpoint in V().

For each vertex of 𝒫_ℓ^1 (i.e., x is a fixed value), we have computed in case (1) the O(n) candidate segments verifying that x=y and so we must determine those for which x=z
(analogous for each vertex in 𝒫_ℓ^2 and y=z). This can be done as in case (1) where λ is now the variation of y since x is fixed; the formula is 
    |pq'|=√(a^2+(b∓λ)^2 - 2a(b∓λ)cosα).
 Note that p is a fixed vertex of 𝒫_ℓ^1 and the corresponding q and q' are points on an edge of 𝒫_ℓ^2. Thus, there is a total of O(n^2) candidate segments.

Besides the segments obtained in cases (1) and (2), we must consider other segments that are pivoting on a vertex w of  (see Figure <ref>) and such that the two smallest values among x,y,z are equal. Note that in the preceding cases we have not computed those whose endpoints are not vertices and z=x≠ y or z=y≠ x. This can be done applying twice the argument of case (2): to the left and to the right of the line shown in Figure <ref> passing through vertex w. The desired value z is the sum of the two obtained values.




Finally, we classify all our segments, O(n^2) in total,


into three sets: 𝒮 of simple shortcuts, ℒ of limit cases (the segment intersects  on three points), and shortcuts that intersect  on more than three points. There exists an optimal simple shortcut if and only if the minimum value of diam(∪ pq) over pq∈𝒮∪ℒ is attained by a segment in 𝒮.





§ CONCLUSIONS


In this paper we have presented the first results on the computation of optimal shortcuts for general networks in the planar model.
This can be seen as a particular variant of the road network design problem, where the problem is abstracted to its most fundamental geometric version.
Clearly, even in this restricted setting, the problem continues to be difficult and challenging.
We have shown that an optimal shortcut can be computed in polynomial time, and given a discretization of the problem that results in an approximation of the original continuous version.
Even though the discretization obtained is too large to be of practical use, it is interesting from a theoretical point of view, and hopefully will be useful to obtain smaller discretizations in the future.

We have also presented new results for paths, including how to quickly compute the diameter after inserting a shortcut, the computation of an optimal shortcut of fixed orientation, and of an optimal simple shortcut.
These are important first steps on a relevant and difficult problem, which leave many intriguing questions open.
The existence of a small discrete set of segments to approximate an optimal shortcut, or a fast algorithm to find an optimal shortcut for paths (any orientation), are some examples.

Finally, the questions studied in this paper but for optimal sets of k>1 shortcuts pose challenging open problems.



  
Acknowledgments.

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.




