Minimum Manhattan network problem in normed planes with polygonal balls: a factor 2.5 approximation algorithm

Nicolas Catusse, Victor Chepoi, Karim Nouioua +1

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…