The minimum Manhattan network problem approximations and exact solutions

The Minimum Manhattan Network Problem— Approximations and Exact Solutions Marc Benkert a, Takeshi Shirabe b, and Alexander Wolff a aFaculty of Computer Science, Karlsruhe University, Germany. WWW: i11www.ilkd.uka.de/algo/group bInstitute for Geoinformation, Technical University of Vienna, Austria. Email: [email protected] 1. Introduction AManhattan p–qpath is a geodesic in the Manhattan (or L1-) metric that connects pand q, i.e. a staircase path between pand q. Given a set of points Pin the plane, a Manhattan network is a set of axis-parallel line segments that contains a Manhattan p–qpath for each pair {p, q}of points in P. In this paper we consider the minimum Manhattan network problem which consists of finding a Manhattan network of minimum total length, an MMN in short, i.e. a 1-spanner for the Manhattan metric. The problem is likely to have applications in VLSI layout. Its complexity status is unknown. The problem has been considered before. Gudmundsson et al. [1] have proposed a factor-8 O(nlog n)-time and a factor-4 O(n3)-time approximation algorithm, where nis the number of input points. Later Kato et al. [2] have given a factor-2 O(n3)-time approximation algorithm. However, their correctness proof is incomplete. In this paper we give a geometric factor-3 approximation algorithm that runs in O(nlog n) time and the first mixed-integer programming (MIP) formulation for the MMN problem. We have implemented and evaluated both approaches. 2. Preliminaries We will use the notion of a generating set that has been introduced in [2]. A generating set is a subset Zof P 2with the property that a network containing Manhattan paths for all pairs in Zis a Manhattan network of P. The authors of [2] defined a generating set Z with the nice property that Zconsists only of a linear number of point pairs. Here we use the same generating set Z, but more intuitive names for the subsets of Z. In [2] Z=Zh∪Zv∪Zx∪Zy∪Z2. Here we define Z=Zhor ∪Zver ∪Zquad, where Zhor =Zh∪Zy,Zver =Zv∪Zx, and Zquad =Z2. We consider Zquad a set of ordered pairs. Now let Rhor ={BBox(p, q)| {p, q} ∈ Zhor}, where BBox(p, q) is the smallest axis-parallel closed rectangle that contains pand q. Note that BBox(p, q) is just the line segment pq if pand qlie on the same horizontal or vertical line. In this case we consider BBox(p, q) a degenerate rectangle. Define Rver and Rquad analogously. Let Ahor,Aver, and Aquad be the subsets of the plane that are defined by the union of the rectangles in Rhor,Rver, and Rquad, respectively. As Kato et al. we start with some basic, yet incomplete network whose length is bounded by the length of an MMN. Definition 1 [2] A set of vertical line segments V covers Rver, if for any horizontal line ℓand any R∈ Rver with R∩ℓ6=∅there is a V∈ V with V∩ ℓ6=∅. We say that Vis a minimum vertical cover (MVC) if Vhas minimum length among all covers of Rver. The definition of a minimum horizontal cover (MHC) is analogous. Kato et al. have observed the following. Lemma 2 [2] The union of an MVC and an MHC has length bounded by the length of an MMN. In general such a union does not satisfy, i.e. connect by Manhattan paths, all pairs in Zver and Zhor. Additional segments must be added to the union to achieve this. To ensure that the total length of these segments can be bounded, we need covers with a special property. Obviously the segments in an MVC can be moved such that each segment is contained in a vertical edge of a rectangle in Rver. We say that an MVC is nice if additionally each cover segment is incident to a point in P. Note that each vertical rectangle edge contains at most one segment of a nice MVC, since degenerate rectangles do not share edges with other rectangles 20th EWCG Seville, Spain (2004) 20th European Workshop on Computational Geometry and must therefore be covered completely. In order to show that every point set has in fact a nice MVC, we need the following definitions. For a horizontal line ℓconsider the graph Gℓ(Vℓ, Eℓ), where Vℓis the intersection of ℓwith the vertical edges of rectangles in Rver, and there is an edge in Eℓif two intersection points belong to the same rectangle. We say that a point vin Vℓis odd if the number of points to the left of v that belong to the same connected component of Gℓis odd, otherwise vis even. For a vertical edge eof a rectangle in Rver, let an odd segment be an inclusion-maximal connected set of odd points on e. Define even segments accordingly. For example, the segment s(drawn bold in Figure 1) of the edge fis an even segment, while f\sis odd. We say that the parity of an edge changes where two segments of different parity touch. Theorem 3 Every point set Phas a nice MVC and a nice MHC. PROOF. We only show the statement for the vertical case, the horizontal case is analogous. Our proof is constructive. Let Vbe the union of all odd segments and all degenerate rectangles in Rver. Clearly Vcovers Rver. Let ℓbe a horizontal that intersects Aver. Consider a connected component Cof Gℓand let kbe the number of vertices in C. If kis even then any cover must contain at least k/2 vertices of C, and Vcontains exactly k/2. On the other hand, if k > 1 is odd then any cover must contain at least (k−1)/2 vertices of C, and Vcontains exactly (k−1)/2. Thus Vis an MVC. To see that Vis nice, we consider a vertical edge eof a rectangle in Rver and the input point p0on e. We show that either eis even or p0lies on the only odd segment of e. In both cases Vcontains only cover segments that touch an input point. Wlog. let p0be the e s fL pk pk p0 p1 p2 p2 p3 p4 Fig. 1. Proof of Theorem 3. topmost point of e. Let p0, p1,...,pkbe the input points in order of decreasing x-coordinate that span the rectangles in Rver that are relevant for the parity of e. Let pi= (xi, yi) and y0=y0,y1=y1. For 2≤i≤kdefine recursively yi= min{yi, yi−2}if iis even, and yi= max{yi, yi−2}if iis odd. Let pi= (xi, yi), and let Lbe the polygonal chain through p0, p1, p2, p3, . . . , pk) in this order, see Figure 1. Note that the parity of a point von eis determined by the number of segments of Lthat intersect the horizontal hthrough v. If his below pk, then it intersects a descending segment for each ascending segment of L, hence v is even. If on the other hand hgoes through or is above pk, then it intersects an ascending segment for each descending segment—plus p1p0, hence v is odd. So ecan change parity only in (x0,yk). ✷ A simple sweep-line algorithm yields the following. Lemma 4 A nice MVC and a nice MHC can be computed in O(nlog n)time using linear space. 3. An Approximation Algorithm Our algorithm ApproxMMN proceeds in three phases, see Algorithm 1. In phase I we compute the generating set Zver ∪Zhor ∪Zquad. In phase II we satisfy all pairs in Zver ∪Zhor by computing a nice MVC Cver and a nice MHC Chor, and by then adding at most one additional line segment for each rectangle Rver ∪ Rhor. Since each rectangle R= BBox(p, q)∈ Rver (Rhor) is covered nicely, it suffices to add a horizontal (vertical) segment whose length is the width (height) of Rin order satisfy {p, q}. Let Sbe the set of these additional segments. Consider the vertical strip that is defined by a rectangle R∈ Rver. By definition of Rver,Ris the only rectangle in Rver that intersects the interior of the strip. Thus the total length of the additional horizontal (vertical) segments is the width W(height H) of BBox(P). By Lemma 2 the network N1=Cver ∪ Chor ∪ S has length ≤ |Nopt|+H+W, where Nopt is a fixed MMN and |M|is the total length of a set Mof line segments. In phase III we satisfy the pairs in Zquad. Let Q(r, 1) = {s∈R2|xr< xsand yr< ys}be the first quadrant of the Cartesian coordinate system with origin r. Define Q(r, 2), Q(r, 3), Q(r, 4) analogously and in the usual order. Let P(q, t) = {p∈ P∩Q(q, t)|(p, q)∈Zquad}for t= 1,2,3,4. Let ∆(q, t) = Sp∈P(q,t)BBox(p, q)\int(Ahor ∪ Aver), where int(M) denotes the interior of a set M⊆R2. Let δ(q, t) be the union of those connected components of ∆(q, t) that are incident to some p∈ P(q, t). Note that each connected component A of δ(q, t) is a staircase polygon—by definition of Zquad there is a strictly xand y-monotone ordering of the points in P(q, t). The C-hull of Ais the union of Aand the bounding boxes of neighboring March 25-26, 2004 Seville (Spain) Algorithm 1 ApproxMMN Phase I: Compute Z=Zver ∪Zhor ∪Zquad. Phase II: Satisfy Zver ∪Zhor: compute a nice MVC Cver and a nice MHC Chor compute set Sof additional horizontal (vertical) segments for rectangles in Rver (Rhor) N1← Cver ∪ Chor ∪ S,N2← ∅,N3← ∅ Phase III: Satisfy Zquad: for each region δof type δ(q, t)do for each connected component Aof δdo compute rectangulation RA′of A′ N2←N2∪∂A′∪ {sA′} N3←N3∪(RA′\∂A′) end for end for return N=N1∪N2∪N3 input points on the boundary ∂A of A. It is known that any MMN rectangulates the C-hull of A[1, Lemma 4]. The same holds for a slightly smaller region A′that can be connected to N1via at most one segment sA′. There is a simple O(n)-time factor2 approximation algorithm Bfor rectangulating staircase polygons [1]. We use Bto compute the rectangulation RA′of each A′. Let N2be the union of all ∂A′and all sA′. Let N3be the union of the rectangulations RA′without ∂A′. Our algorithm returns the line segments in N=N1∪N2∪N3. To bound the length of Nwe partition the plane into two regions and compare Nto Nopt in each region separately. Region A3is the union of int(A′) over all areas of type A′, while A12 =R2\ A3. We have N1∪N2⊆ A12 and N3⊆ A3, and the interiors of different regions of type Ado not intersect. On the one hand the approximation factor of Byields that |N∩ A3| ≤ 2|Nopt ∩ A3|. On the other hand we can show that |N2| ≤ 2|Nopt| − (H+W). Thus |N∩ A12|=|(N1∪N2)∩ A12| ≤ 3|Nopt ∩ A12|, which in turn yields |N| ≤ 3|Nopt|. Theorem 5 A 3-approximation of an MMN can be computed in O(nlog n)time and O(n)space. 4. A MIP Formulation In this section we give the first MIP formulation of the MMN problem. This formulation gives us the possibility to implement an exact solver for the MMN problem that can solve small examples in a bearable amount of time. Those will be used as benchmarks for our approximation algorithm. We need some notation: For a set Pof ninput points p1(x1, y1),...,pn(xn, yn) let x1<···< xu and y1<··· < ywbe the ascending sequences of xrespectively y-coordinates of the input points. The grid Γ induced by Pconsists of the grid points (xi, yj) with i= 1,...,u and j= 1,...,w. In this section we will only consider pairs {p, q} ∈ Z with xp≤xq. This is no restriction since we can flip the names of pand q. For each such pair let V(p, q) = Γ ∩BBox(p, q) and let A(p, q) be the set of arcs between horizontally or vertically adjacent grid points in V(p, q). Horizontal arcs are always directed from left to right, vertical arcs point upwards (downwards) if yp< yq (yp> yq). Our formulation is based on the grid graph GP(V, A), where V=S{p,q}∈ZV(p, q) and A=S{p,q}∈ZA(p, q). Let E={{g, g′} | (g, g′)∈ Aor (g′, g)∈A}be the set of undirected edges. For each pair {p, q} ∈ Zwe enforce the existence of a p–qManhattan path by a flow model as follows. We introduce one 0–1 variable f(p, q, g, g′) for each arc (g, g′) in A(p, q), which encodes the size of the flow along arc (g, g′). For each grid point gin V(p, q) we introduce the flow constraint X (g,g′)∈A(p,q) f(p, q, g, g′) −X (g′,g)∈A(p,q) f(p, q, g′, g)          =     +1 if g=p, −1 if g=q, 0 else. (1) Next we introduce a continuous variable F(g, g′) for each edge {g, g′}in E. This variable will in fact be forced to take a 0–1 value by the objective function and the following constraints. The MMN that we want to compute will consist of all grid edges {g, g′}with F(g, g′) = 1. We now add one or two constraints for each {g, g′}in Eand each {p, q} ∈ Zwith gg′⊆BBox(p, q): F(g, g′)≥(f(p, q, g, g′) if (g, g′)∈A, f(p, q, g′, g) if (g′, g)∈A. (2) Note that the two conditions are not mutually exclusive. Our objective function expresses the total length of the selected grid edges: min! X {g,g′}∈E |gg′| · F(g, g′),(3) where |gg′|is the Euclidean distance of gand g′. This MIP formulation uses O(n3) variables and constraints. By treating pairs in Zquad more carefully, a reduction to O(n2) is possible, see full paper. It is not hard to see that our formulation always yields an MMN: 20th European Workshop on Computational Geometry Theorem 6 Let Pbe a set of points and let Z,A, and Ebe defined as above. Let F:E→R+ 0and f:Z×A→ {0,1}be functions that fulfill (1) & (2) and minimize (3). Then the set of line segments {gg′| {g, g′} ∈ E, F(g, g′)≥1}is an MMN of P. Due to our objective function (3), Equation (1) can be replaced by an inequality (with direction ≥). If the resulting constraint matrix was totally unimodular (every square submatrix has determinant in {−1,0,+1}), every vertex of the solution polyhedron would be integral and the MMN problem would in fact correspond to an LP. Unfortunately it turned out that this is not the case and that there are instances with fractional vertices that minimize our objective function. 5. Experiments We used two different types of random instances. Squarekinstances were generated by drawing ndifferent points with uniform distribution from a kn ×kn integer grid. We wanted to see the effects of having more (ksmall) or less (klarge) points with the same xor y-coordinate. If a pair of points shares a coordinate, the manhattan path connecting them is uniquely determined. Circlekinstances consist of a point p1at the origin and n−1 points on the upper half of the unit circle. The points are distributed as follows. The interval I= [0, π/4] is split into ksubintervals I1,...,Ikof equal length. We used k∈ {1,2,5,10}. Then n−1 random numbers r2,...,rnare drawn from I. If the number rifalls into a subinterval of even index, it is mapped to the point pi= (cos ri,sin ri) otherwise to pi= (−cos ri,sin ri). The resulting points pi(except for the topmost point in each quadrant and the “bottommost” point in each subinterval) all form pairs {pi, p1} that are in Zquad. This makes Circle instances very different from Square instances where only few point pairs belong to Zquad. We generated instances of the above types and solved them with ApproxMMN and with Cplex using the MIP formulation of Section 4. We implemented ApproxMMN in C++ using the compiler gcc-3.3. The asymptotic runtime of our implementation is Θ(n2), the real runtime was measured on an AMD Athlon 1800+with 512 MB RAM under Linux-2.4.20. To compute exact solutions we used the LP Barrier Solver of ILOG Cplex-9.0 on an IBM RS/6000. The results of our experiments can be found in the diagram below. The sample size, i.e. the number of points per instance, is shown on the x-axis. For each sample size we generated 30 instances and averaged the results over those. The y-axis shows the performance ratio of ApproxMMN, i.e. the ratio of the length of the network computed by ApproxMMN over the length of the MMN computed by Cplex. Cplex ran out of memory on Circle01 instances of more than 45 points and on Square10 instances of more than 110 points. Below these thresholds ApproxMMN always had a performance ratio below 1.55, which is much better than what the approximation factor of 3 suggests. While the ratio seems to approach 1 on Square instances of increasing size, the picture is not so clear for Circle instances: 1 1.1 1.2 1.3 1.4 1.5 10 20 30 40 50 60 70 80 90 100 110 Circle01 ✸✸✸ ✸ ✸ ✸✸✸ ✸ Circle10 ++ +++ +++++++++ Square01 ✷ ✷ ✷ ✷ ✷✷✷✷✷✷✷✷✷✷✷✷✷✷✷✷✷ ✷ Square10 × ×× ×××××××××××××××××× × The runtime of ApproxMMN was practically independent of the type of instance. The CPU times we measured reflected the quadratic asymptotic runtime. 500 points took roughly 0.3 seconds. The exact solver depended much more on the type of instance than the approximation algorithm. It solved Square instances much faster than Circle instances. This is due to the fact that pairs in Zquad require a quadratic number of variables and constraints in our MIP formulation, while pairs in Zver and Zhor need only a linear number. 100 points of type Squarektook 0.6–1.6 seconds and 6–13 seconds for k= 1 and 10, respectively, while 40 points of type Circlektook 61–480 seconds and 1.2–2.4 seconds for k= 1 and 10, respectively. References [1] J. Gudmundsson, C. Levcopoulos, and G. Narasimhan. Approximating a minimum Manhattan network. Nordic J. Comput., 8:219–232, 2001. [2] R. Kato, K. Imai, and T. Asano. An improved algorithm for the minimum Manhattan network problem. In Proc. ISAAC’02, vol. 2518 of LNCS, pages 344–356, 2002.