  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 Minimal Rectilinear Steiner Tree is to find a rectilinear
Steiner tree with minimal total length. We investigate how the complexity of
Minimal Rectilinear Steiner Tree for point sets $P$ inside the strip
$(-\infty,+\infty)\times [0,\delta]$ depends on the strip width $\delta$. We
obtain two main results. 1) We present an algorithm with running time
$n^{O(\sqrt{\delta})}$ for sparse point sets, that is, point sets where each
$1\times\delta$ rectangle inside the strip contains $O(1)$ points. 2) For
random point sets, where the points are chosen randomly inside a rectangle of
height $\delta$ and expected width $n$, 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$.
