More results about spanners in the l1-metric

More results about spanners in the l1-metric.∗ J. C´aceres† , C. I. Grima, A. M´arquez‡and A. Moreno-Gonz´alez§ Abstract In this work we study more questions about spanners in the l1-metric. Concretely, we will see that adding some Steiner points to a set of sites the metrically complete graph of the new set has a linear number of edges. We will also characterize the free dilation trees. Finally, inspired in the work for the l1-metric, we will study points in general position for other metrics, the λ-metrics. 1 Introduction. There are many applications in geometric network design in which it would be interesting to find graphs with few edges that approximate shortest paths between all pair of vertices. Since in many problems, as the design of VLSI circuits, the metric that reflexes the actual distance between the vertices is the l1-metric, in previous works [2, 3] we presented some results about the first questions that arise in the study of these graphs. Given a set of sites Sin the plane, the dilation of a subgraph of the complete geometric graph is the largest ratio between the length of the shortest path from a pair of points of Sto the distance of those points in the plane. In this way, we have presented the next results: •It is possible to construct graphs approximating the complete Euclidean graph closely in the l1-metric. Moreover, we found graphs that are not the complete graph but they have dilation 1 (dilation free graphs). More precisely, given a set of sites Sin the plane, we call the metrically complete graph of S(denoted M(S)) to the minimal dilation free graph. •The metrically complete graph is strictly smaller than the complete graph in the l1-metric; in fact, if K(S) denotes the complete geometric graph on S, then |K(S)−M(S)| ∈ O(N3/2). •There exists a characterization of the set of sites with a planar metrically complete graph. Also, we have found some necessary conditions for a planar graph in order to be isomorphic to a metrically complete graph. In this work we present some additional results that continue those two mentioned works. Firstly, given a set of sites Sin the plane we try to reduce the size of M(S) and we will see that adding some Steiner points to Sthe metrically complete graph of the new set of sites has a linear number of edges. Secondly, we try to find which trees have dilation 1 in the l1-metric, obtaining a characterization for these graphs. Finally, we try to generalize some of our first results for other metrics, the λ-metrics. In fact, we will see that the metrically complete graph of a set of sites is smaller than the complete Euclidean graph for those metrics. ∗Partially supported by MCyT project BFM2001-2474 †Departamento de Matem´atica Aplicada y Estad´ıstica. Universidad de Almer´ıa. E-mail: [email protected] ‡Departamento de Matem´atica Aplicada I. Universidad de Sevilla. E-mail: {grima,almar}@us.es §Departamento de Matem´aticas. Universidad de Huelva. E-mail: [email protected] 65 2 It is possible to reduce the size of a metrically complete graph. As we have said above, given a set of sites Sin the plane, |K(S)−M(S)| ∈ O(N3/2) in the l1-metric, but, in general, M(S) has a quadratic number of edges. Thus, the first question we consider is to reduce the size of M(S) adding some new points to S. In order to find these points we only have to make a partition of the initial set of sites that leads to a kd-tree [1], (see Figure 1). Then, we add one Steiner point in the intersections of the lines used to make the partition. Then, we can prove the next result. p p p p p p p p p p 1 2 3 4 5 6 7 8 9 10 l l l l l l l l 2 3 4 5 6 7 8 9 l 1 Figure 1: A partition of a set of sites. Theorem 1 Given a set of nsites Sin the plane, there exists a linear number of Steiner points Stverifying that |M(S∪St)| ∈ O(n). 3 Free dilation trees. As we have said in the Introduction, the second question we try to solve is to find which are the trees with dilation 1. In the Euclidean metric the answer to this question is very simple: we can only construct a free dilation tree when the sites are in a straight line. In the l1-metric, some new cases appear. Theorem 2 If Tis a free dilation tree, then Tis isomorphic to one of the trees in Figure 2. 4 Points in general position for a λ-metric. Given a λ-metric, a ball centered in xand radio ris a regular polygon of λedges verifying that the Euclidean distance between xand the vertices of the polygon is r. Observe that for any value of λthere exist infinite regular polygons centered in x, so a λ-metric is not only characterized by the number of edges, but also by their orientation. However, it is only necessary to solve the question for one of them. One of the 4-metrics is the l1-metric, so it is natural to consider the question of constructing free dilation graphs for other values of λ. In fact, we will see that the metrically complete graph of a set of points has less edges that the complete graph in a λ-metric. In order to solve this result 66 (a) (b) (c) (d) Figure 2: Free dilation trees in the l1-metric. we will prove that for every λ, there exists a number n(λ) verifying that any set of points with more than n(λ) points in general position for the Euclidean metric, is not in general position in the λ-metric. We consider that a set of points is in general position if there are not three consecutive points in a straight line. Then, the first question we must solve is to find the minimum arc between two points. Then, let u1, u2be two points in the plane and for each point uiwe consider a neighbor Ei. These neighbors make a partition of the plane in sectors centered in the initial points. If we call Sij the sector centered in uithat contains uj, the minimum arcs between uiand ujare all the arcs not decreasing parallel to the border of Sij TSji, [7, 5], (see Figure 3). u v Figure 3: Two minimum arcs between uiand ujin a 6-metric. Lemma 1 Given a λ-metric, there exist, at most, λpoints in convex position in general position. Now, in 1935 Erd¨os y Szekeres [4] proved that for every natural number nthere exists an integer g(n) verifying that for every set with more than g(n) points, there are nin convex position. Then, we can prove the next result. 67 Theorem 3 For any value of λthere exists n(λ)verifying that every set of points with, at least, n(λ)points is not in general position. Now, our objective is to find bounds for n(λ). It is obvious that λ+ 1 ≤n(λ)≤g(λ+ 1), and it is known [6] that g(n)≤µ2n−5 n−2¶+ 2 However, this bound does not seem to be tight because for n= 4 we obtain 12 as upperbound and we know that n(4) = 5. In fact, for small values of λ, it is easy to prove that n(λ) = λ+ 1. References [1] J. L. Bentley. Multidimensional binary search trees used for associative searching. Commun. ACM, 18:509–517. 1975. [2] J. C´aceres, C. I. Grima, A. M´arquez and A. Moreno-Gonz´alez. Dilation free graphs in l1-metric. 17th European Workshop on Computational Geometry, Berlin. 2001. [3] J. C´aceres, C. I. Grima, A. M´arquez and A. Moreno-Gonz´alez. Planar graphs and metrically complete graphs. 18th European Workshop on Computational Geometry, Warsaw. 2002. [4] P. Erd¨os and G. Szekeres. A combinatorial problem in geometry. em Compositio Math., 2:463–470. 1935. [5] R. Klein. Concrete and Abstract Voronoi Diagrams. Lecture Notes in Computer Science. Springer-Verlag. 1989. [6] G. Toth and P.Valtr. Note on the Erd¨os-Szekeres theorem. Rutger University. Technical Report DIMACS TR:97-31. 1997. [7] P. Widmayer, Y. F. Yu and C. K. Wong. Distance problems in computational geometry for fixed orientations. Proceedings 1st ACM Symposium on Computational Geometry, 186–195. 1985. 68