Approximating a minimum Manhattan network
Joachim Gudmundsson, Christos Levcopoulos, Giri Narasimhan · 2001
Given a set S of n points in the plane, we dene a Manhattan Network on S as a rectilinear network G with the property that for every pair of points in S, the network G contains the shortest rectilinear path between them. A Minimum Manhattan Network on S is a Manhattan network of minimum possible length. A Manhattan network can be thought of as a graph G = (V; E), where the vertex set V corresponds to points from S and a set of Steiner points S 0 , and the edges in E correspond to horizontal or vertical line segments connecting points in S [S 0 .