Rectilinear Steiner Trees in Narrow Strips

A rectilinear Steiner tree for a set P of points in R² 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 δ δ -strip—that is, a strip of the form (-∞ ,+∞ )× [0,δ ] ( - ∞ , + ∞ ) × [ 0 , δ ] —depends on the strip width δ δ . 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 δ δ , then an optimal monotonic rectilinear Steiner tree for a point set inside a δ δ -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× δ 1 × δ rectangle inside the δ δ -strip contains O (1) points. We first show that an optimal monotonic rectilinear Steiner tree provides an O(δ ) O ( δ ) -approximation of an optimal rectilinear Steiner tree. Second, we present an algorithm with running time nO(√δ ) 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]× [0,δ ] [ 0 , n ] ×