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

Let $ℬ$ be a centrally symmetric convex polygon of ℝ² and ∥p-q∥ be the distance between two points p,q∈ ℝ² in the normed plane whose unit ball is $ℬ$ . For a set T of n points (terminals) in ℝ², a $ℬ$ ‐network on T is a network N(T)=(V,E) with the property that its edges are parallel to the directions of $ℬ$ and for every pair of terminals t i and t j , the network N(T) contains a shortest $ℬ$ ‐path between them, i.e., a path of length ∥t i -t j ∥. A minimum $ℬ$ ‐network on T is a $ℬ$ ‐network of minimum possible length. The problem of finding minimum $ℬ$ ‐networks has been introduced by Gudmundsson, Levcopoulos, and Narasimhan (APPROX’99) in the case when the unit ball $ℬ$ is a square (and hence the distance ∥p-q∥ is the l 1 or the l ∞‐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 $ℬ$ ‐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.