Spanners in l1
Full text
99Session C3.2 12th Canadian Conference on Computational Geometry Spanners in l 1 J. Ca c e r e s 1 , C. I . G r i m a 2 , A . M a r q u e z 2 an d A. M o r e n o - G o n z a l e z 2 [1] Departamento de Estadstica y Matematica Aplicada, Universidad de Almera (Spain). [email protected] [2] Departamento de Matematica Aplicada I, Universidad de Sevilla (Spain). [email protected]s, [email protected], [email protected] Abstract In this work, three problems arising in geometric network design theory are considered using the l 1 metric. We rst study the values of for which the -Yao graph (using the metric ab ove) contains the M S T of a collection of sites in the plane, and additionally, we consider the same problem with other l p metrics. Secondly, we give upp er b ounds for the dilation of -Yao in the l 1 metric. And nally, we study the size of a graph with dilation 1 in the l 1 metric. Key words: Spanner, MST, dilation, complete geometric graph, Minkowski metrics. 1 Intro duction The quality of a network interconnecting p oints can b e measured in dierent ways. Typically some minimal conditions are imp osed to the network; for instance, it is usually desired that the Minimum Spanning Tree (MST) must b e contained in the network. But when one tries to design a go o d network for connecting comp onents of a VLSI circuit such that uses little surface area on the chip, draws little p ower and propagates signals quickly, it could b e interesting to nd a sparse graph which approximates shortest paths b etween all pairs of vertices. Those graphs are called spanners and they have b een extensively studied [1] [2] [3] [4] [7]. More precisely, given a set of p oints S in the plane, the dilation of a subgraph of the complete geometric graph is the largest ratio b etween the length of the shortest path from a pair of p oints of S to the distance of those p oints in the plane. A graph with dilation t is called a (t)-spanner of S . But, although the metric that reexes the distance b etween comp onents in an electronic circuit is the l 1 metric, all cited works are fo cused on the Euclidean metric. We try, in this work, to study some of the rst questions that arise in the study of spanners but with the l 1 metric (obtaining some results for the l 1 metric as well). Remind that the l 1 and l 1 metrics are the Manhattan and the Supreme metrics, resp ectively; that is, given two p oints A = ( a 1 ; a 2 ) ; B = ( b 1 ; b 2 ) 2 R 2 , d l 1 ( A; B ) = j b 1 ? a 1 j + j b 2 ? a 2 j and d l 1 ( A; B ) = max fj b 1 ? a 1 j ; j b 2 ? a 2 jg . It is p ossible to nd sparse graphs approximating the complete Euclidean graph arbitrary closely. Thus, Keil [6] showed that a class of graphs called Yao graphs pro duces graphs with dilation arbitrary closed to 1, with O ( n ) edges and that they can b e constructed in time O ( n log n ). Thus, the rst question, treated in the next section, will b e to study whether a Yao graph contains the MST in b oth the l 1 or the l 1 metrics. Secondly, we will study the dilation of those graphs. And, nally, we will see that in the l 1 metric graphs with dilation 1 have much less edges that in the Euclidean distance. 2 - Yao graphs and MST of a collection of sites in the l 1 metric. As it was p ointed out in the Intro duction, in this section we study which are the Yao graphs that contain the MST of a collection of sites in the metric l 1 . First of all, we will give the -Yao graph construction in any metric. Let S b e a collection of sites in R 2 . We partition the space around each p oint into wedges with a given xed op ening angle, , and connect the p oint to the nearest neighb or in each wedge with the given metric. The graph obtained is called the -Yao graph of S . In this work, we extend this denition and we will call ( ; )-Yao graph to the -Yao graph constructed by placing the b orders of the rst wedge forming an angle with the abscissae axis, as we can see in Figure 1. u Figure 1: Construction of a ( ; )-Yao graph. With this new concept we want to know the values of and for which the ( ; )-Yao graph contains the MST of a collection of sites. This problem was studied by Yao [8] for the Euclidean metric and he proved that any = 3-Yao graph of a set of sites contains the MST of the sites. In this work we give similar results for the
100 CCCG 2000, Fredericton, New Brunswick Session C3.2 metrics l 1 and l 1 . Theorem 1 Let S be a set of sites in R 2 . Any ( ; = 4) -Yao graph of S contains the MST of the sites in the l 1 metric. Proof: Without loss of generality, we can supp ose that 2 [0 ; = 4). We know that the MST of a set of sites S can b e built incrementally by adding the shortest edge joining S 1 and S 2 not explored yet, which also maintains the acyclicity, (where S 1 is the subset of sites that have already b een taken and S 2 = S ? S 1 ). Supp ose then that in a step of this algorithm, we have to take the edge uw ; u 2 S 1 ; w 2 S 2 and that this edge is not an edge of the ( ; = 4)-Yao graph of S with the l 1 metric. In this case, if we place the wedges in u , there is an edge uv , shorter than uw , that have b een selected b efore. Then, we only have to prove that d ( u; w ) d ( w ; v ) in the l 1 metric. The worst case o ccurs when uv and uw are similar in length but widely separated in angle, as we see in Figure 2. u v wa a b c Figure 2: The worst case for the pro of of d ( u; w ) d ( w ; v ), (see text). In Figure 2 we can also see that tan = b a + c ; tan( + = 4) = a + b c : But, by other side we have that tan( + = 4) = sin( + = 4) cos( + = 4) = 1 + tan 1 ? tan : So, we get a + b c = 1 + b a + c 1 ? b a + c ; and, simplifying we have a 2 = b 2 + c 2 . Now, it is easy to see that a b + c , so the result holds. 2 The b ound obtained in Theorem 1 is tight, and so given > = 4 it is p ossible to nd a -Yao graph for a set of sites that do es not contain the MST. Theorem 2 Let S be a set of sites in R 2 . The ( = 4 ; = 2) -Yao graph of S contains the MST of the sites in the l 1 metric, but there exists col lections of sites S such the (0 ; = 2) -Yao graph does not contain the MST of S in that metric. Proof: Firstly, we prove that the ( = 4 ; = 2)-Yao graph contains the MST of any set of sites. The pro of is similar to that of Theorem 1, so we only have to prove that the edge v w is shorter than uw in the l 1 metric, b eing w a site in the wedge where v is, (see Figure 3). u v Figure 3: w is a site in the colored region. But, as we can see in Figure 3, any site in the b order of the disc with center u and radio d ( u; v ) is at the same distance from u than from v . So, it is trivial to see that the distance b etween w and u is not smaller than the distance b etween w and v . So, the ( = 4 ; = 2)- Yao graph contains the MST of any set of sites. Now, we give an example of a collection of sites S such the (0 ; = 2)-Yao graph do es not contain the MST of S in the l 1 metric. We consider the set S = f x = (0 ; 0) ; y = (1 0 25 ; ? 0 0 25) ; z = (2 ; 1) ; u = (0 0 5 ; 1 0 5) ; v = (1 ; 1 0 25). Then, in Figure 4 we see that the (0 ; = 2)- Yao graph do es not contain the MST of S . xy z u v xy z u v Yao graph MST Figure 4: v y is an edge of the MST of S but it is not an edge of the (0 ; = 2)-Yao graph of S . 2
101Session C3.2 12th Canadian Conference on Computational Geometry Our next step is to study the same problem for the l 1 metric. Firstly, we consider the problem of nding an angle that satises that any ( ; )-Yao graph of a set of sites contains the MST of the sites. Here, the result is similar to that given for the l 1 metric. Theorem 3 Let S be a set of sites in R 2 . Any ( ; = 4) -Yao graph of S contains the MST of the sites in the l 1 metric. Proof: The pro of of this result is similar to those of Theorems 1 and 2. As in Theorem 1, we only prove the result for 2 [0 ; = 4). We have to prove that the edge uw is longer than v w with the l 1 metric, (see Figure 5). u v w a a b c Figure 5: uw is not shorter than v w . But, as we can see in Figure 5, it is trivial that b; c < a , so the result holds. 2 Secondly, we study what happ ens for the = 2-Yao graphs of a collection of sites and we see that the situation is completely dierent. Theorem 4 Let S be a set of sites in R 2 . The (0 ; = 2) -Yao graph of S contains the MST of the sites in the l 1 metric, but there exists col lections of sites S such the ( = 4 ; = 2) -Yao graph does not contain the MST of S in that metric. Proof: Firstly, we prove that the (0 ; = 2)-Yao graph of aany set of sites S contains its MST. The pro of of this result is similar to that of Theorem 3, so we only have to prove that the edge uw is not shorter than the edge v w in the l 1 metric, where w is a site in the wedge where v is, (see Figure 6). But, it is easy to see that any site in the b order of the disc with center v and radio d ( u; v ) is nearer to v than to u , so the result holds. Now, we give an example of a collection of sites S such the ( = 4 ; = 2)-Yao graph do es not contain u v Figure 6: w lies in the colored region. the MST of S in the l 1 metric. We consider the set S = f x = (0 ; 0) ; y = (1 0 5 ; 1) ; z = (1 ; 3) ; u = ( ? 0 0 25 ; 2 0 25) ; v = ( ? 1 ; 2). Then, in Figure 7 we see that the ( = 4 ; = 2)-Yao graph do es not contain the MST of S . x y z u v Yao graph MST x y z u v Figure 7: uy is an edge of the MST of S but it is not an edge of the ( = 4 ; = 2)-Yao graph of S . 2 3 Dilation in -Yao graphs. In this section we study the dilation in the ( ; )-Yao graphs of a collection of sites. As we did in the previous section, we give a similar result to one given by Keil [6] for the Euclidean metric. In this way, we have found upp er b ounds for the dilation in the ( ; )-Yao graphs of a set of sites in the l 1 metric. Theorem 5 Let S be a set of sites in R 2 . The ( ; ) - Yao graph of the sites has dilation arbitrary closed to 1 when tends to 0. Proof: To nd a path in this graph from u to v , one at each step determines the wedge containing v and moves along a graph edge to the nearest vertex, w , in that
102 CCCG 2000, Fredericton, New Brunswick Session C3.2 wedge. The worst case for the algorithm o ccurs when uv and uw are similar in length but widely separated in angle, as we see in Figure 8, but with prop erties of angles and triangles we can b ound the dilation, as follows. u v w a a h l l1 2 Figure 8: The worst case for the dilation. We denote by d ( ; ) ( S ) the dilation of the ( ; )-Yao graph of the set S . We know that d ( ; ) ( S ) = j uv j + j v w j j uw j : But, as we can see in Figure 8, j uv j = j uw j = a + l 1 + l 2 and j v w j = 2 a , so we have that d ( ; ) ( S ) = 1 + 2 a l 1 + l 2 + a : On the other hand, we have sin h = sin( ? = 4 ? ? ) d e ( u; v ) sin( ? = 4 ? ? ) j uv j : So, as a h , we get that d ( ; ) ( S ) 1 + 2 sin sin( ? = 4 ? ? ) ; that tends to 1 when tends to 0. 2 With this result, we provide a way to construct spanners with dilation as closed to 1 as we want. 4 Graphs with dilation 1 in the l 1 metric. As we mentioned in the Intro duction, in this section we see that in the l 1 metric graphs with dilation 1 have much less edges that in the Euclidean distance. We also give three dierent algorithms for constructing these graphs. Let S b e a set of n sites in R 2 . We denote by M n a graph of minimal size of S with dilation 1. In the Euclidean metric, except if the sites are on a straight line, M n is the complete geometric graph of the sites K n . That is, M n has n ( n ? 1) 2 edges. With the l 1 metric this result can b e improved by virtue of a result by Erdos and Szekeres [5]: In any sequence of pq + 1 integers, there exists an increasing subsequence of length p or a decreasing subsequence of length q . We order the sites by their rst co ordinates and then, we can use the result by Erdos and Szekeres taking the second co ordinates as a sequence, obtaining three dierent cases: If ( b n c + 1) b n c + 1 n , then there exist an increasing subsequence of length b n c + 1 and a decreasing subsequence of the same length. If b n cb n c + 1 n , then there exists a decreasing or increasing subsequence of length b n c + 1. In other case, there exists a decreasing subsequence of length b n c and an increasing subsequence of the same length. In these cases, all the edges that form the complete geometric graph of the subsequences are not needed in M n , except the ones that join the correlative sites. In Figure 9 we can see an example with 7 sites, where we have two subsequences of length 3. The edges that we save in each subsequence are marked. (a) (b) Figure 9: (a) Two subsequences of length 3; (b) edges saved in each subsequence. Now, we can use the result again with the sites that have not b een taken in the decreasing or increasing subsequences, so we obtain dierent subsequences of dierent size in which we can erase edges. We can even take a site in each subsequence and use the result by Erdos and Szekeres again. Then, with this metho d, we have a way to approximate the numb er of edges of K n ? M n . In fact we have got a function that pro duces this numb er and we have
103Session C3.2 12th Canadian Conference on Computational Geometry compared it with other functions obtaining that that function is in O ( n 3 = 2 ). Now, we present a result in which we give an upp er b ound for the size of K n ? M n . Theorem 6 Let S be a col lection of n sites in R 2 . With the l 1 metric, j K n ? M n j 2 O ( n 3 = 2 ) . Proof: Let S b e a set of sites in R 2 and let L 1 : : : L k its convex layers. In any of these layers we have four dierent decreasing or increasing chains of sites, (see Figure 10). C CCC CC 1 2 34 Figure 10: An example of the four chains in a convex layer. In Figure 10 we can also see that in each chain we only need the edges joining correlative sites, that is, in each chain C i we do not use j C i j ( j C i j ? 1) 2 ? ( j C i j ? 1) edges. Given any convex layer L i , the worst case is when we have j L i j = 4 sites in each chain. In this case, we do not use j L i j 4 ( j L i j 4 ? 1) 2 ? ( j L i j 4 ? 1) edges in each chain, so the numb er of edges not needed in a lawyer is four times the previous one. Then, as we have k convex layers, it is trivial to see that the total numb er of edges that we do not use is k X i =1 j L i j 4 ( j L i j 4 ? 1) 2 ? ( j L i j 4 ? 1) : Now, if we study the previous expression, we see that the worst case is when k = p n and there are p n sites in each layer. So, we get that at least p n ( n 8 ? 3 p n 2 + 4) edges are not needed in M n . On the other side, we can consider a site in the last convex layer and then partition the space around this p oint into four wedges with b orders parallel to the axis. Then, we do not need the edges joining sites in the rst wedge and the third one and edges joining sites in the second wedges and the fourth one. This happ ens b ecause we have a path b etween these sites, (see Figure 11). u v w z Figure 11: We do not need the edges uv and w z . Now, in the last convex layer there are p n sites and if we study the p osition of the rest of sites we obtain that the worst case is when we have p n= 2 sites in the rst and second wedges and ( n ? 2 p n ) = 2 in the third and fourth wedges. So, we save 2 p n 2 ( n ? 2 p n 2 ) edges. In conclusion, j K n ? M n j has at least 5 8 n p n ? 5 2 n + 4 p n edges, so j K n ? M n j 2 O ( n 3 = 2 ). 2 Corollary 7 Let S be a set of sites in R 2 . With the l 1 metric, j K n ? M n j 2 O ( n 3 = 2 ) . Proof: The pro of of this result is based in the relation b etween the l 1 and the l 1 metrics: if we consider a disc with center u 2 R 2 and radio r with the l 1 metric and we rotate the plane an angle of = 4, we get the disc with center u and radio r in the l 1 metric. Then, to construct the graph K n ? M n of a set of sites S in the l 1 metric, we only have to rotate the plane an angle of = 4, construct K n ? M n in the l 1 metric and rotate the plane again an angle of ? = 4, as we can see in Figure 12. 2 The question that arises now is to compare the two metho ds we have given to approximate the size of j K n ?
104 CCCG 2000, Fredericton, New Brunswick Session C3.2 (a) (b) (c) (d) SS' Figure 12: (a) A set of sites S ; (b) S rotated an angle of = 4, S 0 ; (c) the graph K n ? M n of S 0 in the l 1 metric; (d) the graph K n ? M n of S in the l 1 metric. M n j . In this way, we intro duce now some results for dierent sets of sites, as we can see in Figure 13, where n is the size of S , E 1 the edges we save using the result by Erdos and Szekeres and E 2 the edges we do not use with the metho d given in the pro of of Theorem 6. n 10 10 10 10 10 2· 3 4 5 6 6 10.705 345.118 10.789.476 338.247.777 954.163.715 600.400 16.999 19.501.264 622.504.000 1.762.505.656 12 E E Figure 13: Some results of the size of K n ? M n . 4.1 Three algorithms to construct M n . As it was p ointed out ab ove, we give here three dierent algorithms for constructing the graph M n of any set of sites in the plane. But, as K n ? M n and M n are complementary graphs, these algorithms let us to construct the graph K n ? M n , to o. In this way, we present the rst and the second algorithms to get K n ? M n and the third one to construct M n . We must say that these three algorithms let us to construct the graphs M n and K n ? M n of a set of sites in the l 1 metric. As we did in Corollary 7, we only have to rotate the plane an angle of = 4, construct the graph M n or K n ? M n of the new set of sites and rotate the plane again an angle of ? = 4. 4.1.1 The rst algorithm. The rst algorithm runs in time O ( n 3 ) in the worst case, but we think that the average-case running time is much b etter. This algorithm is based in the following assert: Let S b e a set of sites in R 2 . Then if we place the axis in u 2 S we save the edges that join sites in the rst quadrant with sites in the third one. The same happ ens with the sites in the second and the fourth quadrant, as we saw in the pro of of Theorem 6. So, if we place the axis in all the sites of S , we only have to add the edges joining the sites in the p osition we said ab ove for getting K n ? M n . This is what the algorithm do es. Let S b e a set of n sites in R 2 . Firstly, we order the sites by the second co ordinate p 1 ; p 2 ;:::;p n , that can b e done in time O ( n log n ). Secondly, we visit all the sites of S from p 1 to p n . When we place the axis in a site p j we consider two lists, l T and l B . In l T we have the sites in the second and the rst quadrant ordered by the rst co ordinate and separated by a p ointer M and in l B we have the p oints of the third and the fourth quadrant ordered by the rst co ordinate and separated by a p ointer N . we can maintain the two lists in time O ( n log n ). In the rst step, we have all the sites in l T with the p ointer M in the place of p 1 and in l B we only have the p ointer N . Then for k = 1 ;:::;n the lists change as follows. In l T we put M in the place of p k . In l B we add p k ? 1 in the place of N and we put N in the place of p k . In Figure 14 we can see an example for a set of 7 sites. At last we have to add the edges joining the sites on the left of M with the sites on the right of N and the sites on the right of M with the sites on the left of N that have not b een considered yet. Each step can b e done in quadratic time, so the whole algorithm runs in time O ( n 3 ). 4.1.2 The second algorithm. The second algorithm we present to construct K n ? M n runs in time O ( n 2 log n ) and is based in the following result: given two sites u and v in the plane, we save the edge uv if there is a site, dierent from u and v , in the rectangle that u and v form, (see Figure 15). Then, let S b e a set of sites in R 2 . We consider a pair of sites u and v , we check if there is another site in the rectangle that they form and in armative case, we add the edge uv . Now, to check if there is any site in a rectangle takes time O (log n + k ), where k is the numb er of p oints inside the rectangle. But we stop when we nd one site, so each step of the algorithm can
105Session C3.2 12th Canadian Conference on Computational Geometry p p p p p p p 1 2 3 4 5 6 7 lT={ppp 56 7} M l={pp} B p N 2 1 3 p p p p p p p 1 2 3 4 5 6 7 lT={pp6 7} l={ p p} Bp N21 3 M p 4 Step 4 Step 5 Figure 14: Two steps of the rst algorithm. u v w z Figure 15: We save the edge uv , but not the w z . b e done in O (log n ). As we have n 2 pairs of sites, the whole algorithm runs in time O ( n 2 log n ). 4.1.3 The third algorithm. Here, we present a third algorithm which constructs the graph M n of a p oint set in the plane. This algorithm runs in optimal time O ( n 2 ) in the worst case but, we think that the average-case running time is worst than the obtained by the two algorithms given ab ove. Without loss of generality, supp ose that the p oints f p 1 ; p 2 ;:::;p n g have b een ordered from left to right (that can b e done in O ( n log n )). For simplicity, we split the algorithm in two steps but it is not needed they are implemented separately. The rst step consists of constructing a binary tree T with f p 1 ; p 2 ; : : : ; p n g as its vertices which records the order of the p oints from up to down. Let p 1 b e the ro ot of the tree then, one of its descendant subtrees contains all the p oints which are higher than p 1 and the other subtree contains the p oints which are lower. The tree can b e constructed simply by inserting the p oints successively in order and every insertion takes time at most O (log n ) (see Figure 16 as an example), so the whole step can b e done in O ( n log n ). We will referred the subtrees of every non-leaf no de as its high and low subtrees . Figure 16: An example of tree As it was said ab ove, the second step can b e done simultaneously with the rst one. Consider a p oint p j which have b een just inserted in the tree. Now, the goal is to nd the previous p oints which are joined with p j in the graph M n . Clearly, p j is joined in M n with its parent and with the parent of its parent if and only if p j is a low son of a high son or vice versa. It is not dicult to check this claim and that no other ancestor of p j is joined with it in M n . Now, for every ancestor p i of p j we will make some op erations. For the sake of simplicity, let us supp ose that p j is containing in the low subtree of p i as you can see in Figure 17 (the other case is treated in a symmetric way). Next we will nd the highest leaf of the low subtree and the lowest one of the high subtree and call them p k and p l resp ectively. If p k 6 = p j , we set the variable r as k , otherwise r := 0.
106 CCCG 2000, Fredericton, New Brunswick Session C3.2 pi pk pl pj high subtree low subtree Figure 17: For every ancestor p i of p j , this is one of the two p ossible situations. Finally, we will explore the no des of the the high subtree, b eginning with p l in such a way that a no de is visited after all of its its descendants have b een visited. For every such no de p m , then: If p m is a leaf and m > r , then the edge p j p m b elongs to M n . Also, we set r := m . If p m is not a leaf and it has no low subtree then p j p m is an edge of the graph M n Adding the edges of the tree T to the nal result, we get the graph M n . Since in the worst case, every p oint is needed to b e checked with all the previous p oints in the order, the whole algorithm runs in time O ( n 2 ) but this is optimal. 5 Conclusions and op en problems In this work we have proved that any ( ; = 4)-Yao graph contains the MST of a collection of sites in the l 1 and l 1 metrics and we have studied what happ ens with some ( ; = 2)-Yao graphs. It could b e interesting to study the rest of cases and try to generalize these results to other l p metrics. Other question related with Yao graphs is to nd upp er b ounds for the dilation in those metrics, as we have done for the l 1 . We also have studied graphs with dilation 1 in the l 1 metric and the numb er of edges that we do not need to construct them. We have obtained that j K n ? M n j 2 O ( n 3 = 2 ), so the op en question is to nd b etter upp er b ounds for the size of K n ? M n . In fact, we have found some particular cases, for instance if the sites are in convex p osition, where j K n ? M n j 2 O ( n 2 ). References [1] L.P. Chew. There are planar graphs almost as go o d as the complete graph. J. Comput. System. Sci., 39 (1989), pp. 205{219 [2] G. Das and D. Joseph. Which triangulations approximate the complete graph? Pro c. Int. Symp. Optimal Algorithms, Springer LNCS 401 (1989), pp. 168{192 [3] G. Das and G. Narasimhan. A fast algorithm for constructing sparse Euclidean spanners. Pro c. 10th ACM Symp. Comp. Geom., (1994), pp. 132{139 [4] D. Epstein. Spanning Trees and Spanners. Handb o ok of Computational Geometry. Edited by J.-R. Sack and J. Urrutia. Elsevier Science B. V. (1999), pp. 425{461 [5] P. Erd os and A. Szekeres. A combinatorial problem in geometry. Comp ositio Mathematica, vol. 2 (1935) 463-470. [6] J. M. Keil. Approximating the complete Euclidean graph. Pro c. 1st. Scand. Worksh. Algorithm Theory, Springer LNCS 318 (1988), pp. 208{213. [7] C. Levcopoulos and A. Lingas. There are planar graphs almost as go o d as the complete graphs and as short as minimum spanning trees. Pro c. Int. Symp. Optimal Algorithms, Springer LNCS 401 (1989), pp. 9{13 [8] A. C. Yao. On constructing minimum spanning trees in k-dimensional space and related problems. SIAM J. Comput. (1982), no. 11, pp. 721{736.