A rectilinear Steiner tree for a set P of points in \(\mathbb {R}^2\) is a tree that connects the points in P using horizontal and vertical line segments. The goal of Minimum Rectilinear Steiner Tree is to find a rectilinear Steiner tree with minimum total length. We investigate how the complexity of Minimum Rectilinear Steiner Tree for point sets P inside a \(\delta \) -strip—that is, a strip of the form \((-\infty ,+\infty )\times [0,\delta ]\) —depends on the strip width \(\delta \) . We obtain three main results. 1. We present an algorithm that finds an optimal monotonic rectilinear Steiner tree in O(n) time, assuming the points are already sorted by x-coordinate. We show that when the difference between any two distinct x-coordinates is at least \(\delta \) , then an optimal monotonic rectilinear Steiner tree for a point set inside a \(\delta \) -strip is also optimal among all (possibly non-monotonic) rectilinear Steiner trees.
2. Next, we consider sparse points sets, that is, point sets such that any \(1\times \delta \) rectangle inside the \(\delta \) -strip contains O(1) points. We first show that an optimal monotonic rectilinear Steiner tree provides an \(O(\delta )\) -approximation of an optimal rectilinear Steiner tree. Second, we present an algorithm with running time \(n^{O(\sqrt{\delta })}\) that computes an optimal rectilinear Steiner tree for sparse point sets.
3. For point sets whose points are chosen randomly inside the rectangle \([0,n]\times [0,\delta ]\) , we present an algorithm that is fixed-parameter tractable with respect to \(\delta \) and linear in n. It has an expected running time of \(2^{O(\delta \sqrt{\delta })} n\) .
