The rectilinear class Steiner tree problem for intervals on two parallel lines

The paper considers a genealization of the Rectilinear Steiner Tree problem, where the present input is classes of required points instead of simple required points. The task is to find a minimum rectilinear tree connecting at least one point from each class. The paper proves that the version, where all required points lie on two parallel lines, called Rectilinear Class Steiner Tree (channel) problem, is NP-hard. But it gives a linear time algorithm for the case where the points of each required class are clustered, and the classes consist of non-overlapping intervals of points.