Optimal spanners for axis-aligned rectangles

Optimal Spanners for Axis-Aligned Rectangles 1 Tetsuo Asano aMark de Berg bOtfried Cheong bHazel Everett cHerman Haverkort d Naoki Katoh eAlexander Wolff f aJAIST, Japan bTU Eindhoven, the Netherlands cLORIA, France dUtrecht University, the Netherlands eKyoto University, Japan fUniversit¨at Karlsruhe, Germany 1. Introduction Geometric networks arise frequently in our everyday life: road networks, telephone networks, and computer networks are all examples of geometric networks that we use daily. They also play a role in disciplines such as VLSI design and motion planning. Almost invariably, the purpose of the network is to provide a connection between the nodes in the network. Often it is desirable that the connection through the network between any pair of nodes be relatively short. From this viewpoint, one would ideally have a direct connection between any pair of nodes. This is usually infeasible due to the costs involved, so one has to compromise between the quality and the cost of the connections. For two given nodes in a graph, the ratio of their distance in the graph and their ‘direct’ distance is called the dilation or stretch factor for that pair of nodes, and the dilation of a graph is the maximum dilation over all pairs of nodes. For geometric networks, this is more precisely defined as follows. Let Sbe a set of npoints (in the plane, say), and let Gbe a graph with node set S. Now the dilation for a pair of points p, q is defined as the ratio of the Email addresses: [email protected] (Tetsuo Asano), [email protected] (Mark de Berg), [email protected] (Otfried Cheong), [email protected] (Hazel Everett), [email protected] (Herman Haverkort), [email protected] (Naoki Katoh), [email protected] (Alexander Wolff). 1Part of this research was done during the First Utrecht-Carleton Workshop on Computational Geometry. H.H. acknowledges support by the Netherlands’ Organization for Scientific Research (NWO). length of the shortest path in Gbetween pand q, and the length of the segment pq. (The length of a path is the sum of the lengths of its edges.) Again, the dilation of Gis the maximum dilation over all pairs of points in S. A graph with dilation tis called a t-spanner. Ideal networks are t-spanners for small twith small cost. Spanners were introduced by Peleg and Sch¨affer [6] in the context of distributed computing, and by Chew [1] in the context of computational geometry. They have attracted much attention since— see for instance the survey by Eppstein [2]. The cost of spanners can be measured according to various criteria. For example, it is sometimes defined as the number of edges (here the goal is to find a spanner with O(n) edges), or as the total weight of the edges (here the goal is to find a spanner whose total weight is a constant times the weight of a minimum spanning tree). Additional properties, such as bounding the maximum degree or the diameter, have been considered as well. We generalize the notion of spanners to geometric networks whose nodes are rectangles rather than points. Let Sbe a set of nnon-intersecting, axis-parallel rectangles and let Ebe a set of axisparallel segments connecting pairs of rectangles. For any two points p, q in the union of the rectangles, the dilation is now the ratio of the length of the shortest rectilinear path in the network between pand qand their L1-distance. Here a path in the network is a path that stays within the union of the rectangles and the connecting segments. The dilation of the network is the maximum dilation over all pairs p, q. Again, our aim is to construct a network whose dilation is small. To illustrate the concept, imagine one is given a number of rect20th EWCG Seville, Spain (2004) 20th European Workshop on Computational Geometry angular buildings, which have to be connected by footbridges. It is quite frustrating if, to walk to a room opposite ones own room in an adjacent building, one has to walk all the way to the end of a long corridor, then along the footbridge, and then back again along the corridor in the other building. Hence, one would usually place the footbridge in the middle between buildings. Following this analogy, we will call the rectangles in the input buildings from now on, and the connecting segments bridges. We call the underlying graph of the network the bridge graph. The generalization we study introduces one important additional difficulty in the construction of a spanner: for points one only has to decide which edges to choose in the spanner, but for buildings, one also has to decide where to place the bridge between a given pair of buildings. It is the latter problem we focus on in this paper: we assume the topology of the network (the bridge graph) is given, and our only task is to place the bridges so as to minimize the dilation. Formally, our problem can be stated as follows: we are given a set Sof axis-parallel disjoint rectangles (buildings) in the plane, a graph Gwith node set S, and for each arc eof Gabridge region Λe, an axis-aligned rectangle connecting the two buildings. Buildings may degenerate to segments or points. The bridge graph Gmust only have arcs between buildings that can be connected by a horizontal or vertical segment, and may not have multiple edges or loops. The bridge regions must be disjoint from each other and the buildings. Our goal is to find a set of horizontal or vertical bridges lying in the bridge regions that has minimum dilation. Figure 1 shows a bridge graph (the bridge regions are shaded) and a set of possible bridges. Note that the bridge regions Λ2and Λ3simply allow any bridge between the two buildings, but bridge region Λ1has been chosen so as to avoid intersecting s4or the bridge between s3and s4. Our results are as follows. •In general, the problem is NP-hard. •If the bridge graph is a tree, then the problem can be solved by a linear program with O(n2) variables and constraints. •If the bridge graph is a path, then the problem can be solved in O(n3log n) time. •If the bridge graph is a path and the buildings are sorted vertically along this path, the problem can be solved in time O(n2). A (1 + ε)-approximation can be computed in linear time. s1 s2 s3 s4 Λ1 Λ2 Λ3 Fig. 1. A bridge graph and a bridge configuration 2. The bridge graph is arbitrary The bridge-placement problem is NP-hard if the bridge graph is allowed to be arbitrary. We prove this by a reduction from Partition. The input to Partition is a set Bof npositive integers, and the task is to decide whether Bcan be partitioned into two subsets of equal sum. Partition is NPhard [3, Problem SP12]. Theorem 1 It is NP-hard to decide whether the bridges in a given bridge graph on nrectangular buildings can be placed such that the dilation is at most 2. 3. The bridge graph is a tree In this section we will show that the bridgeplacement problem can be solved by a linear program if the bridge graph is a tree. We start by introducing some terminology and notation, and by proving some basic lemmas. As before, we denote the bridge graph by G. Any set of bridges realizing Gwill be called a configuration. p q π(p, q,B) kpqk Fig. 2. March 25-26, 2004 Seville (Spain) Fig. 3. Given a configuration Band two points pand q in the union of all buildings, we use π(p, q, B) to denote the family of rectilinear shortest paths from p to qwithin the configuration (that is, paths whose links lie inside buildings or on bridges). The paths of this family are essentially the same, they differ only in how they connect two points inside the same building, and so we will simply speak about the unique path π(p, q, B). The dilation of the path π=π(p, q, B) is dil(π) := |π|/kpqk, where |π|is the total length of πand kpqkis the L1-distance of pand q. Figure 2 shows a configuration and an example path. The dilation dil(B)of a configuration Bis defined as the maximum dilation of any path with respect to B. Our aim is to find a configuration of minimum dilation. We first characterize pairs of points that are responsible for the dilation of a given configuration. Lemma 2 Let σbe the dilation of a configuration Bwhose underlying graph is a tree. Then there are points pand qwith dil(π(p, q, B)) = σsuch that the closed bounding box of pand qdoes not contain any point of a building other than pand q, and at least one of the points pand qis a building corner. A point pair (p, q) as in the lemma—its bounding box contains no other point of any building and at least one of pand qis a building corner—will be called a visible pair—see Figure 3 for examples. We denote the set of all visible pairs by V. Given a bridge graph G, our goal is to minimize max (p,q)∈V dil(π(p, q, B)) over all configurations Brealizing G. We show that this problem can be reformulated as a linear program. Theorem 3 If the bridge graph Gis a tree, then a placement of the bridges that minimizes the dilation can be computed by solving a linear program with O(n2)variables and constraints, where nis the number of bridges in the bridge graph. 4. The bridge graph is a path In the previous section we have given a linear program for the bridge-placement problem for the case where the bridge graph is a tree. Linear programs can be solved in practice, and for integer coefficients, interior-point methods can solve them in time polynomial in the bit-complexity of the input [4]. It is not known, however, if they can be solved in polynomial time on the real RAM, the standard model of computational geometry. In this section, we give polynomial time algorithms for the case where the bridge graph is a path. Since the bridge graph Gis a path, we can number the buildings and bridges so that bridge biconnects buildings si−1and si, for 1 ≤i≤n(so there are n+ 1 buildings and nbridges). Before we continue, we need to introduce some more terminology. We consider a path π=π(p, q, B) to be oriented from pto q. After traversing a bridge b, the path can continue straight on to traverse the next bridge b′if band b′are collinear. In all other cases, it has to turn. b9 b10 b8 b12 b13 p π b1 b2 b4 b6 b7 b11 b14 q s6 b5 b3 s10 s1 Fig. 4. U-turns and their outer sides Given a path π, a link ℓof πis a maximal straight segment of the path. A link can contain more than one bridge if they are collinear. For example, in Figure 4 there is a link containing b1and b2, and another link containing b8,b9, and b10. The path πturns at both ends of a link (except for the first and last link). The link is a right Uturn if πturns right before and after the link. A left U-turn is defined symmetrically. In Figure 4, the links containing bridges (b1, b2), (b4, b5), and b12 are right U-turns, while the links containing b7, (b8, b9, b10), b11, and (b13, b14) are left U-turns. Note that there can be U-turns that do not contain 20th European Workshop on Computational Geometry any bridges, as the link of πinside building s6in Figure 4. The inner side and outer side of a U-turn are rectangular regions infinite on one side, and bounded by the line supporting the link and the two lines orthogonal to it through the first and last points of the link. The outer side lies locally to the left of a right U-turn, or to the right of a left U-turn, the inner side lies locally to the right of a right U-turn or to the left of a left U-turn. In Figure 4, the outer sides of all U-turns are shaded. U-turns are the links of a path that determine its dilation, as the following lemma shows. Lemma 4 Let Band B′be configurations, (p, q) a visible pair, and π:= π(p, q, B)and π′:= π(p, q, B′)the paths between pand qwith respect to the two configurations. If dil(π′)<dil(π)then there exists a U-turn ℓcontaining bi...bjof πsuch that the corresponding bridges b′ i,...,b′ jof B′lie strictly on the inner side of ℓ. We will give an algorithm that takes as input the set of buildings s0,...,snand a real number σ > 1, and computes a configuration Bwith dil(B)≤σ, or determines that no such configuration exists. The algorithm computes nsets I1, I2,...,In, where Iiis a set of possible bridges between si−1and si. The sets are defined recursively as follows. Assume that I1,...,Ii−1have already been defined. For each visible pair (p, q) with p∈Si−1 j=0 sjand q∈siwe define I(p, q) as the set of bridges biconnecting si−1and si such that the following holds: there is a set of bridges b1∈I1, b2∈I2, ...,bi−1∈Ii−1such that dil(π(p, q, (b1,...,bi))) ≤σ. Finally, Iiis the intersection of all I(p, q). Note that for each visible pair (p, q) we can choose the bridges in I1,...,Ii−1independently. This makes it possible to compute Iiefficiently, as we will see below. On the other hand, it implies that not every sequence of bridges chosen from the sets will be a configuration with dilation at most σ—our main lemma will be to show that such a sequence does indeed exist. Once we know I1,...,In, we can recursively compute a configuration with dilation at most σ: Choose an arbitrary bridge bn∈In. If bridges bn−1, bn−2,...,bi+1 have been computed, choose a bridge bi∈Iiwhose distance from bi+1 is minimal. Since Iiis an “interval of bridges”, this implies that either biand bi+1 are collinear, or biis one of the extreme bridges in Ii. We now prove that this approach is correct. Lemma 5 Let I1,...,Inbe given as defined above. A configuration Bwith dilation dil(B)≤σexists if and only if In6=∅. If it exists, it can be computed in O(n)time from the intervals. Lemma 6 The intervals I1,...,Indefined above can be computed in O(n2)time and O(n)space. Lemmas 6 and 5 imply the following theorem. Theorem 7 Given a bridge graph Gon a set of n+1 buildings that is a path and a real number σ > 1, we can in time O(n2)compute a configuration B realizing Gwith dil(B)≤σor determine that no such configuration exists. It seems hard to improve this result when there are Θ(n2) visible pairs that could determine the dilation. In fact, we do not even know how to decide in o(n2) time whether a given configuration has dilation ≤σ. If the number kof visible pairs of the given set of buildings is o(n2/log n), the running time can be improved to O(klog n). We solve the original optimization problem using Megiddo’s parametric search [5]. Theorem 8 Given a bridge graph on a set of n+1 buildings that is a path, we can compute a configuration with the optimal dilation in time O(n3log n), or in time O(nk log2n), where kis the number of visible pairs. References [1] L. P. Chew. There are planar graphs almost as good as the complete graph. J. Comput. Syst. Sci., 39:205–219, 1989. [2] David Eppstein. Spanning trees and spanners. In J¨orgR¨udiger Sack and Jorge Urrutia, editors, Handbook of Computational Geometry, pages 425–461. Elsevier Science Publishers B.V. North-Holland, Amsterdam, 2000. [3] M. R. Garey and D. S. Johnson. Computers and Intractability: A Guide to the Theory of NPCompleteness. W. H. Freeman, New York, NY, 1979. [4] N. Karmarkar. A new polynomial-time algorithm for linear programming. Combinatorica, 4:373–395, 1984. [5] N. Megiddo. Applying parallel computation algorithms in the design of serial algorithms. J. ACM, 30(4):852– 865, 1983. [6] D. Peleg and A. Sch¨affer. Graph spanners. J. Graph Theory, 13:99–116, 1989.