Shortcut sets for plane Euclidean networks (Extended abstract)

Shortcut sets for plane Euclidean networks (Extended abstract) 1 J. C´aceresaD. GarijobA. Gonz´alezbA. M´arquezb M. L. PuertasaP. Ribeiroc aDepartamento de Matem´aticas, Universidad de Almer´ıa, Spain. bDepartamento de Matem´atica Aplicada I, Universidad de Sevilla, Spain. cInstituto Superior de Engenharia, Universidade do Algarve, Faro, Portugal. Abstract We study the problem of augmenting the locus Nof a plane Euclidean network N by inserting iteratively a finite set of segments, called shortcut set, while reducing the diameter of the locus of the resulting network. We first characterize the existence of shortcut sets, and compute shortcut sets in polynomial time providing an upper bound on their size. Then, we analyze the role of the convex hull of Nwhen inserting a shortcut set. As a main result, we prove that one can always determine in polynomial time whether inserting only one segment suffices to reduce the diameter. Keywords: Shortcut set, Euclidean network, diameter, augmentation problem. 1 Introduction Aplane Euclidean network N=(V(N),E(N)) is a plane geometric graph (i.e., an undirected graph whose vertices are points in R2and whose edges are 1 Supported by projects MTM2014-60127-P and PAI FQM-0164. E-mails: [email protected], [email protected], [email protected], [email protected], [email protected], [email protected]. non-crossing straight-line segments connecting pairs of points) in which edges are assigned lengths equal to the Euclidean distances between their endpoints. It is natural to distinguish between a network Nand its locus N, which is the union of the segments that form the network. When no confusion may arise, we shall say network, it being understood as plane Euclidean network. When two points p, q are on edges of N,apath connecting them may consist of a number of edges and at most two fragments of edges. For computing their distance d(p, q), we sum the lengths of all the edges in a shortest path between them and the lengths of the possible fragments. The diameter of N, denoted by diam(N), is the maximum among the distances between any two points on N 2.Whend(p, q)=diam(N), points p, q are called diametral. In this work we study the following problem: Given a plane Euclidean network N, insert a finite set of segments S= {s1,...,s k}in order to reduce (or minimize) the diameter of the locus of the resulting network, provided that the endpoints of segment s1are on Nand the endpoints of si,2≤i≤k,areonN∪{s1,...,s i−1}. We say that Sisashortcut set for N.WhenS={s}, segment sis called shortcut,andsis simple if it only intersects Non its endpoints. This type of problems is mainly motivated by urban network design: to introduce shortcut sets is a way of improving the worst-case travel time along networks of roads in a city, highways, etc. Such models are considering the locus of the network which is also used for related applications to location analysis and feed-link problems; see for example [1]. Our problem also belongs to the class of graph augmentation problems. Concretely, it is a variant of the Diameter-Optimal k-Augmentation Problem for edge-weighted geometric graphs, where one has to insert kadditional edges to an edge-weighted plane geometric graph in order to minimize the diameter of the resulting graph. There are very few results on this problem and, in general, on graph augmentation over plane geometric graphs; see for instance [6]. When considering Ninstead of N, the hardness of the problem is enormously increased which motivates that, to the best of our knowledge, there are only two previous works on this topic, both restricted to specific families of graphs. Yang [8] deals with the problem of inserting only one segment to a simple polygonal chain, designing three different approximation algorithms to compute an optimal shortcut (i.e., the one that minimizes the diameter among all shortcuts). Very recently, De Carufel et al. [4] have studied simple 2The diameter of Nis the generalized diameter of [3]andthecontinuous diameter of [4,7], but we use the context of locus because it fits better to our purpose in this work. shortcuts for paths and cycles. They consider the possibility of inserting more than one segment, although the possible intersection points between their segments are not included as points of the resulting network. With this notion, they determine in linear time optimal simple shortcuts for paths, and optimal pairs of simple shortcuts for convex cycles. We present in this work the first approach to the above-stated problem for general plane Euclidean networks. 2 Existence of shortcut sets There are networks whose locus have no shortcut (a triangle) and even no shortcut set of any size (a straight path); the following theorem states a natural characterization of the existence of shortcut sets. We use CH(N) to denote the convex hull of N, and its diameter diam(CH(N)) is the maximum among the Euclidean distances between any two points in CH(N). Theorem 2.1 Let Nbe a plane Euclidean network. Then, the following statements are equivalent: (i) Nadmits a shortcut set. (ii) The segment defined by any two diametral vertices is not contained in N. (iii) diam(CH(N)) <diam(N). As a consequence of the proof of Theorem 2.1 (here omitted for the sake of brevity), we obtain the following corollary. Corollary 2.2 Let Nbe a plane Euclidean network whose locus Nadmits a shortcut set. Then, it is possible to compute in polynomial time a shortcut set for Nof size at most 2|E(N)|−n1, where n1is the number of vertices of degree 1 in N. By using properties of CH(N), one can improve the preceding upper bound, but we stress its linearity with respect to |V(N)|. Nevertheless, the importance of CH(N) goes much further as the following theorem reflects. Theorem 2.3 Let Nbe a plane Euclidean network whose locus Nsatisfies that diam(CH(N)) <diam(N).Then, for every ε>0such that diam(CH(N))+ ε<diam(N)there exists a shortcut set Sfor Nverifying that diam(CH(N)) ≤ diam(N∪S)<diam(CH(N)) + ε. Proof (Sketch) Let M={p∈N |ecc(p)≥M}where ecc(p) = maxq∈Nd(p, q) and M= diam(CH(N)) + ε 4. This set is non-empty and compact in R2.Further, the collection of balls B(p, ε 4)withp∈Mis a cover of M, and so there is a finite subcover, say M⊆k i=1 B(pi,ε 4). For 1 ≤i≤k, the set Mi={q∈N |d(pi,q)≥M}is also non-empty and compact in R2. Thus, for the cover of Migiven by the balls B(q, ε 4)with q∈M i, there is a finite subcover, say Mi⊆ri t=1 B(qi t,ε 4). One can prove that the set Sof segments with endpoints piand qi j,1≤ i≤kand 1 ≤j≤ri, verifies that diam(N∪S)<diam(CH(N)) + ε. Moreover, it is easy to show that diam(CH(N)) ≤diam(N), which gives diam(CH(N)) ≤diam(N∪S). 2 3 Computing shortcuts In this section, we present our main result in this work. Due to the lack of space, we sketch very briefly its proof. Theorem 3.1 For every plane Euclidean network N, it is possible to determine in polynomial time whether there exists a shortcut for Nand, in that case, to compute it. Proof (Sketch) We distinguish the following two main steps. Step (1). To split the searching space into a polynomial number of “equivalent” regions. Consider two arbitrary vertical lines defining a strip enclosing N.Foreach vertex u, take two horizontal segments defined by uas one endpoint and the other in one of the vertical lines; in total, there are 2nsegments. We say that two lines are equivalent if they intersect the same segments among those 2n segments. Given a line mthat crosses two edges e, e∈E(N), let Pe,e(m) be the set of equivalent lines to mthat intersect edges eand e. This set can be viewed as the set of segments determined by the intersection points of the lines with e and e, and the region of the plane that it defines has the shape of an hourglass [2]. One can check that there are O(n2) regions Pe,e(m). Step (2). To seek for a shortcut in each region Pe,e(m)in polynomial time. First, we prove the result for simple shortcuts (case (a)) and then we extend our arguments for general shortcuts (case (b)). Case (a). Suppose that line mintersects no edges in between eand e.If e=uv and e=uvthen a point pon ecan be expressed as p=ut +(1−t)v, and a point on eis p=ut+(1−t)v. Thus, a segment ppin Pe,e(m)is represented by a pair (t, t). These pairs must lie inside a region Re,e(m)⊆R2 whose boundary is given by the coordinates of the segments bounding Pe,e(m), and so is determined by two polygonal chains; see Figure 1. Each point in Re,e(m) represents a segment in Pe,e(m). u v u v  t0t1t2 t 2t 1t 0s 0 s0 (t1;t 0 1) (t2;t 0 2) (t0;t 0 0) (s3;s 0 3) (s2;s 0 2) (s1;s 0 1) (s0;s 0 0) (a) (b) Fig. 1. Region Pe,e(m) in (a) and its corresponding region Re,e(m)in(b). We now decide in polynomial time whether there is a segment pp∈ Pe,e(m) (endpoint pon eand pon e) that is a shortcut for N(which in this case would be a simple shortcut). That is: (i) ppmust decrease the distance of all pairs (w,z) such that d(w,z)=d= diam(N), and (ii) ecc(q)<d for every q∈pp. These conditions can be captured by two arrangements of conics, denoted by Q(for condition (i)) and Q(for condition (ii)). To construct Q(similar for Q) we analyze, for each type of diametral pair (w,z), the meaning of having a segment pp∈P e,e(m) in a path that passes through, say uand u, and decreases d(w,z)=d. For example, when wand z are vertices, if such a segment ppexists then d(u, p)+d(p, p)+d(p,u )<d−d1 where d1is either d(w,u)+d(z,u)ord(w, u)+d(z,u). That inequation gives us the interior points (t, t) (corresponding to points p, p) of a conic Qw,z u,u(it is a conic because d(u, p)andd(u,p ) are, respectively, linear functions of t and t). We also obtain conics Qw,z u,v,Qw,z v,u,andQw,z v,vfor paths passing through the corresponding endpoints of eand e(instead of u, u). When considering all types of diametral pairs (w,z), we get the arrangement Q. There exists a shortcut for Nin Pe,e(m) if and only if there is a cell in Q∩Q ∩R e,e(m) that is contained in all conics of Qand, per each diametral pair (w,z), in at least one of the four conics of Qassociated to (w,z). Case (b). Suppose that line mintersects k−2 edges in between eand e. Instead of considering only the four combinations of endpoints of eand e, we take the 4k(k−1)/2 suitable combinations of endpoints of different pairs of edges among the kintersected edges (counting eand e). Further, we do not obtain conics because the terms d(u, p)andd(u,p ) may not be linear functions of tand tbut, for each diametral pair (w,z), certain curves Qz,w ui,uj are obtained. The key to handle the situation in a similar fashion of case (a) is to prove that those curves are convex. For the complexity, note that the preceding analysis must be performed at most in the O(n2) regions Pe,e(m) for each of the O(n2) pairs of edges e, e. Also, the computation of diam(N), which depends on the distances between vertices, can be done in polynomial time [3]. By Lemma 9 of [1], the set of diametral pairs of points is at most quadratic, and the sets of vertices and edges are linear. Thus, the set of values needed to obtain our arrangements is polynomial, and they can also be computed in polynomial time [5]. 2 References [1] Bose, P., Dannies, K., De Carufel, J. L., Doell, C., Grimm, C., Maheshwari, A., Schirra, S., and M. Smid, Networks farthest-point diagrams and their application to feed-link network extension, Journal of Computational Geometry 4(1) (2013), 182–211. [2] Chazelle, B., and L. J. Guibas, Visibility and intersection problems in plane geometry, Discrete Computational Geometry 4(1989), 551–581. [3] Chen, C. E., and R. S. Garfinkel, The generalized diameter of a graph,Networks 12 (1982), 335–340. [4] De Carufel, J. L., Grimm, C., Maheshwari, A., and M. Smid, Minimizing the continuous diameter when augmenting paths and cycles with shortcuts, preprint, 2015. [5] Edelsbrunner, H., Guibas, L., Pach, J., Pollack, R., Seidel, R., and M. Sharir, Arrangements of curves in the plane–topology, combinatorics, and algorithms, Theoretical Computer Science 92 (1992), 319–336. [6] Farshi, M., Giannopoulos, P., and J. Gudmundsson, Improving the strech factor of a geometric network by edge augmentation, SIAM Journal of Computing 38(1) (2005), 226–240. [7] Hansen, P., Labb, M., and B. Nicolas, The continuous center set of a network, Discrete Applied Mathematics 30 (1991), 181–195. [8] Yang, B., Euclidean chains and their shortcuts, Theoretical Computer Science 497 (2013), 55–67.