Summary: Given a set \(S\) of \(n\) points in the plane, we define 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'\), and the edges in \(E\) correspond to horizontal or vertical line segments connecting points in \(S\cup S'\). A Manhattan network can also be thought of as a 1-spanner (for the \(L_1\)-metric) for the points in \(S\).
Let \(R\) be an algorithm that produces a rectangulation of a staircase polygon in time \(R(n)\) of weight at most \(r\) times the optimal. We design an \(O(n\log n+ R(n))\) time algorithm which, given a set \(S\) of \(n\) points in the plane, produces a Manhattan network on \(S\) with total weight at most \(4r\)-times that of a minimum Manhattan network. Using known rectangulation algorithms, this gives us an \(O(n^3)\)-time algorithm with approximation factor four, and an \(O(n\log n)\)-time algorithm with approximation factor eight.