Minimum Manhattan Network Problem in Normed Planes with Polygonal Balls: A Factor 2.5 Approximation Algorithm

作者：Catusse N; Chepoi V^*; Nouioua K; Vaxes Y

来源：Algorithmica, 2012, 63(1-2): 551-567.

DOI：10.1007/s00453-011-9560-z

• Normed plane
• Distance
• Geometric network design
• Manhattan network
• Approximation algorithms

Let B be a centrally symmetric convex polygon of R-2 and parallel to p-q parallel to be the distance between two points p, q is an element of R-2 in the normed plane whose unit ball is B. For a set T of n points (terminals) in R-2, a B-network on T is a network N(T) = (V, E) with the property that its edges are parallel to the directions of B and for every pair of terminals t(i) and t(j), the network N(T) contains a shortest B-path between them, i.e., a path of length parallel to ti - t(j)parallel to. A minimum B-network on T is a B-network of minimum possible length. The problem of finding minimum B-networks has been introduced by Gudmundsson, Levcopoulos, and Narasimhan (APPROX%26apos;99) in the case when the unit ball B is a square (and hence the distance parallel to p - q parallel to is the l(1) or the l(infinity)-distance between p and q) and it has been shown recently by Chin, Guo, and Sun (Symposium on Computational Geometry, pp. 393-402, 2009) to be strongly NP-complete. Several approximation algorithms (with factors 8, 4, 3, and 2) for the minimum Manhattan problem are known. In this paper, we propose a factor 2.5 approximation algorithm for the minimum B-network problem. The algorithm employs a simplified version of the strip-staircase decomposition proposed in our paper (Chepoi et al. in Theor. Comput. Sci. 390:56-69, 2008, and APPROX-RANDOM, pp. 40-51, 2005) and subsequently used in other factor 2 approximation algorithms for the minimum Manhattan problem.

• 出版日期2012-6