2 papers
cs.CG2011
Bidirected minimum Manhattan network problem
Nicolas Catusse, Victor Chepoi, Karim Nouioua +1
In the bidirected minimum Manhattan network problem, given a set T of n terminals in the plane, we need to construct a network N(T) of minimum total length with the property that t…
cs.CG2010
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…