Before revision:  We then consider a line-constrained version of the problem in which the segments of S are all initially on the line L. Previously, an O(n log n)-time algorithm was known for the case m=1.
After revision:  We then consider a line-constrained version of the problem in which the segments of S are all initially on the line L. Previously, an O(n \log n)-time algorithm was known for the case m=1.