  Let B be a centrally symmetric convex polygon of R^2 and || p - q || be the
distance between two points p,q in R^2 in the normed plane whose unit ball is
B. For a set T of n points (terminals) in R^2, a B-Manhattan 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 || t_i - t_j
||. A minimum B-Manhattan network on T is a B-Manhattan network of minimum
possible length. The problem of finding minimum B-Manhattan networks has been
introduced by Gudmundsson, Levcopoulos, and Narasimhan (APPROX'99) in the case
when the unit ball B is a square (and hence the distance || p - q || is the l_1
or the l_infty-distance between p and q) and it has been shown recently by
Chin, Guo, and Sun (SoCG'09) to be strongly NP-complete. Several approximation
algorithms (with factors 8, 4 ,3 , and 2) for minimum Manhattan problem are
known. In this paper, we propose a factor 2.5 approximation algorithm for
minimum B-Manhattan network problem. The algorithm employs a simplified version
of the strip-staircase decomposition proposed in our paper (APPROX'05) and
subsequently used in other factor 2 approximation algorithms for minimum
Manhattan problem.
