Rectilinear Steiner Trees in Narrow Strips

Abstract A rectilinear Steiner tree for a set P of points in $$\mathbb {R}^2$$ 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 ]$$ ( - ∞ , + ∞ ) × [ 0 , δ ] —depends on the strip width $$\delta $$ δ . We obtain three main results. 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. Next, we consider sparse points sets, that is, point sets such that any $$1\times \delta $$ 1 × δ rectangle inside the $$\delta $$ δ -strip contains O (1) points. We first show that an optimal monotonic rectilinear Steiner tree provides an $$O(\delta )$$ O ( δ ) -approximation of an optimal rectilinear Steiner tree. Second, we present an algorithm with running time $$n^{O(\sqrt{\delta })}$$ n O ( δ ) that computes an optimal rectilinear Steiner tree for sparse point sets. For point sets whose points are chosen randomly inside the rectangle $$[0,n]\times [0,\delta ]$$ [ 0 , n ] ×